Search Versus Knowledge in Game-Playing Programs Revisited

Perfect knowledge about a domain renders search unnecessary and, likewise, exhaustive search obvi-ates heuristic knowledge. In practise, a tradeoff is found somewhere in the middle, since neither ex-treme is feasible for interesting domains. During the last two decades, the focus for increas-ing the performance of two-player game-playing programs has been on enhanced search, usually by faster hardware and/or more efficient algorithms. This paper revisits the issue of the relative advan-tages of improved search and knowledge. It in-troduces a revised search-knowledge tradeoff graph that is supported by experimental evidence for three different games (chess, Othello and checkers) using a new metric: the “noisy oracle”. Previously published results in chess seem to con-tradict our model, postulating a linear increase in program strength with increasing search depth. We show that these results are misleading, and are due to properties of chess and chess-playing programs, not to the search-knowledge tradeoff.