Many problems can be framed as search: there is an initial state, operations that lead from one state to another, and a goal. Since exploring every alternative is impossible, one uses heuristics: rules of thumb or functions that estimate which paths look promising. For Newell and Simon, such guided search was the essence of intelligence (Newell & Simon, 1976; Buckner, 2024, p. 51), and their Logic Theorist used it to prove theorems of Principia Mathematica (Newell & Simon, 1956). It is the technical core of GOFAI.
Game trees. In a game, the root of the tree is the current position and each branch a possible move. The program looks a few moves ahead, scores the final positions with an evaluation function, and propagates the scores upward with minimax: it maximizes on its own turns and assumes the opponent will minimize on theirs (M. Mitchell, 2019, ch. 9). Alpha–beta pruning discards branches that can no longer change the decision; it was essential to Samuel's checkers program and to Deep Blue (M. Mitchell, 2019, ch. 9, n. 10).
Combinatorial explosion. Checkers has about six or seven moves per position and games of about fifty moves: a computer examining a trillion positions per second would need more than 10¹⁹ years to cover the tree (M. Mitchell, 2019, ch. 9). Deep Blue won at chess through refined brute force: more than 200 million moves per second and hand-written heuristics such as "control the center" (Buckner, 2024, p. 51). In Go, with about 300 possible moves per turn, that was not enough (Buckner, 2024, p. 52).
Search with learned intuition. AlphaGo combined Monte Carlo tree search (simulating many random games from the position and counting wins) with neural networks that suggest moves and evaluate positions (M. Mitchell, 2019, ch. 9; Silver et al., 2016). Without the search, its networks still played at grandmaster level (Buckner, 2024, pp. 52–53).
A philosophical angle. Where does intelligence lie: in searching a lot, or in knowing what not to search? Buckner (2024) objects that AlphaGo's search is "classical" and innate, not learned, and only works in well-defined spaces (2024, p. 230). The debate returns with the test-time compute of reasoning models: spending more computation on thinking before answering.