Heikki's answer is close. I would think it important to add that MC is a
statistical sampling algorithm, so the attempt is to simplify the
difficult
job of evaluating a board state by sampling a large number of random
continuations, with the assumption that if enough samples are checked,
you will have some idea of the likely outcome starting at that board.
Any
one continuation is of virtually no value, it is only the statistics
that are
meaningful.
By substituting "board state plus one more move" for "board state" you
get an estimated value for the move you are adding to the board as
long as you start the random sequence many times with that particular
move.
Now my personal bias: This method is extremely valuable and accurate
in physics because we have a very solid theory for determining the
distributions in thermal or quantum systems. This means that we do
not simulate every possibility with equal probability, but use a bias
that
is specified by equations we trust and that have proved to work. The
problem in Go is that we have no such theory yet, so, we end up with
hand-tuned rules and biases created by other means, such as a UCT
tree, to slowly and somewhat inefficiently (compared with having the
right bias from an equation) move from what is being called "pure MC"
(but really means uniform random) sampling towards a bias better for
Go.
Cheers,
David
On 30, Oct 2007, at 9:58 AM, Heikki Levanto wrote:
On Tue, Oct 30, 2007 at 12:43:35PM -0400, Joshua Shriver wrote:
There has been a lot of talk about monte carlo and while I have the
jist not sure exactly what it is? Would someone explain it?
Here is my (amateurish) understanding:
Evaluation of a go position is very difficult. Monte Carlo (MC) is
one way to
shortcircuit this. The idea is to play the game to the bitter end,
very
quickly, and badly, on the assumption that if the position favours
white,
then white is likely to win, even if both players play equally bad
quality
moves. Taken to the extreme, they play pure random games. This can
be done
very quickly, and doing it many times gives some sort of measure of
how good
the position is.
Now all is left for a pure MC player is to try every legal move,
evaluate
them with enough MC playouts, and choose the one that is most
likely to win.
This works surprisingly well, although there are some drawbacks.
Evaluating
positions this way prefers safe, solid groups. And in the end game,
when the
result is decided, the programs play unnatural moves, since all
moves lead to
the same result - the resulting score is usually not considered, so
to the
program it is the same if it wins by 0.5 points or the whole board...
On its own MC is not all too strong, but it solves the evaluation
problem.
This can be included in some tree-search based programs, most
commonly UCT or
similar. And the results are surprisingly good.
Lukasz Lew has written a simple C library that makes it easy to
experiment
with the thing. Google on 'Lew libEGO' and you should find him.
- Heikki
P.S. If any of the above is not right, I am sure the better
informed people
will rush in to correct me. I welcome that!
--
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/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
