Fred,
others have already indicated that you are missing the "tree" part of
Monte Carlo Tree Search, but there is something else to add.
If you run uniform random playouts on an empty 9x9 board, let's say a
million of them for each point, you will see a probability distribution
emerging that roughly shows the centre 3x3 or 4x4 points as having a
high probability of winning (around 50%, depending on komi), and you
will see the edges and first line having a much lower probability.
This is not going to help you choose between the points in the centre.
Every time you run the simulation, a different point will be selected as
"best" - because the state space will be inadequately explored, as you
say - but you will be able to choose a good move.
On 19x19, the space is so inadequately explored that running a uniform
Monte Carlo simulation on an empty board is useless (i.e. you will get
completely different results every time you run it) and further
heuristics either during playouts or during the tree search phase are
needed.
Christian
Fred Hapgood wrote:
I have a really basic question about how MC works in the context of Go.
Suppose the problem is to make the first move in a game, and suppose we
have accepted as a constraint that we will abstain from just copying
some joseki out of a book -- we are going to use MC to figure out the
first move de novo. We turn on the software and it begins to play out
games. My question is: how does the software pick its first move? Does
it move entirely at random? Sometimes it sounds that way MC works is by
picking each move at random, from the first to the last, for a million
games or so. The trouble is that the number of possible Go games is so
large that a million games would not even begin to explore the
possibilities. It is hard to imagine anything useful emerging from
examining such a small number. So I'm guessing that the moves are not
chosen at random. But even if you reduce the possibilities to two
options per move, which would be pretty impressive, you'd still run out
of your million games in only twenty moves, after which you would be
back to picking at random again.
What am I missing??
http://www.BostonScienceAndEngineeringLectures.com
http://www.pobox.com/~fhapgood
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
--
Christian Nentwich
Director, Model Two Zero Ltd.
+44-(0)7747-061302
http://www.modeltwozero.com
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
