Hello Josef et al, unfortunately, not too much has happened since Explorer in terms of applying CGT to computer Go. For real play, there are large obstacles in terms of board partitioning, selecting strong local moves, and local evaluation (e.g. safety of stones, and necessary backfilling moves). I do believe that a combined MCTS+CGT approach can be successful, but it is far from trivial. I agree with Hideki that endgame may be a weak point of current programs.
The most significant work on CGT+Go that has not been mentioned yet in this thread is the work by Elwyn Berlekamp’s PhD students Bill Fraser and Aaron Siegel. Both built sophisticated specialized software for interactive analysis of human endgames. Their programs allow human experts to partition the board, enter all relevant local lines of play by hand, fix any local scoring problems (e.g. defensive plays inside territory), then use CGT to compute means and temperatures. Both programs can handle complex local ko fights. Especially Aaron’s program had several more advanced features as well, such as support for merging regions, handling small dependencies between regions, and backing up to earlier points in the game. I always thought that an automated, or at least semi-automated, version of their programs would be very useful. I.e. a version that can fill in the repetitive final local moves. Explorer can do that, but only for very simple endgames - fully surrounded by proven-safe stones, and ko-free on the inside. Explorer has never been combined with Bill’s or Aaron’s programs. By the way I have kept Explorer and its CGT modules working all these years. It is now a private extension to Fuego. In more recent work, we have developed forward search-based approaches for computing local temperatures called TDS and TDS+. For simplicity we have tested these in the game of Amazons, but I believe that with a little bit of work they could be made to work for small Go endgames as well. M. Müller, M. Enzenberger, and J. Schaeffer. Temperature discovery search <http://webdocs.cs.ualberta.ca/~mmueller/ps/AAAI104MullerM.pdf>. In Nineteenth National Conference on Artificial Intelligence (AAAI 2004), pages 658-663, San Jose, CA, 2004. Y. Zhang and M. Müller. TDS+: Improving Temperature Discovery Search <http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9554>. AAAI 2015, pages 1241-1247. By the way, if anyone here is interested in doing graduate research with me on this subject, please let me know. Martin On Jul 13, 2015, at 7:20 PM, computer-go-requ...@computer-go.org wrote: > > As far as I know, combinatorial game theory is not used in modern Go > engines, despite its nice theoretical properties. I have been wondering why > this is so. Or am I mistaken and some engines do use it? In general, I only > know about Martin Mueller's Explorer program, which is however slightly > dated :-). Are there some other solvers? > > I imagine it would be fairly easy to swap from MCTS to a CGT solver once it > could be applied.. Or is this not interesting for some reason? >
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
