Re: [computer-go] Efficiently selecting a point to play in a random playout
I've been messing around with where to apply heuristics. Candidates include: 1) In the UCT tree, since this is earliest in each playout. 2) In the moves beyond the tree (heavy playouts), since this is where most of the moves happen. Because this part is so speed-critical, ... Remi (using learned patterns instead of heuristics, but should be the same) got dramatic improvements doing both (see quote below). It is also my understanding that in Crazy Stone the patterns are being used at every ply in the playouts; given that the program is being given a constant time it seems the overhead of this is more than made up for by the increase in strength. Darren -- In the computer-go Amsterdam 2007 paper thread, on 2007-05-18: Here are tests of Crazy Stone at 90s/game 1CPU against GNU 3.6 level 10, measured over about 200 games: no pattern: 38.2% (version available on my web page) patterns in simulations:68.2% patterns for pruning and simulations:90.6% I found these number in my history of Crazy Stone versions, so they may not be extremely accurate, because other things have changed in between. I will run cleaner tests for the final version of the paper. I will also try to test what each feature brings. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Darren Cook wrote: I've been messing around with where to apply heuristics. Candidates include: 1) In the UCT tree, since this is earliest in each playout. 2) In the moves beyond the tree (heavy playouts), since this is where most of the moves happen. Because this part is so speed-critical, ... Remi (using learned patterns instead of heuristics, but should be the same) got dramatic improvements doing both (see quote below). It is also my understanding that in Crazy Stone the patterns are being used at every ply in the playouts; given that the program is being given a constant time it seems the overhead of this is more than made up for by the increase in strength. Darren Interestingly, I got no overhead when I added 3x3 patterns. It even made simulations faster, because detecting illegal moves or moves into eyes came for free. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Peter Drake wrote: On Jun 6, 2007, at 2:41 PM, Rémi Coulom wrote: Also, if you have a clever probability distribution, the range of values for each move will be very large. For instance, here are two 3x3 shapes used by Crazy Stone (# to move): O O # # . . # O # Gamma = 143473; . # # . . . . . . Gamma = 20; Playing in the empty corner has gamma = 1. So that would be a lot of tickets to distribute. Is this distribution something like the number of times a given move was played in your training set? No. It is explained in my Amsterdam paper: http://remi.coulom.free.fr/Amsterdam2007/ Doesn't the play in empty space pattern swamp everything else? No. Gamma = 214 for that one. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
I noticed there is almost no activity on the 19x19 server. I don't have the computing power to run bots on both servers, but I remember there were some volunteers.If someone would run Dog for me, I would appreciate it. It's a linux program statically linked I think. It is running about 1400 strength and is a worthy opponent for Christoph's program. It would be nice to get some competition going, it doesn't matter if it's playing well below gnugo's level, a lot of program play at that level so it would be great. Someone could also run a weak Gnugo - perhaps with level set from 1-3 or something. To run gnugo at level 2 - ./gnugo-3.7.10-L2 --mode gtp --score aftermath --capture-all-dead --chinese-rules --min-level 2 --max-level 2 --positional-superko - Don On Tue, 2007-06-05 at 14:21 -0700, Christoph Birk wrote: I have a request for the programmers of the weaker than 1800 programs on the 19x19 CGOS (eg. ControlBoy, Explorer, Dog, AverageLib): Please run your program overnight (PDT) once in a while to allow for more precise ratings below 1800. Thanks, Christoph (myCtest) ___ 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] 19x19 CGOS
I'll run Dog if you send me the binary. I have a 3ghz P4 w/ HT online 24/7 -Josh On 6/7/07, Don Dailey [EMAIL PROTECTED] wrote: I noticed there is almost no activity on the 19x19 server. I don't have the computing power to run bots on both servers, but I remember there were some volunteers.If someone would run Dog for me, I would appreciate it. It's a linux program statically linked I think. It is running about 1400 strength and is a worthy opponent for Christoph's program. It would be nice to get some competition going, it doesn't matter if it's playing well below gnugo's level, a lot of program play at that level so it would be great. Someone could also run a weak Gnugo - perhaps with level set from 1-3 or something. To run gnugo at level 2 - ./gnugo-3.7.10-L2 --mode gtp --score aftermath --capture-all-dead --chinese-rules --min-level 2 --max-level 2 --positional-superko - Don On Tue, 2007-06-05 at 14:21 -0700, Christoph Birk wrote: I have a request for the programmers of the weaker than 1800 programs on the 19x19 CGOS (eg. ControlBoy, Explorer, Dog, AverageLib): Please run your program overnight (PDT) once in a while to allow for more precise ratings below 1800. Thanks, Christoph (myCtest) ___ 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] Efficiently selecting a point to play in a random playout
Jacques Basaldúa wrote: Rémi, are your values the result of learning in masters games? Yes. I took data from a learning experiment based on very few games. So there may be a little overfitting. Still, the ratio between the strongest and the weakest patterns is always very big. I'll run some experiments with more random simulations (by exponentiating the gammas by a constant 1). Maybe it would produce better play. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Sylvain and David's paper about Mogo at ICML
Hi, Their paper is available online: http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf I thank Lukasz for letting me know. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
On Thu, Jun 07, 2007 at 09:20:35AM -0400, Don Dailey wrote: Someone could also run a weak Gnugo - perhaps with level set from 1-3 or something. I have put up GnuGo on level 2 as GnuGo-3.7.10-H2. It looks like it is not eating much of my cpu power, so my home server seems to be able to handle both it and the anchor GnuGo. For some reason it starts at a rating of 1800, which may be a bit too much for it. Some day (soon?) when I get my Halgo debugged, I may put it up on 19x19 as well, just to see how badly it does there. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
On 6/7/07, Don Dailey [EMAIL PROTECTED] wrote: I noticed there is almost no activity on the 19x19 server. I can run an old version of housebot (0.4) on the server. It does 1-ply search with heuristics, so its rating would be quite low, but it's almost zero CPU load. It can run 24/7 minus outages due to my unreliable internet connection. It would be nice to get some competition going, it doesn't matter if it's playing well below gnugo's level, a lot of program play at that level so it would be great. In a few weeks, housebot 0.6 will start on the 9x9 server. Probably a week or two after that it'll start on the 19x19 server as well. It'll be a massive CPU hog and will split its time between the various servers. By default, I'd probably end up with a simple shell scripts along the lines of the following: #! /bin/sh while [1 -eq 1] do ./housebot-cgos --server=9x9 --numgames=1 ./housebot-cgos --server=19x19 --numgames=1 ./housebot-kgs --numgames=1 done ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
1800 is the default rating - probably too high. However the K-factor is so high that a single win or loss will make a big difference and it will eventually move to it's natural level. - Don On Thu, 2007-06-07 at 15:39 +0200, Heikki Levanto wrote: On Thu, Jun 07, 2007 at 09:20:35AM -0400, Don Dailey wrote: Someone could also run a weak Gnugo - perhaps with level set from 1-3 or something. I have put up GnuGo on level 2 as GnuGo-3.7.10-H2. It looks like it is not eating much of my cpu power, so my home server seems to be able to handle both it and the anchor GnuGo. For some reason it starts at a rating of 1800, which may be a bit too much for it. Some day (soon?) when I get my Halgo debugged, I may put it up on 19x19 as well, just to see how badly it does there. -H ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
So you basically play 1 game at a time - 1 per server. I suggest that you will play many more games if you play them in bigger batches, perhaps 3 or 4 games each. When you finish a 9x9 game, you will likely have a long wait for a 19x19 games. Could you get a bit more clever? When a 19x19 game is complete, there is a very good chance you have time to play a 9x9 game before the next 19x19 round starts. That of course depends on how quickly housebot and it's opponent plays the 19x19 game and where the 9x9 scheduling point is. Even if you don't get too clever, this might be a better order: while (true) loop N times play a 19x19 game play a 9x9 game endloop play N games on KGS outerLoop The idea is that you might get to play a 19x19 AND a 9x9 in the time it would take to play 1 19x19 game on average. However, if you miss the bus (do not finish 9x9 game before the 19x19 starts) it might be WORSE than some other method. - Don On Thu, 2007-06-07 at 09:41 -0400, Jason House wrote: On 6/7/07, Don Dailey [EMAIL PROTECTED] wrote: I noticed there is almost no activity on the 19x19 server. I can run an old version of housebot (0.4) on the server. It does 1-ply search with heuristics, so its rating would be quite low, but it's almost zero CPU load. It can run 24/7 minus outages due to my unreliable internet connection. It would be nice to get some competition going, it doesn't matter if it's playing well below gnugo's level, a lot of program play at that level so it would be great. In a few weeks, housebot 0.6 will start on the 9x9 server. Probably a week or two after that it'll start on the 19x19 server as well. It'll be a massive CPU hog and will split its time between the various servers. By default, I'd probably end up with a simple shell scripts along the lines of the following: #! /bin/sh while [1 -eq 1] do ./housebot-cgos --server=9x9 --numgames=1 ./housebot-cgos --server=19x19 --numgames=1 ./housebot-kgs --numgames=1 done ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
On 6/7/07, Don Dailey [EMAIL PROTECTED] wrote: I noticed there is almost no activity on the 19x19 server. BTW - A google search for CGOS gives http://cgos.boardspace.net/ as the top hit. That page has a link to http://cgos.boardspace.net/9x9/index.html but not to the 19x19 go server. I know there's no index for it, but even a link to the 19x19 standings page may help people. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
I still have a bunch of work to do on getting this better organized. I don't have simple instructions for running on the 19x19 server (they are buried on [EMAIL PROTECTED] somewhere) and there is still no nice way to download games sets. It's a simple matter of finding the time! But you are right, that may be part of the problem. - Don On Thu, 2007-06-07 at 11:26 -0400, Jason House wrote: On 6/7/07, Don Dailey [EMAIL PROTECTED] wrote: I noticed there is almost no activity on the 19x19 server. BTW - A google search for CGOS gives http://cgos.boardspace.net/ as the top hit. That page has a link to http://cgos.boardspace.net/9x9/index.html but not to the 19x19 go server. I know there's no index for it, but even a link to the 19x19 standings page may help people. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Literature review: where to apply heuristics?
Where are heuristics applied in UCT Go? The following is a review of the literature regarding application of heuristics to UCT Go. It explicitly does not address questions of how the heuristics are generated nor of other algorithmic improvements. Numbers are section numbers within papers. I eagerly look forward to any comments, corrections, or expansions. Peter Drake http://www.lclark.edu/~drake/ Chaslot G.M.J.B., Winands M.H.M. Winands, Uiterwijk J.W.H.M., van den Herik H.J., and Bouzy B. Progressive strategies for Monte-Carlo tree search. 1.3.1: Add heuristic value (divided by # of playouts) to UCT value. 1.3.2: Progressive widening, similar ot Coulom below. Rémi Coulom. Computing Elo ratings of move patterns in the game of Go. 4.1: Heavy playouts, probability distribution. 4.2: Progressive widening in tree, add nth best heuristic move after a certain number of playouts. Peter Drake and Steve Uurtamo. Heuristics in Monte Carlo Go. 4: Heavy playouts, roulette wheel. Sylvain Gelly and David Silver. Combining online and offline knowledge in UCT. 5: Heavy playouts, probability distribution, with noise introduced in a variety of ways. 7: Value of new leaf is initialized by heuristics. Sylvain Gelly, Yizao Wang, Rémi Munos, and Olivier Teytaud. Modification of UCT with patterns in Monte-Carlo Go. 3.2: Heavy playouts, play any move suggested by heuristics, otherwise randomly. 3.4: Ordering of child creation in tree. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Literature review: where to apply heuristics?
On 6/7/07, Peter Drake [EMAIL PROTECTED] wrote: Chaslot G.M.J.B., Winands M.H.M. Winands, Uiterwijk J.W.H.M., van denHerik H.J., and Bouzy B. Progressive strategies for Monte-Carlo tree search. 1.3.1: Add heuristic value (divided by # of playouts) to UCT value. While I haven't done any formal publishing, I have suggested a similar approach where the mean used for UCT is replaced by a weighted average of the traditional mean and a heuristic value.. Essentially x_bar_h = (x_bar_uct * n + heuristic * n_h)/(n+n_h). This is similar to section 1.3.1in the above paper. The last time I posted about it, I didn't know how to modify the full UCB calculation While I don't have my notes in front of me, I think I replaced sqrt(log(n_parent)/n) with sqrt(x_bar_h*(1-x_bar_h)*log(n_parent)/(n+n_h+1)) I started typing up the derivation into something paper-ish, but it's not done and I haven't tried it out in a bot yet to prove how effective it is (or isn't). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Literature review: where to apply heuristics?
By all means, try it out and write up a paper! Peter Drake http://www.lclark.edu/~drake/ On Jun 7, 2007, at 11:25 AM, Jason House wrote: On 6/7/07, Peter Drake [EMAIL PROTECTED] wrote: Chaslot G.M.J.B., Winands M.H.M. Winands, Uiterwijk J.W.H.M., van den Herik H.J., and Bouzy B. Progressive strategies for Monte-Carlo tree search. 1.3.1: Add heuristic value (divided by # of playouts) to UCT value. While I haven't done any formal publishing, I have suggested a similar approach where the mean used for UCT is replaced by a weighted average of the traditional mean and a heuristic value.. Essentially x_bar_h = (x_bar_uct * n + heuristic * n_h)/(n+n_h). This is similar to section 1.3.1 in the above paper. The last time I posted about it, I didn't know how to modify the full UCB calculation While I don't have my notes in front of me, I think I replaced sqrt(log(n_parent)/n) with sqrt(x_bar_h*(1-x_bar_h)*log (n_parent)/(n+n_h+1)) I started typing up the derivation into something paper-ish, but it's not done and I haven't tried it out in a bot yet to prove how effective it is (or isn't). ___ 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] ICAI
Is anyone else here going to the International Conference on Artificial Intelligence in Lost Wages, Nevada later this month? Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/