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/
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/
[computer-go] Simple gogui problem
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? Also, is there a site that describes the workings of a UCT bot in detail similiar to some chess programming tutorial sites? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Simple gogui problem
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/
Re: [computer-go] Simple gogui problem
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.comwrote: 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/
Re: [SPAM] Re: [computer-go] Simple gogui problem
• record results for all visited nodes___ Where do you record the results? In each node, you keep the statistics of simulations in this node. Many informations can be useless in each node: rave values (the gellysilver paper I've emailed to you) criticality (to be found on Rémi Coulom's web page), but for a first implementation the main thing is the number of won simulations and the number of lost simulations (among those which go through this node). Possibly, you use a hashtable so that if two nodes are identical (up to the history reaching the node, which might nonetheless matter in case of superko) you can share the information. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Simple gogui problem
On Dec 13, 2009, at 11: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. It isn't as fast as you might think. You want to use zobrist hashing for looking up nodes. IIRC, Many Faces discards the search tree after each move and simply does not create more nodes when it runs out of memory. • record results for all visited nodes ___ Where do you record the results? Logically, every node in the search tree has an estimated win rate. It's also possible to store the win rate of all follow-up moves for a given node. That's friendlier on the cache but uses more memory per node. I'm unsure what most bots do. tracking of win rates can be done in a few different ways: • Total simulations, Win percentage • Total simulations, # of wins • Total simulations, # of wins - # losses • # of wins, # of losses More important than how to store those values is how they're initialized based on domain knowledge. 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 hi ghest 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] Simple gogui problem
Many Faces keeps the tree from move to move. I discard nodes with few visits (or old nodes) after each move to free up most of the tree memory, but I keep the core of the tree. When MF runs out of memory it garbage collects some nodes. David From: computer-go-boun...@computer-go.org [mailto:computer-go-boun...@computer-go.org] On Behalf Of Jason House Sent: Sunday, December 13, 2009 12:27 PM To: computer-go Subject: Re: [computer-go] Simple gogui problem On Dec 13, 2009, at 11: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. It isn't as fast as you might think. You want to use zobrist hashing for looking up nodes. IIRC, Many Faces discards the search tree after each move and simply does not create more nodes when it runs out of memory. • record results for all visited nodes___ Where do you record the results? Logically, every node in the search tree has an estimated win rate. It's also possible to store the win rate of all follow-up moves for a given node. That's friendlier on the cache but uses more memory per node. I'm unsure what most bots do. tracking of win rates can be done in a few different ways: • Total simulations, Win percentage • Total simulations, # of wins • Total simulations, # of wins - # losses • # of wins, # of losses More important than how to store those values is how they're initialized based on domain knowledge. 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] Simple gogui problem
On Sun, Dec 13, 2009 at 10:30:13AM -0600, Corey Harris 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. In Pachi, I don't manage memory at all, I simply hope it won't run out; if it does, it means my simulations are needlessly fast ;-). I think if you are reasonably careful about designing your node data structure, you don't need to worry if your thinking times aren't too long, and worry *afterwards* when you will want to play with long thinking times. That's the case at least for 4G of RAM and 9x9 boards. With more memory, this should be even less of an issue, and on 19x19 just as well since your simulations take much longer, so you don't have as much time to grow the tree. Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/