Re: [Computer-go] On Semeai Detection. Was: Zen resignation positions
Hi all, 2013/10/10 Lars Schäfers sl...@upb.de 3) two-safe-group It is a term used by Aja Huang to describe a class of Go positions he created, that contain two safe but not yet completely settled groups. The positions were created with the aim to be difficult to understand for current MC programs. Aja Huang and Martin Müller recently published a very nice paper about this test suite and experimental results with a number of strong Go programs. You can find their paper Investigating the Limits of Monte Carlo Tree Search Methods in Computer Go here: http://webdocs.cs.ualberta.ca/~mmueller/publications.html If you are interested, the final version of our paper Investigating the Limits of Monte Carlo Tree Search Methods in Computer Go is available for download at https://sites.google.com/site/ajahuangshomepage/home The other paper on the site is MoHex 2.0: a pattern-based MCTS Hex player where we have described the various MCTS enhancements (large patterns in priors, probabilistic simulation, etc) that boosted the MCTS Hex program MoHex for 250-300 Elo, around 80%-85% winning rate against the original version. The latest source of MoHex (hopefully including our C++ implementation of MM) will be publicly available in the near future. Best regards, Aja ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] On Semeai Detection. Was: Zen resignation positions
Hi Robert, I too have problems with receiving mails form this list. Hence, sorry for late replies. Thanks to veg for working on this issue! 1) Use of the term semeai In this paper the term semeai is indeed not used in the most accurate fashion. We realized this only after the paper was already accepted (thanks to a comment by Rémi Coulom) and addressed this issue in the conclusion section: For the sake of correctness, we must admit that the term semeai might not be completely appropriately used throughout this paper. A score cluster does not always need to be caused by the presence of a capturing race. In any case, it represents an evaluation singularity that is likely caused by uncertainty in the evaluation of the life and death state of one or more groups of pieces. Also in this case our approach will help to localize the respective groups on the board. 2) Identification of score clusters The score clusters are obtained by analyzing the observed outcomes of the semi-randomized MC simulations. The identification of the critical board regions has no two-value-logic evidence. 3) two-safe-group It is a term used by Aja Huang to describe a class of Go positions he created, that contain two safe but not yet completely settled groups. The positions were created with the aim to be difficult to understand for current MC programs. Aja Huang and Martin Müller recently published a very nice paper about this test suite and experimental results with a number of strong Go programs. You can find their paper Investigating the Limits of Monte Carlo Tree Search Methods in Computer Go here: http://webdocs.cs.ualberta.ca/~mmueller/publications.html 4) runtime We plan to use this heuristic foremost in near root nodes. It is certainly to expensive to be used all over the tree. The collection of the necessary data is pretty efficient. The mode seeking part is a bit more involved, but not more expensive than the computation of other state-of-the-art heuristics used for move prediction. This is at least the case for Gomorras implementation of those heuristics. Once again: The described heuristic is yet not used in our productive version of Gomorra. Its application to improve the MCTS search process is still research in progress. Cheers, Lars On 09.10.2013 15:30, Lars Schäfers wrote: On Semeai Detection in Monte-Carlo Go In this paper, does semeai stand for one of 'capturing race', 'unsettled life and death situation', 'basic ko fight', 'multiple ko fight', 'ladder breaking' 'etc.'? Is the identification of a cluster proven only with stochastic probability, or is there even two-value-logic evidence? What is a two-safe-group? How do the methods affect simulations runtime? -- robert jasiek -- 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 Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
[Computer-go] On Semeai Detection. Was: Zen resignation positions
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 +, Ingo Althöfer wrote: Kahn Jonas jonas.k...@math.u-psud.fr ... 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=crazystoneyear=2012month=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 Computer-go@dvandva.org 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 Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] On Semeai Detection. Was: Zen resignation positions
On 09.10.2013 15:30, Lars Schäfers wrote: On Semeai Detection in Monte-Carlo Go In this paper, does semeai stand for one of 'capturing race', 'unsettled life and death situation', 'basic ko fight', 'multiple ko fight', 'ladder breaking' 'etc.'? Is the identification of a cluster proven only with stochastic probability, or is there even two-value-logic evidence? What is a two-safe-group? How do the methods affect simulations runtime? -- robert jasiek ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
