In the popular culture of games, chess has dominated the imagination as
the pinnacle of human mental challenge.
For which reason it has attracted the attention of computer
scientists intent on building programs to defeat the best
human player.
A preview :
Our presentation will pull together material from various sources - see the
references below. But most of it will come from
[Frey1983],
[Newb1997],
[Russ2003].
Note:
The early history of chess machines:
Claude Shannon (1916-2001):
Exercise:
Look up the ultimate machine on youtube.
Shannon's game tree:
Let's look a little deeper into game trees:
The minimax formulation:
Overview
Early history
→
Most important contribution: an evaluation function.
→
square-root of # possible moves.
→
1 point if another piece can defend it, 1.5 if two others can.
→
Lost to a (weak) human player in 1951.
Chaude Shannon and game trees
→
How can you encode symbols so that they can be transmitted over noisy media?
→
The rest of the game only depends on the current position.
→
Roughly, a high evaluation for player A is a low one for player B.
→
The same evaluation function works for both players (with opposite meaning).
→
It does not score "how you got there".
→
Will maximize score.
→
Will minimize score.
→
e.g., min (24, 32) = 24
→
The value at the upper A node is 24 (best move for A).
value(node) = score(node), if node is a terminal node
maxs value(s), (over successors s), if node is a max-node (A-node).
mins value(s), if node is a min-node (B-node).
Algorithm: findMax (state)
Input: the current "board" or state
1. if state is terminal
2. return value (state)
3. endif
// Search recursively among child states
4. S = generate successor states
5. maxValue = -∞
6. for s ε S
7. v = findMin (s)
8. if v > maxValue
9. maxValue = v
10. endif
11. endfor
12. return maxValue
Algorithm: findMin (state)
Input: the current "board" or state
1. if state is terminal
2. return value (state)
3. endif
// Search recursively among child states
4. S = generate successor states
5. minValue = -∞
6. for s ε S
7. v = findMax (s)
8. if v > minValue
9. minValue = v
10. endif
11. endfor
12. return minValue
→
We need to record the move that achieved the best value.
Algorithm: findMax (state)
Input: the current "board" or state
1. if state is terminal
2. return (null, value(state))
3. endif
// Search recursively among child states
4. M = generate all possible moves
5. maxValue = -∞
6. for m ε M
7. s = state (m) // s is the state you get when applying move m
8. (m',v) = findMin (s) // m' is the best min move
9. if v > maxValue
10. maxValue = v
11. bestMove = m
12. endif
13. endfor
14. return (bestMove, maxValue)
1. (m, v) = findMax (s) 2. play move m
Exercise:
Apply the minimax algorithm to this game tree:
Do all subtrees need to be explored?
Algorithm: findMax (state, α, β) Input: the current "board" or state 1. if state is terminal 2. return (null, value(state)) 3. endif // Search recursively among child states 4. M = generate all possible moves 5. maxValue = -∞ 6. for m ε M 7. s = state (m) // s is the state you get when applying move m 8. (m',v) = findMin (s, α, β) // m' is the best min move 9. if v > maxValue 10. maxValue = v 11. bestMove = m 12. endif // If we've exceeded some earlier B's min-value, there's no point searching further in this A-node's children. 13. if maxValue ≥ β 14. return (bestMove, maxValue) 15. endif // Update this node's best value so far. 16. if maxValue > α 17. α = maxValue 18. endif 19. endfor 20. return (bestMove, maxValue)
Algorithm: findMin (state, α, β) Input: the current "board" or state 1. if state is terminal 2. return (null, value(state)) 3. endif // Search recursively among child states 4. M = generate all possible moves 5. minValue = ∞ 6. for m ε M 7. s = state (m) // s is the state you get when applying move m 8. (m',v) = findMax (s, α, β) // m' is the best max move 9. if v > maxValue 10. minValue = v 11. bestMove = m 12. endif // If we've exceeded some earlier A's max-value, there's no point searching further in this B-node's children. 13. if minValue ≤ α 14. return (bestMove, minValue) 15. endif // Update this node's best value so far. 16. if minValue < β 17. β = minValue 18. endif 19. endfor 20. return (bestMove, minValue)
Exercise: Use the example in the previous exercise and work out the steps in the α-β algorithm.
→
Many type-B programs order child nodes according to value.
Exercise: Modify the Minimax code to implement α-β pruning and test it out with tic-tac-toe.
Iterative deepening:
Algorithm: Iterative-Deepening (search, maxTime) Input: a search algorithm, and a time limit. 1. d = 1 2. while currentTime < maxTime 3. m = search (d) // Apply search algorithm, e.g., α-β, to depth d 4. d = d + 1 5. endwhile 6. return m // Best move found so far
Algorithm: Iterative-Deepening (search, maxTime) Input: a search algorithm, and a time limit. 1. d = 1 2. while currentTime < maxTime 3. m = α-β-search (d) // Apply search algorithm, e.g., α-β, to depth d 4. re-order children of root. 5. d = d + 1 6. endwhile 7. return m // Best move found so far
The chess tree:
Back to Shannon:
Newell, Shaw and Simon:
MIT vs. ITEP
The first decade: Kotok and Kaissa
→
Did not perform well at all.
→
ITEP won 3-1.
→
Type-A vs. Type-B.
MacHack:
Chess 4.5 history:
Type-A vs. Type-B:
Chess 4.5 technical details:
The second decade: MacHack and Chess 4.5
→
Stored opening moves.
→
Essentially a hash table storing previously-scored positions.
→
Received a chess rating of 1510 (modest).
→
Achieved a rating of 2271, highest ever for a program in 1978.
→
Better to search only promising moves in greater depth.
→
Simple minimax for interior nodes.
→
But this can be a much simpler evaluation (because it
doesn't affect quality, only speed).
→
All possible moves for that piece.
→
e.g., remove all "friendly" positions from bishop-bitboard.
→
Will lead to a low evaluation score.
→
Stores only which-pieces-are-active, for quick material balance computation (by lookup).
→
To take pawn structure as input and output an evaluation score.
Challenges issued to chess programmers:
The Levy challenge and Fredkin Prize
→
Won all his games.
→
He won the match but lost one game and drew the other.
An overview:
More about Belle:
Finally, an interesting study using Belle:
Belle
→
Hardware slowed the software.
→
called pseudo-legal moves (without taking "king check" into account).
→
e.g., in Belle, all possible moves for piece are detected in a single cycle.
→
Similar in architecture to the move-generator, but to evaluate a position in parallel.
→
Approx. an increase in 250 points for every additional level of depth.
Recall type-A vs. type-B:
Deep Blue:
More about Deep Blue's internals:
Postscript:
Deep Blue
→
200 million or more positions per move.
→
An average of 126 million positions per second in practice.
→
"If a grandmaster made this move, it must be good".
→
When to load-balance, when to communicate between processors etc.
About Chinook:
[Scha1992].
Chinook technical details:
The more important result about Chinook:
[Scha2007].
Checkers and Chinook
→
Two of them to Chinook.
→
Many cases of quiescent search.
→
8,000,000 such pre-stored positions.
→
That Chinook could do no worse than draw against anyone.
→
Using symmetry arguments.
Here are two interesting questions:
Exercise:
What do you think?
On the first question:
On the second question:
Finally, a humorous comment:
What does it all mean?
→
Even seemingly poor moves need to be explored at sufficient depth.
→
It would be boring, like tic-tac-toe.
→
One is in awe of the effort needed to become a grandmaster.
→
e.g., pattern recognition, NLP.
Chess is the Drosophila of artificial
intelligence. However, computer chess has
developed much as genetics might have if
the geneticists had concentrated their efforts
starting in 1910 on breeding racing
Drosophila. We would have some science,
but mainly we would have very fast fruit
flies.
-- John McCarthy
References and further reading
[WP-1]
Wikipedia entry on chess programs.
[WP-1]
Computer Museum website on chess.
[Camp1999]
M.Campbell. Knowledge discovery in Deep Blue.
Comm. ACM, 42:11, 1999, pp.65-67.
[Camp2002]
M.Campbell, A.J.Hoane and F-H.Hsu.
Deep Blue. Artificial Intelligence, Vol.134,
2002, pp.57-83.
[Frey1983]
P.W.Frey (editor),
Chess Skill in Man and Machine,
Springer, 1983.
[Hsu1999]
F-H.Hsu. IBM's Deep Blue chess grandmaster chips.
IEEE Micro, March-April, 1999, pp.70-81.
[Hsu2002]
F-H.Hsu. Behind Deep Blue,
Princeton University Press, 2002.
[Newb1997]
M.Newborn. Kasparov vs. Deep Blue: Computer
Chess Comes of Age, Springer, 1997.
[Russ2003]
S.Russell and P.Norvig.
Artificial Intelligence: A Modern Approach (2nd Ed),
Prentice-Hall, 2003.
[Scha1992]
J.Schaeffer, J.Culberson, N.Treloar, B.Knight, P.Lu and D.Szafron.
A World Championship Caliber Checkers Program.
Artificial Intelligence, Vol.53, No.2-3, 1992, pp.273-290.
[Scha2007]
J.Schaeffer, N.Burch, Y.Bjornsson, A.Kishimoto, M.Muller,
R.Lake, P.Lu and S.Sutphen.
Checkers is solved.
Science, Vol.317, Sept 2007, pp.1518-22.