Re: [Computer-go] ieee article about computer go
Thank you for the enlightening explanation. It actually explains more than the explainers may wish to convey. My condolences to you for having that innovative visual opener foisted on your fine article. Stefan ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] ieee aticle about computer go by Jonathan Schaeffer
Determining the best move is tricky, however. The most natural approach would be to pick the move with the highest probability of leading to a win. But this is usually too risky. For example, a move with 7 wins out of 10 trials may have the highest odds of winning (70 percent), but because this number comes from only 10 trials, the uncertainty is high. A move with 65,000 wins out of 100,000 trials (65 percent) is a safer bet. This suggests a different strategy: Choose the move with the largest number of wins. And this is indeed the standard approach. Really? Changing the example, what if the 65,000 wins were out of 650,000? (1% win rate vs. 70% win rate), then does it always make sense to choose the path with the most number of moves? If you had a choice between a 1% 65,000-wins move and a 70% 7-wins move, MCTS will keep exploring the 70% move, until it either reaches 65,001 wins, and can be chosen, or the winning percentage comes down to 1% also. BTW, that implies it would be very difficult to ever reach the situation you describe, as 1% win rate moves wouldn't be given 650,000 trials (unless all other moves on the board are equally bad, i.e. the game is clearly lost). Darren -- Darren Cook, Software Researcher/Developer My new book: Data Push Apps with HTML5 SSE Published by O'Reilly: (ask me for a discount code!) http://shop.oreilly.com/product/0636920030928.do Also on Amazon and at all good booksellers! ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] ieee aticle about computer go by Jonathan Schaeffer
On Thu, Jul 3, 2014 at 9:00 AM, Darren Cook dar...@dcook.org wrote: If you had a choice between a 1% 65,000-wins move and a 70% 7-wins move, MCTS will keep exploring the 70% move, until it either reaches 65,001 wins, and can be chosen, or the winning percentage comes down to 1% also. BTW, that implies it would be very difficult to ever reach the situation you describe, as 1% win rate moves wouldn't be given 650,000 trials (unless all other moves on the board are equally bad, i.e. the game is clearly lost). What I dont understand, is why the variation that's trying to catch up has to absolutely overtake the leader. Shouldn't there be a substantial bonus for a late high success rate? ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] ieee aticle about computer go by Jonathan Schaeffer
On Thu, Jul 03, 2014 at 10:57:17AM +0200, Stefan Kaitschick wrote: On Thu, Jul 3, 2014 at 9:00 AM, Darren Cook dar...@dcook.org wrote: If you had a choice between a 1% 65,000-wins move and a 70% 7-wins move, MCTS will keep exploring the 70% move, until it either reaches 65,001 wins, and can be chosen, or the winning percentage comes down to 1% also. BTW, that implies it would be very difficult to ever reach the situation you describe, as 1% win rate moves wouldn't be given 650,000 trials (unless all other moves on the board are equally bad, i.e. the game is clearly lost). What I dont understand, is why the variation that's trying to catch up has to absolutely overtake the leader. Shouldn't there be a substantial bonus for a late high success rate? The way this bonus is often implemented is that if a disparity between the move with the highest winrate and the move with the highest number of simulations is different, the program spends some extra time searching to give a chance to resolve this. (Conversely, if some move has been simulated so much more that no other move can overtake it in the number of simulations in the alloted time anymore, the search can be stopped early.) P.S.: No, I don't like Japanese byoyomi for Pachi. ;-) -- Petr Baudis Life is short, the craft long, opportunity fleeting, experiment treacherous, judgment difficult. -- Hippocrates ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Computer-go Digest, Vol 54, Issue 4
My original example was unrealistic and on the extreme side to make a point. However if there are nodes with say 7/10, 12/20, and 50/100 how should they be ranked? In some sense, the first one seems promising since we've only searched just a few nodes, yet we are mainly seeing wins (granted, the last one expresses more confidence). To me, this would seem like an argument that favors win rate over win count (and we don't always have the benefit of extending the search for these low confidence nodes until the law of large numbers sorts things out). Perhaps there is an argument that the UCB formula won't generally let this happen since it takes into consideration both win rate and tries to increase confidence by promoting the visit of nodes with low visit counts. Still, I can envision cases where time is running out, and UCT has just recently discovered a promising new branch. If the choice were 1/2 vs. 50/100, the second expresses more confidence yet one could argue we should search the first move more (given that time is available to do so) to find out if it is, in fact, better than .5 (since being low confidence, it has a reasonable chance of being better than the 2nd). So the general question becomes how to effectively trade off win rate with win rate confidence? FWIW, the sample code at http://mcts.ai/code/python.html Does something completely different, it selects the root node which has the most number of visits: return sorted(rootnode.childNodes, key = lambda c: c.visits)[-1].move # return the move that was most visited On Thu, Jul 03, 2014 at 10:57:17AM +0200, Stefan Kaitschick wrote: On Thu, Jul 3, 2014 at 9:00 AM, Darren Cook dar...@dcook.org wrote: If you had a choice between a 1% 65,000-wins move and a 70% 7-wins move, MCTS will keep exploring the 70% move, until it either reaches 65,001 wins, and can be chosen, or the winning percentage comes down to 1% also. BTW, that implies it would be very difficult to ever reach the situation you describe, as 1% win rate moves wouldn't be given 650,000 trials (unless all other moves on the board are equally bad, i.e. the game is clearly lost). What I dont understand, is why the variation that's trying to catch up has to absolutely overtake the leader. Shouldn't there be a substantial bonus for a late high success rate? The way this bonus is often implemented is that if a disparity between the move with the highest winrate and the move with the highest number of simulations is different, the program spends some extra time searching to give a chance to resolve this. (Conversely, if some move has been simulated so much more that no other move can overtake it in the number of simulations in the alloted time anymore, the search can be stopped early.) P.S.: No, I don't like Japanese byoyomi for Pachi. ;-) -- Petr Baudis Life is short, the craft long, opportunity fleeting, experiment treacherous, judgment difficult. -- Hippocrates -- ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go End of Computer-go Digest, Vol 54, Issue 4 ** ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] CGOS migration
On 06/30/2014 01:52 PM, Christoph Birk wrote: On 06/23/2014 02:08 PM, Joshua Shriver wrote: I'm migrating between two servers with different IP's so cgos will be down while DNS records are updated worldwide. I still cannot connect to 'cgos.computergo.org' The connection has timed out The server at cgos.computergo.org is taking too long to respond. Christoph ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] ieee article about computer go
Hi Martin, hi all, during the European Go Congress 2012 in Bonn, I was able to buy a very nice drawing by Tanja Esser, visualising the difference between Monte Carlo- and human go. http://www.althofer.de/aesthetics-beyond/go--tanja-esser.jpg If someone wants to use this motif for some publication, feel free to ask me. There is a good chance I will give green light. Cheers, Ingo. Gesendet: Mittwoch, 02. Juli 2014 um 19:15 Uhr Von: Martin Mueller mmuel...@ualberta.ca An: computer-go@dvandva.org Betreff: Re: [Computer-go] ieee article about computer go We had no control over the title page art. The IEEE art dept gave the following explanation for their work: The opening art for the story is conceptual and illustrative. It is not meant to show a game in progress, but rather the idea of AI for Go. We took the game elements (board, stones) and used them to create a brain shape and evoke digital pixels.” Hope that helps :) Martin ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] IEEE Spectrum article
It is a great article overall. I would like it more if it mentions Mogo, at least Follow from the opponent's previous move was actually Mogo's invention in the famous UCT paper, not Fuego's, not to mention a lot of Mogo's achievements on 9x9. But I really like the paragraph describing the great idea RAVE. It might be the first introductory article (for general people) trying to explain RAVE. Hi Aja, thanks for comments. We certainly didn’t mean to short-change the MoGo team's or anybody else’s contribution. For this article there were two main points: - try to explain as much as possible how things work in a current program - have some kind of dramatic story for the introduction. We chose the Fuego game against Mr Chou since we are most familiar with it :) Anything else had to be compressed into very very little space. So there was no real space for history other than the chess vs Go playing strength graph. The original version of the graph had program names attached to it, but it got simplified away. There is quite a number of popular articles that focus on MoGo or Crazy Stone or Zen. For example, see articles on https://www.lri.fr/~teytaud/mogo.html Martin___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Computer-go Digest, Vol 54, Issue 4
On Thu, Jul 03, 2014 at 06:18:32AM -0700, Greg Schmidt wrote: Perhaps there is an argument that the UCB formula won't generally let this happen since it takes into consideration both win rate and tries to increase confidence by promoting the visit of nodes with low visit counts. Still, I can envision cases where time is running out, and UCT has just recently discovered a promising new branch. In practice, choosing this promising new branch is very dangerous. Promising new branches pop up all the time, but we can observe them usually being swiftly squashed away by finding a refutation to their current favorable move as soon as they start receiving simulations, and their winrate fades back again. The fact that some branch has already received many simulations means that it consistently survived all sorts of proposed refutations. -- Petr Baudis Life is short, the craft long, opportunity fleeting, experiment treacherous, judgment difficult. -- Hippocrates ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] IEEE Spectrum article
Hi Martin, 2014-07-03 22:02 GMT+01:00 Martin Mueller mmuel...@ualberta.ca: We certainly didn’t mean to short-change the MoGo team's or anybody else’s contribution. For this article there were two main points: - try to explain as much as possible how things work in a current program - have some kind of dramatic story for the introduction. We chose the Fuego game against Mr Chou since we are most familiar with it :) Thanks for the explanations. I like this article a lot (even shared it in Facebook), just felt a little bit strange that Mogo is not mentioned at all while the author described the MCTS revolution and techniques. But I completely understand your points: yeah the space is too little to cover other things. It is a great article anyway. Thanks for the write-up. Aja ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go