Lecture on Computers and Chess

Introduction

• In 1963, Hubert Dreyfus wrote a paper titled "Computers Can't Play Chess."
• Dreyfus lost to the MIT Greenblatt chess machine.
• David Levy bet John McCarthy in 1968 that no computer would beat the world champion in 10 years.
• McCarthy gave up after five years when it became clear computers couldn't play chess like humans.
• Deep Blue beat the world champion in 1997, demonstrating chess as a model for some kind of intelligence.

Understanding Computer Chess

• The lecture will cover designing a computer program to play chess and what Deep Blue adds beyond speed.

Approaches to Computer Chess

Approach 1: Human-like Board Description

• Involves analysis and strategy, but no current program can mimic this fully.

Approach 2: If-Then Rules

• Rules like "if possible, move Queen pawn forward by one."
• Works for checkers but ineffective for strong chess playing.

Approach 3: Look Ahead and Evaluate

• Looks ahead at possible moves and evaluates which board situations are best.
• Uses features of the board to produce a static value.

Approach 4: British Museum Algorithm

• Evaluates all possible moves, impractical due to the vast number of possibilities.

Approach 5: Practical Look Ahead

• Look as far ahead as possible and evaluate static values at leaf nodes.
• Invented by Claude Shannon and Alan Turing.

Minimax Algorithm

• Back up static values from the bottom of the tree to determine the best move.
• Example: Maximizing player chooses the path with the highest minimum value.

Alpha-Beta Pruning

• Enhances Minimax by cutting off parts of the search tree that won't affect the final decision.
• Involves parameters alpha (lower bound) and beta (upper bound).

Complex Example and Deep Cut-Off

• A deeper tree example to demonstrate alpha-beta pruning efficiency.
• "Deep cut off" occurs when parts of the tree can be ignored due to guaranteed better paths.

Progressive Deepening

• A strategy to ensure a move is always ready, regardless of depth reached.
• Calculates at each level; useful when branching factor is unpredictable.

Deep Blue's Additional Strategies

• Utilized parallel computing, opening books, and special endgame tactics.
• Did not rely on a fixed tree depth, allowing more dynamic tree development.

Human vs. Computer Chess Intelligence

• Deep Blue's approach is different from human intelligence.
• Human chess players rely on pattern recognition and accumulated knowledge.
• Chess masters are capable of memorizing legitimate chess positions but fail with random setups.

Conclusion

• Deep Blue's "bulldozer intelligence" is distinct from human intelligence but also important.
• The lecture concludes with preparation for a "celebration of learning" on Wednesday.