History of Chess game:
- 1950: Programming a Computer for Playing Chess (Claude Shannon)
- 1951: First chess playing program (on paper) (Alan Turing)
- 1958: First computer program that can play a complete chess game
- 1981: Cray Blitz wins a tournament in Mississippi and achieves master rating
- 1989: Deep Thought loses 0-2 against World Champion Garry Kasparov
- 1996: Deep Blue wins a game against Kasparov, but loses match 2-4
- 1997: Upgraded Dee Blue wins 3.5-2.5 against Kasparov
- 2005: Hydra destroys GM Michael Adams 5.5-0.5
- 2006: World Champion Vladimir Kramnik looses 2-4 against Deep Fritz (PC
Complexity of a Chess game:
- 20 possible start moves, 20 possible replies, etc.
- 400 possible positions after 2 ply (half moves).
- 197 281 positions after 4 ply.
- 713 positions after 10 ply (5 White moves and 5 Black moves).
- Exponential explosion!
- Approximately 40 legal moves in a typical position.
- There exists about 10120 possible chess games .
Search Trees and Position Evaluation:
- Search trees (nodes are positions, edges are legal chess moves).
- Leaf nodes are end positions which needs to be evaluated (judged).
- A simple judger: Check mate? If not, count material.
- Nodes are marked with a numeric evaluation value.
The Basic Search Algorithm:
• Minimax: Assume that both White and Black plays the best
moves. We maximizes White’s score
• Perform a depth-first search and evaluate the leaf nodes
• Choose child node with highest value if it is White to move
• Choose child node with lowest value if it is Black to move
• Branching factor is 40 in a typical chess position
ply = 0
ply = 1
ply = 2
ply = 3
ply = 4
- The complexity of searching d ply ahead is O(b*b*…*b) = O(bd)
- With a branching factor (b) of 40 it is crucial to be able to prune the search tree .
Analyze the Best Move First:
- Even with alpha-beta pruning, if we always start with the worst move, we still get O(b*b*..*b) = O(bd).
- If we always start with the best move (also recursive) it can be shown that complexity is O(b*1*b*1*b*1…) = O(bd/2) = O(√bd).
- We can double the search depth without using more resources.
- Conclusion: It is very important to try to start with the strongest moves first .
- Killer-move heuristics is based on the assumption that a strong move which gave a large pruning of a sub tree, might also be a strong move in other nodes in the search tree.
- Therefore we start with the killer moves in order to maximize search tree pruning.
- Alpha-Beta cutoff: “The position is so good for White (or Black) that the opponent with best play will avoid the variation resulting in that position”.
- Zero-Move heuristics is based on the fact that in most positions it is an advantage to be the first player to move.
- Let the player (e.g. White) who has just made a move, play another move (two moves in a row), and perform a shallower (2-3 ply less) and therefore cheaper search from that position.
- If the shallower search gives a cutoff value (e.g. bad score for White), it means that most likely the search tree can be pruned at this position without performing a deeper search, since two moves in a row did not help.
- Very effective pruning technique!
- Cavecats: Check and endgames (where a player can be in “trekktvang” – every move worsens the position) .
- Same position will commonly occur from different move orders.
- All chess engines therefore has a transposition table (position cache).
- Implemented using a hash table with chess position as key.
- Doesn’t have to evaluate large sub trees over and over again.
- Chess engines typically uses half of available memory to hash table – proves how important it is.
Download chess game code in java: