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:
value(node) = score(node), if node is a terminal node max_{s} value(s), (over successors s), if node is a max-node (A-node). min_{s} 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
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)findMin is similarly modified.
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
MacHack:
Chess 4.5 history:
Type-A vs. Type-B:
Chess 4.5 technical details:
Challenges issued to chess programmers:
An overview:
More about Belle:
Finally, an interesting study using Belle:
Recall type-A vs. type-B:
Deep Blue:
More about Deep Blue's internals:
Postscript:
About Chinook: [Scha1992].
Chinook technical details:
The more important result about Chinook: [Scha2007].
Here are two interesting questions:
Exercise: What do you think?
On the first question:
On the second question:
Finally, a humorous comment:
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
[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.