RE: [computer-go] Simple gogui problem
This is what I do (no tree, just a hash table). The cost is that the nodes become very large because every node also holds all the child information, all rave counters, etc. So memory usage is higher. David From: computer-go-boun...@computer-go.org [mailto:computer-go-boun...@computer-go.org] On Behalf Of Corey Harris Sent: Monday, December 14, 2009 5:34 AM To: computer-go Subject: Re: [computer-go] Simple gogui problem Is it possible to just use a hash table (no tree) and just update the hash entry's node? Advantages/disadvantages of this approach? On Sun, Dec 13, 2009 at 10:30 AM, Corey Harris charri...@gmail.com wrote: Was looking for a basic UCT data structure. I guess a tree structure is created in memory. How is this managed, because memory can be exausted pretty fast. . record results for all visited nodes___ Where do you record the results? I appologize for the simple questions, I'm new at this. On Sun, Dec 13, 2009 at 9:48 AM, Jason House jason.james.ho...@gmail.com wrote: On Dec 13, 2009, at 9:38 AM, Corey Harris charri...@gmail.com wrote: I know this is a simple issue but I'm not sure of the solution. I am currently in the very early stages of writing a go engine. I have the board state and simple opening library implemented (no play logic yet). I'm would like to output debugging/developnent output statements to the gogui shell window. If the engine sends printf(some output\n); gogui says Sent a malformed response. If it fprintf(stderr, some output\n); nothing is displayed. How can you print messages to the shell without disrupting the message protocol? Writing to stderr works fine for me, but gogui does not show shell output immediately. It waits until some point in overall execution before showing anything in the shell output. Also, is there a site that describes the workings of a UCT bot in detail similiar to some chess programming tutorial sites? Not that I'm aware of, but senseis.xmp.net http://senseis.xmp.net/ might be a good place to start. Basic UCT is simple: . always start at tree root . pick the child with the highest metric (upper confidence bound on win rate) . repeat last step until you reach a leaf . if simulations of the leaf N, expand leaf and pick child with highest metric . play random game . record results for all visited nodes___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Biasing nodes according to pattern gammas
Hi! How would you recommend to bias nodes in the tree according to pattern strengths, when the pattern strength can be in (0,inf)? (I'm using this for Remi's pattern ELO model, but I guess other fuzzy pattern values face similar problems.) I have node values in the form of W / N (wins / visits), the trouble is that I'm not sure how to scale the value properly (and quickly), given that most pattern values are around 1, but some are in the 0.001 area while best ones are easily 500 (_and_ this is all in a minimax tree). How do you (e.g. CrazyStone) solve the issue? Or do you perform explicit unpruning by sorting the nodes instead of biasing them? Thanks! -- Petr Pasky Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Biasing nodes according to pattern gammas
Petr Baudis wrote: Hi! How would you recommend to bias nodes in the tree according to pattern strengths, when the pattern strength can be in (0,inf)? (I'm using this for Remi's pattern ELO model, but I guess other fuzzy pattern values face similar problems.) I have node values in the form of W / N (wins / visits), the trouble is that I'm not sure how to scale the value properly (and quickly), given that most pattern values are around 1, but some are in the 0.001 area while best ones are easily 500 (_and_ this is all in a minimax tree). How do you (e.g. CrazyStone) solve the issue? Or do you perform explicit unpruning by sorting the nodes instead of biasing them? Thanks! I bias them too. I use move probability, not move gamma, which normalizes the value between 0 and 1. I multiply this probability by a constant, divide by the number of playouts, and add it to the move score. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Biasing nodes according to pattern gammas
On Mon, Dec 14, 2009 at 07:46:54PM +0100, Rémi Coulom wrote: I bias them too. I use move probability, not move gamma, which normalizes the value between 0 and 1. I multiply this probability by a constant, divide by the number of playouts, and add it to the move score. I see, but the constant needs to be fairly large, since probabilities will usually be fairly low...? Do you have a recommendation about initial settings of the constant? (1.5 or 20? :) Thanks! Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Biasing nodes according to pattern gammas
Petr Baudis wrote: On Mon, Dec 14, 2009 at 07:46:54PM +0100, Rémi Coulom wrote: I bias them too. I use move probability, not move gamma, which normalizes the value between 0 and 1. I multiply this probability by a constant, divide by the number of playouts, and add it to the move score. I see, but the constant needs to be fairly large, since probabilities will usually be fairly low...? Do you have a recommendation about initial settings of the constant? (1.5 or 20? :) Thanks! I use 100. But I don't use RAVE. Aja is using RAVE in Erica, and found a lower value is better (50 or so). You have to run your own tests. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Reference Montecarlo TreeDecision Bot.
I've found that AMAF gives very little boost with light playouts, Thanks for this interesting comment. I would (erroneously) have believed that AMAF gives better results with non-optimized implementation (e.g. in Havannah with no expertise Amaf provides huge improvements). In particular, I believed it was moderately efficient in 19x19 due to the patterns which already provide relevant informations - but I could never test it (testing properly this assumption requires the tuning of the version without Rave, which would be time consuming and boring :-) ). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Reference Montecarlo TreeDecision Bot.
That same statement baffles me. AMAF gives a huge boost with light playouts for me. As the number of playouts increase, AMAF gives less and less. After a few thousand playouts it's almost nothing but if it's worse than not doing AMAF it is difficult to measure. Of course MCTS never does thousands of playouts from a single node. What is the definition of light playouts? I am referning only to purely random playouts and perhaps that is where the discrepency is. Don 2009/12/14 Olivier Teytaud teyt...@lri.fr I've found that AMAF gives very little boost with light playouts, Thanks for this interesting comment. I would (erroneously) have believed that AMAF gives better results with non-optimized implementation (e.g. in Havannah with no expertise Amaf provides huge improvements). In particular, I believed it was moderately efficient in 19x19 due to the patterns which already provide relevant informations - but I could never test it (testing properly this assumption requires the tuning of the version without Rave, which would be time consuming and boring :-) ). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Reference Montecarlo TreeDecision Bot.
I've found that AMAF gives very little boost with light playouts, you really need something fairly meaningful already to get any kind of real boost. To have at least 10% chance of beating GNUGo with reasonable time per game (to be able to play-test your bot), I think you can't avoid doing a lot more than plain UCT + AMAF + light playouts. I suppose it depends on what exactly you try to boost. As others already stated doing just light playouts, no tree-search, AMAF gives a huge boost. With light playouts and UCT tree-search, AMAF still gives a considerable improvement. Maybe you can try to search the archives, I think I posted about it. My MCTS ref-bot has a parameter called 'useAMAF'. You can experiment with witching it on and off with different numbers of playouts if you want to. If I remember well, the difference was very obvious, even with high number of playouts. Also the latter statement I find an exaggeration. Plain UCT + AMAF + semi-light playouts beats GNUGo without too much work. All I needed was including some simple tactics and a few tricks to prune the tree early in the game (i.e. not play on the 1st and 2nd line). Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Simple gogui problem
This approach seems easier to manage. 2009/12/14 David Fotland fotl...@smart-games.com This is what I do (no tree, just a hash table). The cost is that the nodes become very large because every node also holds all the child information, all rave counters, etc. So memory usage is higher. David *From:* computer-go-boun...@computer-go.org [mailto: computer-go-boun...@computer-go.org] *On Behalf Of *Corey Harris *Sent:* Monday, December 14, 2009 5:34 AM *To:* computer-go *Subject:* Re: [computer-go] Simple gogui problem Is it possible to just use a hash table (no tree) and just update the hash entry's node? Advantages/disadvantages of this approach? On Sun, Dec 13, 2009 at 10:30 AM, Corey Harris charri...@gmail.com wrote: Was looking for a basic UCT data structure. I guess a tree structure is created in memory. How is this managed, because memory can be exausted pretty fast. • record results for all visited nodes___ Where do you record the results? I appologize for the simple questions, I'm new at this. On Sun, Dec 13, 2009 at 9:48 AM, Jason House jason.james.ho...@gmail.com wrote: On Dec 13, 2009, at 9:38 AM, Corey Harris charri...@gmail.com wrote: I know this is a simple issue but I'm not sure of the solution. I am currently in the very early stages of writing a go engine. I have the board state and simple opening library implemented (no play logic yet). I'm would like to output debugging/developnent output statements to the gogui shell window. If the engine sends printf(some output\n); gogui says Sent a malformed response. If it fprintf(stderr, some output\n); nothing is displayed. How can you print messages to the shell without disrupting the message protocol? Writing to stderr works fine for me, but gogui does not show shell output immediately. It waits until some point in overall execution before showing anything in the shell output. Also, is there a site that describes the workings of a UCT bot in detail similiar to some chess programming tutorial sites? Not that I'm aware of, but senseis.xmp.net might be a good place to start. Basic UCT is simple: • always start at tree root • pick the child with the highest metric (upper confidence bound on win rate) • repeat last step until you reach a leaf • if simulations of the leaf N, expand leaf and pick child with highest metric • play random game • record results for all visited nodes___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Reference Montecarlo TreeDecision Bot.
On Mon, Dec 14, 2009 at 11:45:44AM -1000, Mark Boon wrote: I've found that AMAF gives very little boost with light playouts, you really need something fairly meaningful already to get any kind of real boost. To have at least 10% chance of beating GNUGo with reasonable time per game (to be able to play-test your bot), I think you can't avoid doing a lot more than plain UCT + AMAF + light playouts. I suppose it depends on what exactly you try to boost. As others already stated doing just light playouts, no tree-search, AMAF gives a huge boost. I never tried that, I was talking about UCT case only, sorry if that was unclear. With light playouts and UCT tree-search, AMAF still gives a considerable improvement. Maybe you can try to search the archives, I think I posted about it. My MCTS ref-bot has a parameter called 'useAMAF'. You can experiment with witching it on and off with different numbers of playouts if you want to. If I remember well, the difference was very obvious, even with high number of playouts. Interesting, in my bot, AMAF really made only very small difference (maybe 15% - 25%, +-5% [*]). Perhaps I had some bug in my implementation that caused these measurements. [*] My test records do not go back enough and I cannot re-check easily since apparently, in current Pachi non-AMAF UCT policy must be broken since it never seems to win against GNUGo, and I really don't feel motivated enough to debug plain UCB1. ;-) So I'm sorry if I misled anyone, perhaps it is/was some Pachi bug causing these observations of mine. -- Petr Pasky Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Reference Montecarlo TreeDecision Bot.
I'm a bit confused by the difference between RAVE and AMAF. Or are they the same thing? - Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Reference Montecarlo TreeDecision Bot.
It's easy to get confused -- different researchers use the terms slightly differently. They both gather data on moves other than a move made from the current board configuration. I would say that AMAF stores statistics on every move played from any position, while RAVE only stores info on moves played from descendants of the current position. Consequently, AMAF uses a global table, whereas RAVE data must be stored at every node. Peter Drake http://www.lclark.edu/~drake/ On Dec 14, 2009, at 10:06 PM, Brian Slesinsky wrote: I'm a bit confused by the difference between RAVE and AMAF. Or are they the same thing? - Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/