A central Artificial Intelligence wikibook has been started. Content from this book will eventually be merged into Artificial Intelligence. Please use that article's discussion page for discussion on the subject.

Introduction

While no consensual definition of Artificial Intelligence (AI) exists, AI is broadly characterized as the study of computations that allow for perception, reason and action.

We can divide the cognitive world into 3 domains - Intelligent, Normal and Below Normal. The average human being does Normal things. Intelligence is always demonstrated in NEW domains. The properties of a New domain are that the patterns in these domains are ambiguous and are incomplete. Therefore, Intelligence can be better understood as the ability to work efficiently with Incomplete, Ambiguous Patterns. Artificial Intelligence extends the computing power from an algorithmic domain to this Incomplete, Ambiguous patterns domain. (Algorithms have the property of Definiteness which cannot be satisfied in this domain.)

There are two major views of work in the field of AI: some people view AI as the quest for mechanisms, or algorithms, in which their output would be considered intelligent if performed by a human (i.e., a chess playing computer). Others view AI as a scientific discipline to understand the human mind, by modelling the cognitive processes humans go through.

With a bit of oversimplification, AI is:

simulated intelligent behavior
symbolic processing

Main techniques include:

rule-based or tree-based knowledge representation.
logic programming
heuristics

AI has influenced a number computer scientific areas:

databases
software engineering, include object-oriented design
distributed computing
graphics
user interfaces
simulation

Search

Search is a classical AI topic. Many AI problems reduce to searching for solutions in the problem state space. The basic idea:

initial state
apply an operator to transform state.

Example: symbolic integration

To find this integral: $\int \frac{x^{4}}{(1 - x^{2})^{5 / 2}} d x$ , you can try different tricks, and not all will work.

Example: 8-puzzle

If a bunch of tiles are arranged like this:

$[\begin{matrix} 2 & 8 & 3 \\ 1 & 6 & 4 \\ 7 & ◻ & 5 \end{matrix}]$

And this is the correct order:

$[\begin{matrix} 1 & 2 & 3 \\ 8 & ◻ & 4 \\ 7 & 6 & 5 \end{matrix}]$

and the $◻$ is a blank tile you can slide around, then you can use search to figure it out. Each state will have at most four resulting states, because you can slide $◻$ up, left, right, and down.

Heuristic search

You can use DFS (Depth-first search) or BFS (Breadth-first search) to explore a graph, but it may require O( $b^{m}$ ) node visits, but if you want to search more efficiently, it might be better to check out the promising leads first. With a heuristic search, at each step of the way, you use an evaluation function to choose which subtree to explore. You can think of a heuristic search like a "best-first" search.

It is important to remember that a heuristic search is best at finding a solution that is "good enough" rather than the perfect solution. Some problems are so big that finding the perfect solution is too hard.

To do a heuristic search you need an evaluation function that lets you rank your options.

Sliding tile puzzle aka 8-puzzle Example

This website has an example of a sliding tile puzzle if you are unfamiliar with what these are. Sliding tile puzzles (or 8-puzzles) provide a problem that can be solved more efficiently with a heuristic search (like A*) vs. DFS and BFS.

For the 8-puzzle, we could use this as a simple evaluation function:

$f = g + w$

where $g$ is the distance from the root, and $w$ is the number of misplaced tiles, not counting the $◻$ tile.

The evaluation function $f = g + w$ would score the initial state

$[\begin{matrix} 5 & 4 & ◻ \\ 6 & 1 & 8 \\ 7 & 3 & 2 \end{matrix}]$

as

$4 = 0 + 4$

A better heuristic is known as the Manhattan distance. This heuristic value is determined by the sum of the distance for each tile from its goal location. This heuristic is admissible, such that it does not overestimate the cost to reach the goal node.

TODO: draw search tree for 8-puzzle and show heuristic search path solution, vs. DFS and BFS search solution.

The above evaluation function is just one possible guess. We could play with other evaluation functions, like:

$f = g + p$ , where g is the same, and p is the sum of distances that each tile is from the root.

Or we could use $f = g + p + 3 S$ , where $g$ and $p$ are the same, and $S$ is the sum of sequence scores $Σ s$ . $s$ is calculated for each tile like so:

$s = {\begin{matrix} 1, & if the tile is the central tile \\ 0, & if the tile is the noncentral tile and is followed by the proper successor \\ 2, & if the tile is non-central and is not followed by its proper successor \end{matrix}$

Tic Tac Toe and minimax

to be done later

n,mn,mn,mn

Knowledge discovery and machine learning

Probability is probably going to be interesting

Example 1: tossing a coin once

$ω_{1} = H E A D S$

$ω_{2} = T A I L S$

$Ω = {ω_{1}, ω_{2}}$

$X (ω)$ can be a function like the number of heads. $X (ω_{1}) = 1$ , and $X (ω_{2}) = 0$ .

Example 2: tossing a coin twice.

$Ω = {H H, H T, T H, T T}$

Potiential outputs from our $X (ω)$ function:

$X (ω) = {2, 1, 1, 0}$

On to probability.

$P (H H)$ should return the probability of getting two heads.

Often we denote $P (X (ω) = x)$ as $P (x)$ .

Logarithms refresher

The logarithm L of a number N, in a given base B, is such that $N = B^{L}$

For instance, make $N = 8$ and $B = 2$ . Then, you would have $L = 3$ , as you can see: $l o g_{2} 8 = 3$

Another example:

$l o g_{2} (\frac{1}{4}) = l o g_{2} (2^{- 2}) = - 2 l o g_{2} (2^{1}) = - 2$

Emacs SLIME appendix

Emacs SLIME User Manual

The recommended way to use lisp (according to the #lisp crew) is to use SBCL and emacs with the SLIME extension. Below are some useful commands:

Command                what it does
M-x slime              starts slime session
C-x b                  switches to another buffer
C-c C-l                load current file into SLIME
C-c C-k                compile current file
C-c C-c                compile current function
C-x C-s                save current buffer
C-x C-c                quit emacs
C-c C-z                jump to slime buffer
C-x C-f                open a new buffer
C-x 2                  view two frames, horizontally stacked.
C-x 1                  return to a one-frame view
C-x o                  move to other frame

Common lisp resources

useful links

Wikipedia page for Common Lisp

This page has links to lots of free lisp tools.

Common Lisp HyperSpec online documentation for common lisp.

Lisp in a box seems to be the easiest way for a new user to get set up to use Common Lisp on Windows and Linux.

SLIME User Manual

Practical Common Lisp, by Peter Seibel This book is really good.

a few lisp coding examples

CL-USER> (loop for e in '(a b c)
               do (format t "e is ~a.~%" e)
               collect e)
e is A.
e is B.
e is C.
(A B C)
CL-USER> (let ((x 0)
               (y 1)
               (z 2))
           (format t "x: ~a y: ~a z: ~a~%" x y z)
           (+ x y z))
x: 0 y: 1 z: 2
3
CL-USER> (if (< 3 1) 0 1)
1
CL-USER> (if (< 3 5) 1 2)
1
CL-USER> (cond ((< 3 1) 1)
               ((< 9 10) 2)
               (t 3))
2

class notes on lisp

Lisp is made of symbolic expressions. Everything descends from them.

symbolic expression
- atom
  - number
    - float
    - fixed-point
  - symbol
- list

A lisp program is an ordered set of lists. In lisp, programs and data have the same form. Programs can be manipulated by programs.

(+ 8 3)

In the above computation, + is an operator, and 8 and 3 are arguments.

Some example computations:

CL-USER> (- 8 3)
5
CL-USER> (- 8 3 4)
1
CL-USER> (1+ 8)
9
CL-USER> (1- 8)
7
CL-USER> (* 8 (+ 3 7))
80
CL-USER> (expt 2 3)
8
CL-USER> (expt 3.3 2.2)
13.827086
CL-USER> (sqrt 9)
3
CL-USER> (abs -5)
5

Symbols and setq

x is a symbol, which is sort of like a variable.

(setq x 5) ; assigns 5 to symbol x.

setq does not evaluate its first argument.

Symbols and variables are different; e.g., x is a symbol throughout the program. However, x can be bound to different variables, e.g., a global and a local. The global x may have a value of 5, while the local x has the value 8.

setq can make multiple assignments:

CL-USER> (setq x 5 y 6 y 7)
7

quote

CL-USER> (quote (a b c))
(A B C)
CL-USER> '(a b c)
(A B C)
CL-USER> (setq x '(+ 3 4))
(+ 3 4)
CL-USER> (setq x (+ 3 4))
7
CL-USER> (setq x '(+ 3 (* 4 5)))
(+ 3 (* 4 5))
CL-USER> (setq x `(+ 3 ,(* 4 5) (- 6 7)))
(+ 3 20 (- 6 7))

setq vs set

CL-USER> (setq x 'y)
Y
CL-USER> x
Y
CL-USER> (set x 'z)
Z
CL-USER> x
Y
CL-USER> y
Z

set, rather than setq, evaluates the first argument. setq stands for set quote.

setf, remove, cons

assignment of lists:

CL-USER> (setf friends '(dick jane))
(DICK JANE)
CL-USER> friends
(DICK JANE)
CL-USER> (setf enemies '(grinch ghost))
(GRINCH GHOST)
CL-USER> (setf friends (remove 'ghost enemies))
(GRINCH)
CL-USER> (setf friends (cons 'ghost friends))
(GHOST GRINCH)
CL-USER> friends
(GHOST GRINCH)

first, second, third, etc.

CL-USER> (first '(a b c))
A
CL-USER> (second '(a b c))
B
CL-USER> (third '(a b c))
C

car and cdr: old-school flavor.

CL-USER> (cdr '((a b) c))
(C)
CL-USER> (car (cdr '(a b c)))
B

You can combine car and cdr:

CL-USER> (car (cdr '(a b c)))
B
CL-USER> (cadr '(a b c))
B
CL-USER> (caddr '(x y z w))
Z
CL-USER> (car (cdr (cdr '(x y z w))))
Z

Fun with cons:

CL-USER> (cons 'a '(b c))
(A B C)
CL-USER> (cons '(a b) '(c d))
((A B) C D)
CL-USER> (cons 'a (cons 'b (cons 'c NIL)))
(A B C)
CL-USER> (list 'a 'b 'c)
(A B C)
CL-USER> (append '(a b) '(c d))
(A B C D)
CL-USER>

cons, list, and append do not alter symbol values.

CL-USER> (setq x 'a L '(b c))
(B C)
CL-USER> (cons x L)
(A B C)
CL-USER> L
(B C)
CL-USER> (setq x 'a L '(b c))
(B C)
CL-USER> (setq L (cons x L))
(A B C)
CL-USER> L
(A B C)

Inserting an element at the end of a list:

CL-USER> (append '(a b) '(c))
(A B C)
CL-USER> (setq x 'c)
C
CL-USER> (append '(a b) (list x))
(A B C)
CL-USER> (length '(a b c))
3
CL-USER> (length '((a b) (c d)))
2

Reverse only reverses the order of the top list elements:

CL-USER> (reverse '(a b c))
(C B A)
CL-USER> (reverse '((a b) (c d)))
((C D) (A B))

alists and assoc

CL-USER> (setf apple '((ako fruit)
                       (color red)
                       (shape sphere)))
((AKO FRUIT) (COLOR RED) (SHAPE SPHERE))
CL-USER> (assoc 'color apple)
(COLOR RED)

three rules of evaluation

1. Symbols are replaced by their current bindings

CL-USER> (setq x 2)
2
CL-USER> (+ x x)
4

2. Lists are evaluated as function calls. 3. Everything else evaluates to itself.

It may not look particularly significant, but the above illustrates an important characteristic. You can write symbols rather than only reserved words and variables.

Generations of computer languages

Machine language -> assembly -> high-level languages -> very high-level languages -> symbolic languages

Functions

CL-USER> (defun addthree (x) (+ x 3))
ADDTHREE

In addthree, x is a formal parameter, meaning that x is in the function definition, rather than the function call.

CL-USER> (defun sum-average (x y)
           (setq sum (+ x y))
           (/ sum 2))
SUM-AVERAGE

sum is a non-formal parameter. non-formal parameters are free rather than bound. x and y are formal parameters, which are bound. free parameters are global, and bound parameters are local.

CL-USER> (sum-average 3 5)
4
CL-USER> sum
8
CL-USER> (sum-average 10 20)
15
CL-USER> sum
30

Notice that sum in the top level has its value changed. Use free symbols with great care. It is conventional to set off global parameters with asterisks, like *PS*.

CL-USER> (defun sum-ave-caller (sum x y)
           (sum-average x y) sum)
SUM-AVE-CALLER
CL-USER> (sum-ave-caller 0 10 20)
0
CL-USER> sum
30

Take a look at the above code carefully. It may be confusing but the code listed below is equivalent.

CL-USER> (defun sum-ave-caller (sum_name_substitute x y)
           (sum-average x y) sum_name_substitute)
SUM-AVE-CALLER
CL-USER> (sum-ave-caller 0 10 20)
0
CL-USER> sum
30
CL-USER> sum_name_substitute
ERROR

Theory

The discipline of artificial intelligence potentially provides answers to unsolved problems in neuroscience because AI must devise and test theories of how mind emerges from brains.

I hope you got the idea.

Computer Science:Artificial Intelligence

Contents