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.
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/
