6. Search: Games, Minimax, and Alpha-Beta

The paragraph discusses the early skepticism about computers playing chess expressed by philosopher Hubert Dreyfus in 1963. Despite losing to the Greenblatt chess machine, Dreyfus' point was that computers couldn't play chess like humans. This was further highlighted by a bet between David Levy and John McCarthy, where McCarthy conceded that computers wouldn't beat the world champion within 10 years by playing like humans. However, IBM's Deep Blue defeated the world champion in 1997, sparking a discussion on different types of intelligence and the ways computers might play chess.

This section explores various methods for programming computers to play chess. It starts with the idea of machines describing the board like humans, considering strategy and tactics. However, this approach is acknowledged as unknown and thus not utilized. The paragraph then discusses the use of if-then rules, which, despite their simplicity, fail to produce strong chess programs. The narrative suggests looking at other methods, hinting at more complex strategies.

The paragraph delves into the strategy of looking ahead and evaluating potential moves in chess. It introduces the concept of static value, which assesses the board's current state without considering future moves. The discussion then shifts to the use of linear scoring polynomials to form a static value, which is a simplified method of evaluating board positions. The section concludes with the idea that a more comprehensive approach might be necessary for stronger play.

This part of the script introduces the concept of a game tree in chess, focusing on the branching factor and the depth of the tree. It explains how the number of possible board positions grows exponentially with each move, leading to an enormous tree of possibilities. The discussion uses mathematical calculations to illustrate the impracticality of evaluating every possible move in a game of chess, setting the stage for more efficient algorithms.

The speaker humorously dismisses the idea of using the British Museum algorithm, which would involve evaluating every possible move in a game of chess, as impractical. The paragraph uses cosmic-scale comparisons to emphasize the sheer number of calculations required, suggesting that even with cloud computing, such an approach is unfeasible due to the astronomical number of operations needed.

The paragraph introduces the minimax algorithm with alpha-beta pruning, a technique used to efficiently find the optimal move in games like chess. It explains how the algorithm works by alternating between a maximizing player and a minimizing player, and how alpha-beta pruning can significantly reduce the number of necessary calculations by eliminating branches of the game tree that don't need to be explored.

This section discusses the concept of progressive deepening, where the search algorithm starts with a shallow search and progressively goes deeper as time allows. It also touches upon the idea of uneven tree development, where certain parts of the tree are explored more deeply based on their potential impact on the game. The paragraph highlights the importance of having an answer ready at any given time, aligning with the anytime algorithm concept.

The final paragraph contrasts the brute force approach of Deep Blue, which used massive computational power and advanced algorithms, with the more sophisticated and pattern-recognition-based strategies used by human chess players. It questions whether Deep Blue's approach is a model of human intelligence or a different form of intelligence altogether, suggesting that while it demonstrates a capability to play chess at a high level, it does so through raw computational power rather than the nuanced understanding humans possess.