Abstract
Progressive Pruning (PP) is employed in the Monte-Carlo Go-playing program Indigo. For each candidate move, PP launches random games starting with this move. The goal of PP is: (1) to gather statistics on moves, and (2) to prune moves statistically inferior to the best one [7]. This papers yields two new pruning techniques: Miai Pruning (MP) and Set Pruning (SP). In MP the second move of the random games is selected at random among the set of candidate moves. SP consists in gathering statistics about two sets of moves, good and bad, and it prunes the latter when statistically inferior to the former. Both enhancements clearly speed up the process of selecting a move on 9×9 boards, and MP improves slightly the playing level. Scaling up MP to 19×19 boards results in a 30% speed-up enhancement and in a four-point improvement on average.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abramson, B.: Expected-outcome: a General Model of Static Evaluation. IEEE Transactions on PAMI 12, 182–193 (1990)
Billings, D., Davidson, A., Schaeffer, J., Szafron, D.: The Challenge of Poker. Artificial Intelligence 134, 201–240 (2002)
Bouzy, B.: Associating Domain-Dependent Knowledge and Monte-Carlo Approaches within a Go Program. Information Sciences 175, 247–257 (2005)
Bouzy, B.: Associating Shallow and Selective Global Tree Search with Monte-Carlo for 9×9 Go. In: van den Herik, H.J., Björnsson, Y., Netanyahu, N.S. (eds.) CG 2004. LNCS, vol. 3846, pp. 67–80. Springer, Heidelberg (2006)
Bouzy, B.: Indigo Home Page (2005), www.math-info.univ-paris5.fr/~bouzy/INDIGO.html
Bouzy, B., Cazenave, T.: Computer Go: an AI-oriented Survey. Artificial Intelligence 132, 39–103 (2001)
Bouzy, B., Helmstetter, B.: Monte-Carlo Go Developments. In: van den Herik, H.J., Iida, H., Heinz, E.A. (eds.) 10th Advances in Computer Games (ACG10), Many Games, Many Challenges, pp. 159–174. Kluwer Academic Publishers, Boston (2004)
Brügmann, B.: Monte-Carlo Go (1993), www.joy.ne.jp/welcome/igs/Go/computer/-mcgo.tex.Z
Coulom, R.: CrazyStone Home Page (2005), remi.coulom.free.fr/CrazyStone/
Fotland, D.: Go Intellect Wins 19x19 Go Tournament. ICGA Journal 27(3), 169–170 (2004)
Lieberum, J.: An Evaluation Function in the Game of Amazons. In: van den Herik, H.J., Iida, H., Heinz, E.A. (eds.) 10th Advances in Computer Games (ACG10), Many Games, Many Challenges, pp. 299–308. Kluwer Academic Publishers, Boston (2004)
Müller, M.: Computer Go. Artificial Intelligence 134, 145–179 (2002)
Müller, M.: Position Evaluation in Computer Go. ICGA Journal 25(4), 219–228 (2002)
Schaeffer, J., van den Herik, H.J.: Games, Computers, and Artificial Intelligence. Artificial Intelligence 134, 1–7 (2002)
Sheppard, B.: World-Championship-Caliber Scrabble. Artificial Intelligence 134, 241–275 (2002)
Sheppard, B.: Effective Control of Selective Simulation. ICGA Journal 27(2), 67–80 (2004)
Tesauro, G., Galperin, G.: On-line Policy Improvement using Monte-Carlo Search. In: Advances in Neural Information Processing Systems, pp. 1068–1074. MIT Press, Cambridge (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bouzy, B. (2006). Move-Pruning Techniques for Monte-Carlo Go. In: van den Herik, H.J., Hsu, SC., Hsu, Ts., Donkers, H.H.L.M.(. (eds) Advances in Computer Games. ACG 2005. Lecture Notes in Computer Science, vol 4250. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11922155_8
Download citation
DOI: https://doi.org/10.1007/11922155_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-48887-3
Online ISBN: 978-3-540-48889-7
eBook Packages: Computer ScienceComputer Science (R0)