I think I added a small capture bias, but it didn't make much difference. Sorry, I forgot that it isn't quite pure random. Before the uniform random, if there is an enemy one liberty group on the board, with some small probability, I capture it.
A pattern includes don't cares and is matched in any orientation. The 3x3 patterns are only matched adjacent to the last move (8 local places). David > -----Original Message----- > From: [EMAIL PROTECTED] [mailto:computer-go- > [EMAIL PROTECTED] On Behalf Of Jason House > Sent: Sunday, November 16, 2008 5:06 PM > To: computer-go > Subject: Re: [computer-go] FW: computer-go] Monte carlo play? > > On Nov 16, 2008, at 11:18 AM, "David Fotland" <[EMAIL PROTECTED] > games.com> wrote: > > > I thought Valkyria does local search (ladders) during the playouts. > > > > Many Faces is lighter on the playouts. I have 17 local 3x3 > > patterns, then > > go to uniform random without filling eyes. > > > No capture bias in the playouts? I thought that was a big strength > boost. > > Out of curiosity, how do you count your patterns. For example, is it > still one pattern if it includes a don't care? How about rotations/ > reflections of the same basic pattern? > > > > > > > > Against Gnugo 3.7.10 level 10 on 9x9, with 5000 playouts, I win 92%, > > so our > > performance is similar. I'm doing 23K playouts per second on my 2.2 > > GHz > > Core 2 Duo, so my performance might be a little better, depending on > > the > > specs of your old machine. > > > > David > > > >> -----Original Message----- > >> From: [EMAIL PROTECTED] [mailto:computer-go- > >> [EMAIL PROTECTED] On Behalf Of Magnus Persson > >> Sent: Sunday, November 16, 2008 5:45 AM > >> To: computer-go@computer-go.org > >> Subject: Re: [computer-go] FW: computer-go] Monte carlo play? > >> > >> Quoting Hideki Kato <[EMAIL PROTECTED]>: > >> > >>> Heikki Levanto: <[EMAIL PROTECTED]>: > >>>> The way I understand it, modern Monte Carlo programs do not even > >>>> try to > >>>> emulate a human player with a random player - obviously that > >>>> would not > >> work. > >>> > >>> I believe CrazyStone's use of patterns does so and it seems > >>> successful. > >> > >> With Valkyria I try to follow two principles in heavy playouts. > >> > >> > >> 1) In contact fights there are a lot of shapes that are played most > >> of > >> the time. Thus Valkyria checks each move played if there is an > >> obvious > >> local response to it. If so it plays it deterministcally. In many > >> situations there are two or more such candidates and then it plays > >> one > >> of those moves. > >> > >> 2) In many positions the last move played does not trigger any > >> obvious > >> response, and then a random move is chosen uniformly > >> > >> 3) There are moves that are inferior 100% of the time both locally > >> and > >> globally. These moves are pruned if they are selected and a new > >> random > >> move is chosen as long as there are moves left to try. > >> > >> I got hundreds of handcoded patterns for both 1 and 3. It would be > >> too > >> time consuming to test these patterns, so I use my knowledge and > >> intuition (European 2 Dan) to simply decide what patterns to include. > >> > >> So Valkyria has a lot of go knowledge, but mostly such knowledge that > >> all go players have up to some strength such as perhaps 8-10 kyu. It > >> has no knowledge about global matters. The beauty of MC-evaluation is > >> that globally strong moves are most of the time evaluated better than > >> globally weak moves. Heavy playouts removes noise from MC-evaluation > >> and makes it more sensitive to the true value of moves. Still there > >> are biases with all heavy playouts, but they are overcome with MC > >> Tree > >> Search (MCTS) that corrects mistakes in the evaluation recursively. > >> > >> Here are my latest scaling experiment on 9x9 for Valkyria. > >> > >> Valkyria plays 1150 random games per second on my 4 year old laptop. > >> > >> This test is against gnugo 3.7.10 assumed to be Elo 1800. Most > >> datapoints are based on 500 games. "N sims" means Valkyria playes N > >> heavy playouts per move played. Winrates are in %. > >> > >> N sims WinRate Elo (rel Gnu) > >> 47 7.4 1361 > >> 94 22 1580 > >> 188 37 1708 > >> 375 53 1821 > >> 750 69.9 1946 > >> 1500 81.2 2054 > >> 3000 88 2146 > >> 6000 92.6 2239 > >> 12000 94 2278 > >> 24000 97.2 2416 > >> 48000 97.4 2429 > >> > >> the heavy playouts of Valkyria needs just 375 random games per move > >> to > >> match gnugo using only 0.3 seconds per move. And even using only 47 > >> simulations per move it can still win. > >> > >> So obviously the heavy playout code of Valkyria is much weaker (< Elo > >> 1361) than Gnugo and most human opponents, but compared to CGOS a lot > >> of programs witho no knowledge are about the same level, although > >> they > >> uses 2000 simulations or more. > >> > >> Searching efficiently using MCTS with AMAF it apparently can be made > >> arbitrarily strong. > >> > >> Hope this explains how both the nature of playouts and the MCTS > >> contributes to the playing strength of a program. > >> > >> Should one go heavy or light? I do not know, I feel that Valkyria > >> is a > >> little bit too slow on equivalent hardware against most top programs. > >> On the other hand I think it could be tweaked and improved upon. > >> Perhaps it can even be made faster by removing code that does not > >> improve playing strength. And there is probably still room for adding > >> code that improves strength without a noticable slowdown. > >> > >> I just know that is a lot of hard work doing it the way I did it. > >> > >> Best > >> Magnus > >> _______________________________________________ > >> 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/
