Hi, partly as a result of the discussion in the thread "Zen resignation positions", we wrote the following paper on the detection of semeai during MCTS: "On Semeai Detection in Monte-Carlo Go"
Abstract: A frequently mentioned limitation of Monte-Carlo Tree Search (MCTS) based Go programs is their inability to recognize and adequately handle capturing races, also known as semeai, especially when many of them appear simultaneously. This essentially stems from the fact that certain group status evaluations require deep lines of correct tactical play that somewhat oppose to the exploratory nature of MCTS. In this paper we provide a technique for heuristically detecting and analyzing semeai during the search process of a state-of-the-art MCTS implementation. We evaluate the strength of our approach on game positions that are known to be difficult to handle even by the strongest Go programs to date. Our results show a clear identification of semeai and thereby advocate our approach as a promising heuristic for the design of future MCTS simulation policies. You can download an author manuscript of the paper here: http://www.cs.uni-paderborn.de/fachgebiete/computer-engineering-group/people/schaefers.html Cheers, Lars On Tue, 2012-12-11 at 22:02 +0000, "Ingo Althöfer" wrote: > Kahn Jonas <[email protected]> > > ... and that's not interesting: We want to focus on the multimodularity. > > > > So just count the number and depths of peaks. > > Jonas is right. > Identifying peaks and their "volumes" is indeed rather easy. > > For the long run I see a plan with two stages. Stage (ii) should be > interesting particularly as along as pro players still give handicap > stones to bots. > > (i) Given a large board (typically 19x19) and for some middle game position > a Monte-Carlo histogram with two or more peaks. Identify the corresponding > local fight(s) which is/are responsible for the peak(s). This task is not > trivial, but within reach. > > (ii) When still ahead in such a position, the bot should "resolve" a local > fight for the prize of a "few" points. An example for this can be seen > in ds' and Petr Baudis' comments on a game between Catalin Taranu (5p) > (=egc2012pro) and Crazy Stone on August 02, 2012. > http://www.gokgs.com/gameArchives.jsp?user=crazystone&year=2012&month=8 > The upper left corner was no completely cleared, and CrazyStone played > with the resulting peaks for more than one hundred moves. In the > comments Petr tried to defend CrazyStone, but ds claimed that early > action by the bot would have avoided the mis-evaluations. > > ****************************************************** > One of my hopes (in contrast to pessimists like Stefan Kaitschick) is: > When there are "MANY" unresolved local fights things might become less > complicated again for MC bots. (Side remark: on small boards positions > with several peaks are not seldom.) > > Ingo. > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go -- Lars Schaefers Computer Engineering Group of Prof. Dr. Marco Platzner Paderborn Center for Parallel Computing, University of Paderborn Pohlweg 47-49, 33098 Paderborn, Germany Tel: +49 (0)5251 60 4341, Fax: +49 (0)5251 60 5377 Office: Building O 3.119 _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
