On AO*, Proof Number Search and Minimax Search

Alpha-Beta [Knuth and Moore, 1975] style depthfirst We discuss the interconnections between AO*, adversarial search can also be used for this goal, but its unsatisfying game-searching algorithms, e.g., proof practical performance pushed researchers to devise search number search and minimax search. The former algorithms specialized for solving. Proof number search was developed in the context of a general AND/OR (PNS) [Allis, 1994] was developed of such. Together with graph model, while the latter were mostly presented other game-specific advancements, PNS and its variant [Nagai, in game-trees which are sometimes modeled using 2002] have been used for successfully solving a number AND/OR trees. It is thus worth investigating to of games, e.g., Gomoku [Allis, 1994], checkers [Schaeffer et what extent these algorithms are related and how al., 2007].