Abstract
In complex games with a large branching factor such as Go, programs usually use highly selective search methods, heuristically expanding just a few plausible moves in each position. As in early Chess programs, these methods have shortcomings, they often neglect good moves or overlook a refutation. We propose a safe method to select the interesting moves using game definition functions. This method has multiple advantages over basic alphabeta search: it solves more problems, the answers it finds are always correct, it solves problems faster and with less nodes, and it is more simple to program than usual heuristic methods. The only small drawback is the requirement for an abstract analysis of the game. This could be avoided by keeping track of the intersections tested during the search, maybe with a loss of efficacy but with a gain in generality. We give examples and experimental results for the capture game, an important sub-game of the game of Go. The principles underlying the method are not specific to the capture game. The method can also be used with different search algorithms. This algorithm is important for every Go programmer, and is likely to interest other game programmers.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cazenave T.: Metaprogramming Forced Moves. Proceedings ECAI98 (ed. H. Prade), pp. 645–649. John Wiley & Sons Ltd., Chichester, England. ISBN 0-471-98431-0. 1998.
Cazenave T.: Generating Search Knowledge in a Class of Games. submitted. http://www.ai.univ-paris8.fr/~cazenave/papers.html. 2000.
Frank I.: Search and Planning under Incomplete Information: a Study using Bridge Card Play. PhD Thesis, Department of Artificial Intelligence, University of Edinburgh. 1996.
Kano Y.: Graded Go Problems For Beginners. Volume One. The Nihon Ki-in. ISBN 4-8182-0228-2 C2376. 1985.
Kano Y.: Graded Go Problems For Beginners. Volume Two. The Nihon Ki-in. ISBN 4-906574-47-5. 1985.
Kano Y.: Graded Go Problems For Beginners. Volume Three. The Nihon Ki-in. ISBN 4-8182-0230-4. 1987.
Marsland T. A., Björnsson Y.: From Minimax to Manhattan. Games in AI Research, pp. 5–17. Edited by H.J. van den Herik and H. Iida, Universiteit Maastricht. ISBN 90-621-6416-1. 2000.
Thomsen T.: Lambda-search in game trees — with application to go. CG 2000. This volume.
Willmott S., Richardson J. D. C., Bundy A., Levine J. M.: Applying Adversarial Techniques to Go. Journal of Theoretical Computer Science. 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cazenave, T. (2001). Abstract Proof Search. In: Marsland, T., Frank, I. (eds) Computers and Games. CG 2000. Lecture Notes in Computer Science, vol 2063. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45579-5_3
Download citation
DOI: https://doi.org/10.1007/3-540-45579-5_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43080-3
Online ISBN: 978-3-540-45579-0
eBook Packages: Springer Book Archive