Re: [computer-go] More details about MM + source code
Petr Baudis wrote: Hi! On Thu, Oct 01, 2009 at 11:37:06AM +0200, Rémi Coulom wrote: I have been receiving a lot of questions about MM recently, so I have just updated my web page: http://remi.coulom.free.fr/Amsterdam2007/ You'll find the ICGA Journal version of my paper there, with more details about the math. You'll also find the C++ source code of my implementation of MM. It is a standalone tool that takes a data file as input and produces gammas as output. Thank you very much, this is helping a lot! I wonder, isn't there an off-by-one error in the MM() function? I think Max value is one too big, since you sum all elements in [Min..Max], not [Min..Max). Either the two sums need to be changed, or 1 substracted from Max while setting it and adjusting the FeatureIndex text (which seems right). Or did I miss anything? If I understand correctly, you are refering to that loop: for (int i = Max; --i = Min;) It starts at Max - 1, not Max. I am pretty confident this part is correct. Otherwise, it would have generated obvious errors. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gongo: Go in Go
Even a comparison against the java refbot's performance would be good. IIRC, my D port of the java refbot was within about 1% Sent from my iPhone On Dec 13, 2009, at 12:01 AM, Brian Slesinsky br...@slesinsky.org wrote: I'd like to, but I can't find it. Where do I download it? 2009/12/12 Don Dailey dailey@gmail.com: That's awesome! Do you have performance numbers on the same hardware for the C refbot? - Don On Sat, Dec 12, 2009 at 7:39 PM, Brian Slesinsky br...@slesinsky.org wrote: Thought I'd announce that I've ported the Java refbot to the Go language (with some modifications). I'm getting about 10,000 random playouts/second on 9x9 using a single thread on a 32-bit iMac, using the gc compiler, which doesn't do any optimization. I suspect that a board structure that tracked pseudo-liberties could do better. I probably won't have a chance to work on this for a while, but I think the next step might be some kind of tree search. I'd be interested in a particularly simple, standard, and easy-to-port implementation to use as reference. Source code: http://github.com/skybrian/Gongo Previous discussion on the Go language list: http://groups.google.com/group/golang-nuts/browse_thread/thread/99ab46f5b7219a5b/22e58d9223db10ef - 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/ ___ 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] More details about MM + source code
On Sun, Dec 13, 2009 at 12:15:42PM +0100, Rémi Coulom wrote: If I understand correctly, you are refering to that loop: for (int i = Max; --i = Min;) It starts at Max - 1, not Max. I am pretty confident this part is correct. Otherwise, it would have generated obvious errors. Oh, I'm sorry, you are right, it's obvious when I look at it after good night sleep. ;-) Petr Pasky Baudis ___ 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] More details about MM + source code
2009/12/13 Petr Baudis pa...@ucw.cz: On Sun, Dec 13, 2009 at 12:15:42PM +0100, Rémi Coulom wrote: If I understand correctly, you are refering to that loop: for (int i = Max; --i = Min;) It starts at Max - 1, not Max. I am pretty confident this part is correct. Otherwise, it would have generated obvious errors. Oh, I'm sorry, you are right, it's obvious when I look at it after good night sleep. ;-) A few years ago I could have written that loop the same way, but now I think this is significantly easier to read: for (int i = Max-1; i=Min; --i) My job involves being called at 3 o'clock in the morning because a program is doing the wrong thing, and this has made me develop an enormous appreciation for clarity. I prefer code that is still obvious when you haven't had a good night sleep. Álvaro. ___ 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] Reference Montecarlo TreeDecision Bot.
I like standard references bots a lot :) I think they are very usefull for promoting computer-go, and helping new comers. It gives a very good base for confidence in a new implementation from a new comer :) So it would certainly be usefull, if people could agree on a reference monte carlo tree bot (and provide some reference implementations in popular langages). It would obviously be based on the reference light-bot. Usually people begins with trying their hands at 9x9. For 9x9 basic UCT is viable. I think you get about 50% win against gnu with 50K light-playout and UCT. First we have to agree about a standard UCT formula. I think the http://senseis.xmp.net/?UCT is okay. (first on google for uct algorithm :) ) 1/ Uct formala - UCTValue(parent, n) = winrate + sqrt((ln(parent.visits))/(5*n.nodevisits)) Uct trys each node at least once. We have to agree about an order policy for nodes. Simplicity would call for A1, A2 ... A9, B1 .. B9, C1.. C9 etc. Uper left corner first, then upper edge, etc. But i suppose most people would find that very uncomfortable (giving priority to known worst move in game :) ) so... 2/ If parent.visit 1000, pick a move according to UCT policy, if parent.visit=1000 pick up a move with light playout policy. I think once we agree about 1/ and 2/, we can build reference for pure UCT light-Playout bots. //- Alternatively, i would apreciate if it existed a reference UCT pure-light implementation for 19x19. I think the main difference here, is that pure UCT is hardly an option. So i propose this : 1/ Uct formala - UCTValue(parent, n) = winrate + sqrt((ln(parent.visits))/(5*n.nodevisits)) 2/ If parent.visit 1000, pick a move according to UCT policy (winrate would be (realVisit* realWinRate + AMAFwinRate)/(realVisit+1)), if parent.visit=1000 pick up a move according to AMAF light playout policy. Date: Sat, 12 Dec 2009 16:39:56 -0800 From: br...@slesinsky.org To: computer-go@computer-go.org Subject: [computer-go] Gongo: Go in Go Thought I'd announce that I've ported the Java refbot to the Go language (with some modifications). I'm getting about 10,000 random playouts/second on 9x9 using a single thread on a 32-bit iMac, using the gc compiler, which doesn't do any optimization. I suspect that a board structure that tracked pseudo-liberties could do better. I probably won't have a chance to work on this for a while, but I think the next step might be some kind of tree search. I'd be interested in a particularly simple, standard, and easy-to-port implementation to use as reference. Source code: http://github.com/skybrian/Gongo Previous discussion on the Go language list: http://groups.google.com/group/golang-nuts/browse_thread/thread/99ab46f5b7219a5b/22e58d9223db10ef - Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Téléchargez Internet Explorer 8 et surfez sans laisser de trace ! http://clk.atdmt.com/FRM/go/182932252/direct/01/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gongo: Go in Go
Javabot is at about 6.5k but they're not really comparable anymore, because I added an array to keep track of the liberties for each point. On Sun, Dec 13, 2009 at 5:15 AM, Jason House jason.james.ho...@gmail.com wrote: Even a comparison against the java refbot's performance would be good. IIRC, my D port of the java refbot was within about 1% Sent from my iPhone On Dec 13, 2009, at 12:01 AM, Brian Slesinsky br...@slesinsky.org wrote: I'd like to, but I can't find it. Where do I download it? 2009/12/12 Don Dailey dailey@gmail.com: That's awesome! Do you have performance numbers on the same hardware for the C refbot? - Don On Sat, Dec 12, 2009 at 7:39 PM, Brian Slesinsky br...@slesinsky.org wrote: Thought I'd announce that I've ported the Java refbot to the Go language (with some modifications). I'm getting about 10,000 random playouts/second on 9x9 using a single thread on a 32-bit iMac, using the gc compiler, which doesn't do any optimization. I suspect that a board structure that tracked pseudo-liberties could do better. I probably won't have a chance to work on this for a while, but I think the next step might be some kind of tree search. I'd be interested in a particularly simple, standard, and easy-to-port implementation to use as reference. Source code: http://github.com/skybrian/Gongo Previous discussion on the Go language list: http://groups.google.com/group/golang-nuts/browse_thread/thread/99ab46f5b7219a5b/22e58d9223db10ef - 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/ ___ 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 Sun, Dec 13, 2009 at 07:08:54PM +0100, Denis fidaali wrote: 2/ If parent.visit 1000, pick a move according to UCT policy, if parent.visit=1000 pick up a move with light playout policy. This is a curious rule, does any actual existing bot use a rule like this? It seems immensely ineffective. I think once we agree about 1/ and 2/, we can build reference for pure UCT light-Playout bots. There already are UCT reference bots, aren't there? I personally think it's best to follow the seminal papers or existing implementations with code available. 2/ If parent.visit 1000, pick a move according to UCT policy (winrate would be (realVisit* realWinRate + AMAFwinRate)/(realVisit+1)), if parent.visit=1000 pick up a move according to AMAF light playout policy. 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. -- 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] 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] Reference Montecarlo TreeDecision Bot.
On Dec 13, 2009, at 8:08 AM, Denis fidaali wrote: So it would certainly be usefull, if people could agree on a reference monte carlo tree bot (and provide some reference implementations in popular langages). It would obviously be based on the reference light-bot. This is what I attempted in the 'plug-and-go' project. Apart from making it easy to get started, I included a Java implementation of the AMAF refbot and of what could be used as a refbot for a MCTS refbot with light playouts. But I don't think it got much attention and now I don't have time for it. But it's there for anyone to take a look at. At best I can spend a few hours here and there if people want it. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gongo: Go in Go
Javabot is at about 6.5k but they're not really comparable anymore, because I added an array to keep track of the liberties for each point. Do you mean you added the array to Gongo or to the java version? I.e. is Gongo twice as quick as the java version because the java version is doing more, or twice as quick even though it is also doing more? Darren Thought I'd announce that I've ported the Java refbot to the Go language (with some modifications). I'm getting about 10,000 random playouts/second on 9x9 using a single thread on a 32-bit iMac, using the gc compiler, which doesn't do any optimization. I suspect that a board structure that tracked pseudo-liberties could do better. Source code: http://github.com/skybrian/Gongo -- Darren Cook, Software Researcher/Developer http://dcook.org/gobet/ (Shodan Go Bet - who will win?) http://dcook.org/mlsn/ (Multilingual open source semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ 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] Gongo: Go in Go
On Sun, Dec 13, 2009 at 2:56 PM, Darren Cook dar...@dcook.org wrote: Do you mean you added the array to Gongo or to the java version? I.e. is Gongo twice as quick as the java version because the java version is doing more, or twice as quick even though it is also doing more? Gongo is faster because I added an array to keeps track of liberties. The bottleneck is in the code that checks whether a move is a capture or suicide after choosing a random move. The Java refbot has to visit all the cells in each chain until it finds a liberty. Gongo does this as well, but it's a bit faster due to keeping track of the number of liberties of each point. Both Java and Go (the language) do array index checking, but the Go compiler I'm using isn't smart enough to optimize them away yet, so I believe reducing array accesses is a bigger win for Gongo than it would be for Java. - Brian ___ 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/
Re: [computer-go] Reference Montecarlo TreeDecision Bot.
I probably won't have time to look at it much, but it would be good to have another Java refbot to compare against. I did look at Plug-and-Go but the install seems a bit tricky since I don't use Eclipse or Spring. Ideally, each engine should compile to a jar file that provides a GTP interface when you run it with java -jar somefile.jar, just like Java refbot. - Brian 2009/12/13 Mark Boon tesujisoftw...@gmail.com: On Dec 13, 2009, at 8:08 AM, Denis fidaali wrote: So it would certainly be usefull, if people could agree on a reference monte carlo tree bot (and provide some reference implementations in popular langages). It would obviously be based on the reference light-bot. This is what I attempted in the 'plug-and-go' project. Apart from making it easy to get started, I included a Java implementation of the AMAF refbot and of what could be used as a refbot for a MCTS refbot with light playouts. But I don't think it got much attention and now I don't have time for it. But it's there for anyone to take a look at. At best I can spend a few hours here and there if people want it. Mark ___ 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/
