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

The paragraph discusses the early skepticism about computers playing chess, exemplified by Hubert Dreyfus's 1963 paper. Despite his assertion that computers couldn't play chess, Dreyfus lost to a chess machine, prompting a rebuttal. The narrative then shifts to the 1968 bet between David Levy and John McCarthy on AI's potential in chess, which McCarthy conceded in 1973. However, IBM's Deep Blue's victory over the world chess champion in 1997 contradicted McCarthy's expectations, marking a significant milestone in AI. The paragraph concludes by setting the stage for a discussion on game intelligence and the various methods to program a computer to play chess, hinting at the complexity and the evolution of AI in gaming.

This section delves into potential approaches for programming a computer to play chess. It starts by considering human-like strategic thinking, which remains an unsolved challenge. The paragraph then explores simpler methods like rule-based moves and lookahead evaluation, which involves assessing future board positions. The discussion introduces the concept of 'static value'评估, a function that assigns a numerical value to the board's current state without considering future moves. It explains how a linear scoring polynomial is often used for this evaluation, although it's acknowledged that more sophisticated methods might not require numerical rankings.

The paragraph introduces the concept of a game tree in chess, which represents all possible sequences of moves. It defines 'branching factor' as the average number of choices at each level of the tree and 'depth' as the number of moves into the future. It calculates the number of terminal nodes using these parameters and discusses the impracticality of evaluating every possible game outcome, known as the British Museum algorithm, due to the enormous number of leaf nodes in a full chess game tree. The speaker humorously consults the audience for cosmic-scale calculations to illustrate the point, concluding that such an exhaustive search is infeasible even with vast computational resources.

The discussion turns to the minimax algorithm, a technique for minimizing the maximum possible loss in zero-sum games like chess. It describes how the algorithm works by alternating between a maximizing player and a minimizing player to evaluate the best move. The paragraph uses a simplified game tree to illustrate the algorithm's process, where the values at the bottom of the tree are used to determine the best move at the top. The minimax algorithm is highlighted as a foundational approach in AI for decision-making in games.

This section introduces the alpha-beta pruning technique, an optimization of the minimax algorithm that reduces the number of nodes evaluated in the search tree. The speaker explains how alpha-beta works by using two parameters, alpha and beta, to eliminate branches that cannot possibly influence the final decision. The paragraph provides a detailed example of how alpha-beta can prune the search space, thereby saving computational resources without affecting the outcome. The concept of 'deep cut off' is also introduced, which further enhances the efficiency of the search process.

The speaker demonstrates the application of the alpha-beta algorithm in a more complex game tree, highlighting how it can prune even more branches as the tree's depth and complexity increase. The paragraph emphasizes the significant computational savings achieved through alpha-beta, which is crucial for real-time decision-making in games. It also touches on the concept of move generation and how alpha-beta can reduce the number of moves that need to be considered, further enhancing efficiency.

The paragraph introduces progressive deepening, a technique where the search algorithm starts with a shallow search and gradually increases the depth, ensuring that a move is always available within a time constraint. It discusses the practical implications of varying branching factors and how progressive deepening provides a reliable method to have a valid move ready at any given time. The concept is illustrated with a binary game tree, and the speaker explains the mathematical rationale behind the insurance policy of having moves ready at different tree levels.

This section discusses how IBM's Deep Blue, which defeated world chess champion Garry Kasparov, utilized a combination of minimax, alpha-beta, and progressive deepening. It also mentions additional strategies employed by Deep Blue, such as parallel computing, an opening book, and special-purpose algorithms for the endgame. The paragraph emphasizes the importance of uneven tree development, where certain dynamic situations are explored more deeply, providing a more accurate assessment of the best move.

The final paragraph contrasts the raw computational power of AI like Deep Blue with the sophisticated pattern recognition and chess knowledge that human players use. It questions whether the AI's approach is a model of human intelligence or a different form of intelligence altogether. The speaker suggests that while AI can exhibit intelligence in gaming, it may not mirror the cognitive processes of human experts. The paragraph concludes the discussion by acknowledging the importance of understanding different forms of intelligence and their implications.