Re: [Computer-go] CGT endgame solver
Hello, thanks for the replies everyone. Regards, Josef Dne so 18. 7. 2015 1:59 uživatel Igor Polyakov weiqiprogramm...@gmail.com napsal: I'm working on Iomrascalai with Urban Hafner. It's fairly strong at 9x9 (better than GnuGo), but needs work on larger boards. On 2015-07-14 0:22, Ingo Althöfer wrote: Hi, Igor Polyakov weiqiprogramm...@gmail.com: Even strong engines like Fuego will give wrong sequences in yose. And even very strong programs - like CrazyStone - sometimes have problem in evaluating smooth endgames correctly. I will present an example of this (in a game against Stefan Kaitschick) in my talk during the EGC in Liberec. * Question to Igor: You are with us now for some time already. Do you have a bot in the meantime? Would you be willing to let it participate in the EGC bot tournament? Cheers, Ingo. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
I'm working on Iomrascalai with Urban Hafner. It's fairly strong at 9x9 (better than GnuGo), but needs work on larger boards. On 2015-07-14 0:22, Ingo Althöfer wrote: Hi, Igor Polyakov weiqiprogramm...@gmail.com: Even strong engines like Fuego will give wrong sequences in yose. And even very strong programs - like CrazyStone - sometimes have problem in evaluating smooth endgames correctly. I will present an example of this (in a game against Stefan Kaitschick) in my talk during the EGC in Liberec. * Question to Igor: You are with us now for some time already. Do you have a bot in the meantime? Would you be willing to let it participate in the EGC bot tournament? Cheers, Ingo. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
Hi, Igor Polyakov weiqiprogramm...@gmail.com: Even strong engines like Fuego will give wrong sequences in yose. And even very strong programs - like CrazyStone - sometimes have problem in evaluating smooth endgames correctly. I will present an example of this (in a game against Stefan Kaitschick) in my talk during the EGC in Liberec. * Question to Igor: You are with us now for some time already. Do you have a bot in the meantime? Would you be willing to let it participate in the EGC bot tournament? Cheers, Ingo. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
On Tue, Jul 14, 2015 at 9:22 AM, Ingo Althöfer 3-hirn-ver...@gmx.de wrote: * Question to Igor: You are with us now for some time already. Do you have a bot in the meantime? Would you be willing to let it participate in the EGC bot tournament? As Igor is living in the US I'll take the liberty of answering that question (partly). AFAIK he doesn't have a bot of his own but he's done significant work on https://github.com/ujh/iomrascalai that I started as a way to learn the Rust programming language. I unfortunately haven't done much work on it recently and it as it stands it's still significantly weaker than GnuGo on 13x13 and up (see http://cgos.boardspace.net/13x13/cross/Imrscl-023.html) so I'm a bit hesitant to have it participate. Urban -- Blog: http://bettong.net/ Twitter: https://twitter.com/ujh Homepage: http://www.urbanhafner.com/ ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
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
Re: [Computer-go] CGT endgame solver
Darren, 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? It only becomes usable once the game is fairly much decided. (Though, you can construct artificial positions where it gives you a correct move is non-obvious (*) ) IIRC Martin's papers tried to extend it back a bit earlier in the game, and that is the state of the art as far as I know. In contrast MCTS, while theoretically only giving you a rough estimate, is in fact giving you a Good Enough estimate of the score by the time CGT could be used. I don't think MCTS is good enough at endgames. Actually, its performance at endgames is worse than middle, because IMHO MC simulations don't evaluate the values (due to execution speed) of yose-moves and play such moves in random orders. Assuming there are 7, 3, 1 pts moves left at a end position, for example. Correct order is obviously 7, 3 and 1 (sente gets +5 pts) but all combinations are played at the same probability in MC simulations now. The average of the scores has, thus, a big error. A related problem is the understanding of the end of the game. Strong human players easily detect it but bots play much more moves in playouts. If not, the best yose sequence might be found in search tree. Lukasz Lew did some work in this direction; Chapter 5 of his thesis. http://www.mimuw.edu.pl/~lew/files/phd.pdf Hideki Darren *: http://senseis.xmp.net/?MathematicalGo I guess you've already read Chilling Gets the Last Point ? There is also a lot on Sensei's Library: http://senseis.xmp.net/?CGTPath I spent some time trying to extend the ideas, when first learning of CGT, and got nothing worth reporting. They did inspire some of the work I did on life and death analysis; it was intellectually stimulating, but I kept coming back to the same core issue: you need to do search, to handle the kind of situations that come up in real games. -- Hideki Kato mailto:hideki_ka...@ybb.ne.jp ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
performance at endgames is worse than middle, because IMHO MC simulations don't evaluate the values (due to execution speed) of yose-moves and play such moves in random orders. Assuming there are 7, 3, 1 pts moves left at a end position, for example. (Sorry for two messages). I just thought, don't pattern libraries capture this? (I may be wrong on this, but I thought all the strong programs were using patterns to influence search.) The yose patterns come up multiple times in every game, so shouldn't stopping a monkey jump get searched before a hane-connect move on the 1st line? Darren ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
yose-moves and play such moves in random orders. Assuming there are 7, 3, 1 pts moves left at a end position, for example. Correct order is obviously 7, 3 and 1 (sente gets +5 pts) but all combinations are played at the same probability in MC simulations now. The average of the scores has, thus, a big error. Does the MCTS program just play bad moves, or does it ever play game-losing moves? (E.g. at the point in the game where 2pt gote is the biggest move, which is still before CGT kicks in, isn't it?) (I'm quite curious how many playouts are needed for correct play on http://senseis.xmp.net/diagrams/44/bc3b65c106c9db92bec3a13d0e713718.sgf - or do all the strong programs get it wrong and lose the game?) Darren ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[Computer-go] CGT endgame solver
Hello! 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? Regards, Josef ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
Even strong engines like Fuego will give wrong sequences in yose. 1. Sometimes it will play a 1 point sente too early (right as it's available, so maybe it already played it early game), get into a ko and lose 10 points in seki or die This is because playouts always give a better result for the engine playing the 1 point sente than not playing it 2. It doesn't read out ko variations correctly anyway. Sometimes it makes a thousand year ko instead of a direct ko in a simple corner pattern. 3. It plain doesn't play the correct sequence of moves in the endgame. In fact, none of the engines really ever agree on a move order in the endgame and if you run a few simulations at the end of the game you'll keep getting different results, sometimes W+5.5 and sometimes B+3.5 On 2015-07-13 11:47, Darren Cook wrote: performance at endgames is worse than middle, because IMHO MC simulations don't evaluate the values (due to execution speed) of yose-moves and play such moves in random orders. Assuming there are 7, 3, 1 pts moves left at a end position, for example. (Sorry for two messages). I just thought, don't pattern libraries capture this? (I may be wrong on this, but I thought all the strong programs were using patterns to influence search.) The yose patterns come up multiple times in every game, so shouldn't stopping a monkey jump get searched before a hane-connect move on the 1st line? Darren ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
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? It only becomes usable once the game is fairly much decided. (Though, you can construct artificial positions where it gives you a correct move is non-obvious (*) ) IIRC Martin's papers tried to extend it back a bit earlier in the game, and that is the state of the art as far as I know. In contrast MCTS, while theoretically only giving you a rough estimate, is in fact giving you a Good Enough estimate of the score by the time CGT could be used. Darren *: http://senseis.xmp.net/?MathematicalGo I guess you've already read Chilling Gets the Last Point ? There is also a lot on Sensei's Library: http://senseis.xmp.net/?CGTPath I spent some time trying to extend the ideas, when first learning of CGT, and got nothing worth reporting. They did inspire some of the work I did on life and death analysis; it was intellectually stimulating, but I kept coming back to the same core issue: you need to do search, to handle the kind of situations that come up in real games. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
Pattern moves don't prefer bigger moves but just frequent-appear ones, ie, sometimes prefer smaller moves. Additionally, at endgames, bots do much more simulations than middle for a move and patterns have not so big influence on choosing optimal moves. Hideki Darren Cook: 55a407a4.3050...@dcook.org: performance at endgames is worse than middle, because IMHO MC simulations don't evaluate the values (due to execution speed) of yose-moves and play such moves in random orders. Assuming there are 7, 3, 1 pts moves left at a end position, for example. (Sorry for two messages). I just thought, don't pattern libraries capture this? (I may be wrong on this, but I thought all the strong programs were using patterns to influence search.) The yose patterns come up multiple times in every game, so shouldn't stopping a monkey jump get searched before a hane-connect move on the 1st line? Darren ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go -- Hideki Kato mailto:hideki_ka...@ybb.ne.jp ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] CGT endgame solver
yose-moves and play such moves in random orders. Assuming there are 7, 3, 1 pts moves left at a end position, for example. Correct order is obviously 7, 3 and 1 (sente gets +5 pts) but all combinations are played at the same probability in MC simulations now. The average of the scores has, thus, a big error. Does the MCTS program just play bad moves, or does it ever play game-losing moves? (E.g. at the point in the game where 2pt gote is the biggest move, which is still before CGT kicks in, isn't it?) I can say just heavily depends on the position, maybe, mainly due to maximizing not score but winning rate. Another reason for high level games: playing correct moves at endgames requires correct solutions of LD problems on a position. (I'm quite curious how many playouts are needed for correct play on http://senseis.xmp.net/diagrams/44/bc3b65c106c9db92bec3a13d0e713718.sgf - or do all the strong programs get it wrong and lose the game?) Anyway, number of playouts does not help (or, at least help a little if using adaptive simulations) playing correct yose. Number of playouts only reduces statistical errors. If the average is wrong, quantity makes no sense. Hideki -- Hideki Kato mailto:hideki_ka...@ybb.ne.jp ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
