Transcript Artificial Intelligence - University of St Andrews

Artificial Intelligence
Game Playing:
Checkers
Ian Gent
[email protected]
Artificial Intelligence
The Story of the
World’s Best
Draughts Player
1.
2.
3.
4.
History
Search in Checkers
Endgame Databases
Chinook
A Checkered History
 Arthur Samuel, 1959
 Learning algorithm used to build computer checkers player
 Beat a ‘master’
 Patrick Prosser, 1970s
 Undergraduate project
 Probably state of the art at that time
 Not developed further
 Jonathan Schaeffer, 1990s
 Chinook is the World Man-Machine champion
 Possibly the best player there has ever been of any kind
3
Further Reading
 J Schaeffer
 One Jump Ahead
 Springer, 1997
 A popular account of the history of Chinook
 Little technical detail
 J Schaeffer, J Culberson, N Treloar, B Knight, P Lu,
D Szafron
 A world championship caliber checkers program
 Artificial Intelligence, Vol 53, pages 273-289, 1992
4
Didn’t Samuel solve
Checkers?
 Samuel’s program’s opponent made an appalling
move…
5
Prehistory of Chinook
 Joe Culberson:
 What is the real size of the search tree in Checkers?
 Not the naïve estimate of 1040
 Jonathan Schaeffer took up the challenge
 Project began June 1989
 Goals were to beat Marion Tinsley
 and solve the game completely
6
History of Chinook
 Tournament August 1990
 US National Open, 2nd to Marion Tinsley
 Gained right to challenge Tinsley for World Title
 Political shenanigans
 Establishment did not want machine to be champion
 Tinsley resigned championship to be able to play Chinook
 fudge was “World Man Machine Championship”
 Match vs Tinsley, August 1992
 Lost to Tinsley, won 2, lost 4, drawn 33
7
History of Chinook
 World Man Machine Championship, August 1994
 vs Tinsley, drew 6, won 0, lost 0
 won title by forfeit when Tinsley fell ill -- died 1995
 World Man Machine Championship, 1995
 vs Don Lafferty, won 1, lost 0, drew 31
 Play it on the Web today!
 http://www.cs.ualberta.ca/~chinook/play.html
8
Artificial Intelligence
The Story of the
World’s Best
Draughts Player
1.
2.
3.
4.
History
Search in Checkers
Endgame Databases
Chinook
Search in Checkers
 What is the search tree like in Checkers?
 It is possible to get Zugzwang -- every move loses
 Fine line between win and draw
 e.g. textbook example with 40 critical moves required
 Captures are forced, reducing branching rate
 about 8 when no captures, about 1.25 when captures
 Endgame databases heavily used
 Chinook can use the endgame database at the root
10
Search in Checkers
 Search early in the game involves all of …




opening
middlegame
endgame
endgame database
 All of these factors make search different from chess
11
Artificial Intelligence
The Story of the
World’s Best
Draughts Player
1.
2.
3.
4.
History
Search in Checkers
Endgame Databases
Chinook
Endgame Databases
 Endgames can be 100 moves long in checkers
 branching rate of 2 gives 2100 = 1030 positions.
 But there is a trick when few pieces left
 first used by Ken Thompson in Chess
 (Ken Thompson wrote first Unix, won Turing award)
 Calculate the true optimal move for every position
 e.g. 406 x 109 eight piece positions, 4x1011<< 1030
 Best version of Chinook used 8 piece databases
 web version just uses 6 piece
13
How to calculate Endgame DB’s
 0. Duplicate every position, for W/B to move
 1. Try every possible position of the pieces
 Mark as Win/0 if W has won in this position
 Mark as Loss/0 if W has lost in this position
 Leave other positions unmarked
 2. Iterate until no new positions are marked
 2a) Try every unmarked position of the pieces
 If W has move to Win/n, mark as Win/n+1
 If every W move is to Loss/n, mark as Loss/n+1
Ian Gen
Of cours
might ha
to Loss/1
Loss/5.
case n =
14
Calculating Endgame Databases
 When this process has finished
 We know the number of moves to win for every position
 where either B or W can force win
 Therefore every other position must be drawn
 so the following is valid
 3. Mark all unmarked positions as Drawn
 We can calculate optimal winning moves
 In Win/n position, best move for W is to any Win/n-1
 in Drawn, best move for W is to any Drawn position,
 In Loss/n position, best move is to Loss/n-1
15
Artificial Intelligence
The Story of the
World’s Best
Draughts Player
1.
2.
3.
4.
History
Search in Checkers
Endgame Databases
Chinook: Putting it all together
Putting it all together
 Standard techniques
 a-b search
 endgame databases
 variable search depth
 e.g. pursue positions with material deficit less deeply
 An AntiBook
 not a standard opening book known to opponents
 a book of disallowed moves, encouraging novelty
17
Static Evaluation function
 Game divided into 5 phases





opening
middlegame
early endgame
late endgame
endgame database
 Different evaluation function at each stage
 Search involves all phases early in the game
 deal with ‘blemish effect’ by rescaling each phase
• I.e. problem that score jumps as move from one phase to next
18
Static Evaluation function
 Game divided into 5 phases





opening
middlegame
early endgame
late endgame
endgame database
 Different evaluation function …
 Search involves all phases …
22 parameters
22 parameters
22 parameters
22 parameters
perfect info.
88 parameters
 deal with ‘blemish effect’ by rescaling ...scaling factors
 Total is 88 parameters plus scaling factors!
19
The Weigh-in
Tinsley
Chinook
Team
Marion Tinsley
CPU
Massivel parallel
Schaeffer et al,
SGI computer
16x parallel
Positions/sec
2-3
100,000-500,000
Knowledge
50,000+ patterns
Technique
knowledge based
< 100 patterns
1011 database
Search based
20
The Present and the Future
 Present
 Chinook is best player in the
world following Tinsley
 Never beat Tinsley in a match,
not near solving Checkers
 Deep Blue beat Kasparov, but
has been dismantled
 Harder games
 Go: huge branching rate
(computers terrible)
 Bridge: uncertainty
 Civilization: worst of both the
above!
21