Transcript History of AI - School of Computer Science

G5BAIM
Artificial Intelligence Methods
Graham Kendall
History
G5BAIM History
Predictions
• “Within 10 years a computer will be a
chess champion”
– Herbert Simon, 1958
• Conversion from Russian to English,
when presented with
– “The spirit is willing but the flesh is weak” produced
– “The vodka is good but the meat is rotten”
• National Research Council, 1957
G5BAIM History
The Travelling Salesman Problem
• A salesperson has to visit a number of cities
• (S)He can start at any city and must finish at
that same city
• The salesperson must visit each city only
once
• The number of possible routes is (n!)/2
G5BAIM History
Combinatorial Explosion
Travelling Salesman Problem
Routes
2000000
1500000
1000000
500000
0
1
2
3
4
5
6
Cities
7
8
9
10
G5BAIM History
Combinatorial Explosion
Cities Routes
1
1
2
1
3
3
4
12
5
60
6
360
7
2520
8
20160
9
181440
10 1814400
11 19958400
G5BAIM History
Combinatorial Explosion
A 10 city TSP has 181,000 possible solutions
A 20 city TSP has 10,000,000,000,000,000
possible solutions
A 50 City TSP has
100,000,000,000,000,000,000,000,000,000,00
0,000,000,000,000,000,000,000,000,000,000
possible solutions
There are 1,000,000,000,000,000,000,000
litres of water on the planet
Mchalewicz, Z, Evolutionary Algorithms for Constrained Optimization Problems, CEC 2000 (Tutorial)
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
• How many moves does it take to move four
rings?
• You might like to try writing a towers of
hanoi program (and you may well have to in
one of your courses!)
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
• If you are interested in an algorithm here is
a very simple one
• Assume the pegs are arranged in a circle
• 1. Do the following until 1.2 cannot be done
– 1.1 Move the smallest ring to the peg residing next to it,
in clockwise order
– 1.2 Make the only legal move that does not involve the
smallest ring
• 2. Stop
•
P. Buneman and L.Levy (1980). The Towers of Hanoi Problem, Information Processing Letters, 10, 243-4
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
• A time analysis of the problem shows that
the lower bound for the number of moves is
2N-1
• Since N appears as the exponent we have an
exponential function
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
N
Pegs
2 -1
3
4
5
6
…
10
7
15
32
63
…
1023
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
• The original problem was stated that a
group of tibetan monks had to move 64 gold
rings which were placed on diamond pegs.
• When they finished this task the world
would end.
• Assume they could move one ring every
second (or more realistically every five
seconds).
• How long till the end of the world?
G5BAIM History
Combinatorial Explosion - Towers of Hanoi
• > 500,000 years!!!!! Or 3 Trillion years
• Using a computer we could do many more
moves than one second so go and try
implementing the 64 rings towers of hanoi
problem.
• If you are still alive at the end, try 1,000
rings!!!!
G5BAIM History
Combinatorial Explosion - Optimization
•
•
•
•
Optimize f(x1, x2,…, x100)
where f is complex and xi is 0 or 1
The size of the search space is 2100  1030
An exhaustive search is not an option
– At 1000 evaluations per second
– Start the algorithm at the time the universe was
created
– As of now we would have considered 1% of all
possible solutions
G5BAIM History
Combinatorial Explosion
1E+280
1E+266
1E+252
1E+238
1E+224
1E+210
1E+196
1E+182
1E+168
1E+154
1E+140
1E+126
1E+112
1E+98
1E+84
1E+70
1E+56
1E+42
1E+28
1E+14
1
5N
N^3
N^5
N^10
1.2^N
2^N
N^N
2
4
8
16
Microseconds
in a Day
32
64
128
256
512
1024 2048
Microseconds since
Big Bang
G5BAIM History
Combinatorial Explosion
Running on a computer capable of 1 million instructions/second
N2
N5
10
1/10,000
second
20
1/2500
second
50
1/400
second
100
1/100
second
200
1/25
second
1/10
second
3.2
seconds
5.2
minutes
2.8
hours
3.7
days
> 400
trillion
centuries
45 digit no.
of centuries
2N
1/1000
second
1
second
35.7
years
NN
2.8
hours
3.3
trillion
years
70 digit
no. of
centuries
185 digit
no. of
centuries
Ref : Harel, D. 2000. Computer Ltd. : What they really can’t do, Oxford University Press
445 digit
no. of
centuries
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
Top Left
=
Cognitive Science
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
Top Left
Bottom Left
=
=
Cognitive Science
The Turing Test
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
Top Left
Bottom Left
Top Right
=
=
=
Cognitive Science
The Turing Test
Logical Approach
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
Top Left
Bottom Left
Top Right
Bottom Right
=
=
=
=
Cognitive Science
The Turing Test
Logical Approach
Acting to achieve one’s goals
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
Top
=
Thought Processes and Reasoning
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
Top
=
Bottom =
Thought Processes and Reasoning
Behaviour
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
Top
=
Bottom =
Left
=
Thought Processes and Reasoning
Behaviour
Measure success against ourselves
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
Top
Bottom
Left
Right
=
=
=
=
Thought Processes and Reasoning
Behaviour
Measure success against ourselves
Measure against rationality
G5BAIM History
Definition of AI
Systems that think
like humans
Systems that think
rationally
Systems that act like Systems that act
humans
rationally
G5BAIM History
Not Examinable - but in notes
• Turing Test
• Chinese Room
• Physical Symbol System Hypothesis
• ELIZA
• MYCIN
• Forward/Backward Chaining
• Means End Analysis
G5BAIM
Artificial Intelligence Methods
Graham Kendall
End of History