Photos  Personal  Links  Restaurants  Recipes  2020 Cruise 

How Computers Play Chess

Evaluation Functions

Search Techniques

Favorable Ideas

AI & Psychology

Evaluation Functions

• Material: 
• The number of pieces on each side, modified by a factor which encourages the side ahead to trade pieces ( not pawns ). 
• Pawns worth 1, Knights/Bishops worth 3, Rooks worth 5 and Queen worth 9.
• Position: 
• Counting the number of safe squares your pieces can attack. The more places they control, the better the position. 
• Recognize known draws ( king & two knights vs a king ).
• Tempo: 
• Gain tempo by making productive advances while opponent is not.
• Pawn Structure: 
• Doubled, isolated, backward and passed. 
• Expensive computation. Store scores of recently evaluated pawn structures in a hash table.
• King safety: 
• Deduct points if covering pawns are missing or if there is a hole in front of the king a pawn cannot cover. 
• Multiply the score by the material score to encourage player to trade pieces when his king is vulnerable but not when the opponent's is unsafe.
• Center Control: 
• Reward for posting pieces safely in center.
• King Attack: 
• Bonus for placing pieces near the opposing king.
• Special Bonuses: 
• Bonus for castling or a penalty for giving up castling rights. 
• Rewards for placing rooks on open and half-open files or the seventh rank 
• Penalty for king on the back rank with no air.

Search Techniques

• State-Space Search:
• Depth of eight appears to be "sweet spot" in terms of performance.
• The "branching factor" is about 35 for 2x10^12 leafe nodes.
• Negamax:
• Evaluate the board from the standpoint of the person who is moving.
• Aspiration Search: 
• Estimate the expected result and use an aspiration window which is a measure for the deviations we expect from the result. 
• Uses alpha-beta limits at the root of the tree. 
• Small improvement over Alpha-Beta.
• Transposition Tables 
• Hash table used to detect positions in different branches of the tree which are identical. 
• Can save up to a factor of four on tree size.
• Enhanced Transposition Cutoff 
• Look at all successor positions and see if they are in the transposition table. If such a position is found, no further search necessary. 
• Saves 20-25% in total tree size.
• Iterative Deepening 
• Increase depth if time allows. 
• Use transposition table to prevent searching deeper on useless leaves. 
• Use values returned to adjust aspiration search window.
• Quiescence Search 
• Reason: a position might be favorable in material, but what if your queen can be captured on the next move? 
• Check evasion 
• Capturing a piece that has just captured a piece 
• Promotion threats or promotion opportunities
• Killer Heuristic 
• A good move in one branch of a tree is also good at another branch at the same depth. 
• Maintain one or two killer moves at each ply that are searched first. 
• Improves move ordering. 
• Replace killer moves if better move is found.
• Null Move Heuristic 
• Make no move and see what happens. If there is no improvement, abandon search. 
• Fails to detect deep combinations. 
• Saves time.
• Dual Move Heuristic
• Make two moves in a row and see if there is an improvement.

---

Other Favorable Ideas

• Opening Books: 
• 15-20 initial moves are scripted in hash table. 
• Deep Blue had 18,000 possible opening combinations. 
• Psychological threat to opponent
• Endgame Databases 
• Special evaluation functions applied to known end-game positions. 
• Database of known end-game scenarios for five-piece end games.

Intelligence And Psychology

• Computers are not rattled by a human player's emotions. 
• Use of the Clock: 
• Deep Blue could take its full allotted time to make a move, or move quickly. 
• Forces response from human or bores him.
• No Short-Term Errors. Computers don't make tactical blunders with short-term consequences. It is not obvious to the human when a computer makes a mistake. 
• Computers have no creativity. They cannot gamble as humans might. 
• Know when to take a draw, even with advantage.
• Recognizing tendencies: 
• A computer can store previous games and try the opponent's "favorite" move first in game search. 
• Double-edged sword: Human can steer the computer into a familiar game, then change his strategy.