Transcript Document

Thoughts on AI



Will computers ever be intelligent?
Really intelligent?
Tasks that previously were thought to require intelligence:










adding and subtracting
playing chess
driving a car
recognizing speech or handwriting
translating to a foreign language
proving mathematical theorems
What does it mean to say that a computer is intelligent?
Is that the same as being a person? What is a person?
Is a computer program a person?
Is a person a computer program?
Achieving “Intelligence”


How do AI program achieve “intelligent” behavior?
Currently, three main paradigms:



Symbolic knowledge representation and search
Neural Nets
Genetic Algorithms
Search in Artificial Intelligence

Represent your problem as a graph where nodes are
states and edges are operators that go between states





Define problem states (nodes)
Identify start and goal states
Define operators (edges)
Use DFS or BFS to find goal
Example: Missionaries and cannibals problem

states: (3,3,1)  3 missionaries, 3 cannibals, and 1 boat on
left side of river.
Operators: one or two people cross the river in the boat, so
that there isn’t a cannibal majority on either side.
Goal: get to the other side?
Moves?

(331)–(220)–(321)–(210)–(221)–(020)–(031)–(010)–(021)–(000)



DFS/BFS Resource Requirements

DFS:

Runtime?



O(n), n=number of nodes expanded
Space required?
O(d), d = depth of search

Can I cut off a search after 5 seconds?
BFS:

Runtime? O(n)

Space required?
O(breadth of tree) = O(bd), b=branching factor

Can I cut off a search after 5 seconds?
Staged DFS: do a DFS of depth 1, 2, 3, … until out of time

Runtime?
O(n)

Space required? O(d)
Game Playing

We could use DFS but…can’t search whole tree!


limit depth of search and use an evaluation function
We could use DFS but…how do we know which
move the opponent will choose?


minimax algorithm: assume the opponent does what
looks best.
i.e. at nodes where it is the human’s turn, pick the move
that looks best for human. Where computer’s turn, pick the
move that looks best for the computer
Mankalah



An ancient gamed called Kalah or Mankalah uses stones and pits: 6 to
a side and one on each end.
4 stones are initially placed in each side pit. None are in the end pits
(called Kalahs – a player’s kalah is on her right).
A move consists of picking up the stones in a pit and distributing
them, one at a time, in successive pits.


If the last stone is placed in your Kalah, you go again
If the last stone is placed in an empty pit on your side, you capture the
stones in that pit and the opposite one, on the opponent’s side of the
board. These are put into your Kalah.

The game ends when one player has no stones left; the other player
puts all the remaining stones on her side into her Kalah.
Whoever ends with more stones in her Kalah wins.

See the demo program on holmes at /home/hplantin/kalah.c

 Write a smart kalah playing program!
Mankalah minimax
int kalahboard::minimax(depth d):
//semi-pseudocode
if [human won] return –infinity;
if [machine won] return +infinity;
if (d==0) return evaluate();
if (whosemove==HUMAN)
best=+infinity;
for (move=first; move<=last; move++)
kalahboard b=*this;
//duplicate board
if (b.board[move]>0)
//is move legal?
b.makemove(move);
//make the move
v=b.minimax(d-1);
//find its value
if (v<best) best=v; //remember if best
else // similarly for MACHINE’s move
return best;