Note: [1] IBM Research, Ireland. Email: [email protected]. This research was performed while the author was affiliated with Department of Mathematical and Computing Sciences, Graduate School of Information Science and Engineering, Tokyo Institute of Technology.
Note: [2] Games and AI Group, Department of Knowledge Engineering, Faculty of Humanities and Sciences, Maastricht University, Maastricht, The Netherlands. Email: [email protected]
Note: [3] Department of Computing Science, University of Alberta, Edmonton, Canada. Email: [email protected]
Abstract: Solving games is a challenging and attractive task in the domain of Artificial Intelligence. Despite enormous progress, solving increasingly difficult games or game positions continues to pose hard technical challenges. Over the last twenty years, algorithms based on the concept of proof and disproof numbers have become dominating techniques for game solving. Prominent examples include solving the game of checkers to be a draw, and developing checkmate solvers for shogi, which can find mates that take over a thousand moves. This article provides an overview of the research on Proof-Number Search and its many variants and enhancements.
DOI: 10.3233/ICG-2012-35302
Journal: ICGA Journal, vol. 35, no. 3, pp. 131-156, 2012
