Transcript powerpoint - School of Computer Science

G5AIAI
Introduction to Artificial Intelligence
Graham Kendall
History
G5AIAI 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
G5AIAI History
Why do we need AI
anyway?
G5AIAI 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
G5AIAI 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)
G5AIAI History
Combinatorial Explosion - Towers of Hanoi
G5AIAI History
Combinatorial Explosion - Towers of Hanoi
G5AIAI History
Combinatorial Explosion - Towers of Hanoi
G5AIAI History
Combinatorial Explosion - Towers of Hanoi
G5AIAI History
Combinatorial Explosion - Towers of Hanoi
G5AIAI History
Combinatorial Explosion - Towers of Hanoi
G5AIAI History
Combinatorial Explosion - Towers of Hanoi
G5AIAI History
Combinatorial Explosion - Towers of Hanoi
G5AIAI 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?
G5AIAI 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!!!!
G5AIAI 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
G5AIAI 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
G5AIAI 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
G5AIAI History
Alan Turing
• Founder of computer
science, mathematician,
philosopher and
code breaker
G5AIAI History
Alan Turing
1939-40
the Bombe,
machine
for Enigma
•• 1912
(23 Devises
June): Birth,
Paddington,
London
decryption
• 1931-34: Undergraduate at King's College,
• Cambridge
1947-48: Papers
on programming, neural nets, and
University
prospects for artificial intelligence
• 1935: Elected fellow of King's College, Cambridge
• 1948: Manchester University
• 1936: The Turing machine: On Computable
• Numbers...
1950: Philosophical
Submittedpaper on machine intelligence:
the Turing Test
• 1936-38: At Princeton University. Ph.D. Papers in
• logic,
1954 (7
June):number
Death by
cyanide poisoning,
algebra,
theory
Wilmslow, Cheshire
• 1938-39: Return to Cambridge. Introduced to
German Enigma cipher problem
G5AIAI History
The Turing Test
• Proposed by Alan Turing in 1950
• Suggested as a way of saying when we
could consider computers to be
intelligent
• You need to read and understand The
Turing Test
G5AIAI History
The Chinese Room
• If the Turing Test was passed Turing
would conclude that the machine was
intelligent
• In 1980 John Searle devised a thought
experiment which he called the Chinese
Room (Searle, 1980)
– Searle, J.R. 1980. Minds, brains and programs. Behavioural
and Brain Sciences, 3: 417-457, 1980
G5AIAI History
The Chinese Room
• You need to read and understand the Chinese
Room
• You need to be able to have an opinion about
The Turing Test and Chinese Room
G5AIAI History
Landmarks in AI
 Physical Symbol System Hypothesis
 ELIZA (A Therapist)
 MYCIN (First Expert System)
 Means End Analysis (Exploits Forward and
Backwards Chaining)
G5AIAI History
Summary
 Understand what is meant by combinatorial
explosion (esp. wrt TSP).
 The Turing Test (Read the paper)
 The Chinese Room (Read the paper)
 Be able to recognise the relationship between The
Turing Test and The Chinese Room
 Landmarks in AI History
 Read Chapter 1 of AIMA
G5AIAI History