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