Hi!
On Tue, Oct 27, 2009 at 12:05:57PM +0200, Petri Pitkanen wrote:
> Are there more peculiar situation that will cause problems for MCTS apart
> from the three I know.
> 1. Nakade (this is partuially solved in most of the programs)
> 2. Semeais
> 3. Double Ko.
Yes, these are all just particular instances of a general class; it
shows up in fights at many points. They all manifest as a problem where
the simulations introduce a massive bias in the particular situation,
misjudging life of certain group, usually where there is one right move
and many bad ones in the position (right one will be played only with
small probability).
This causes what I call the "horizon effect" which prevents the
tree exploration to work properly - the moment the tree finds a sequence
that unbiases the simulations, it is horrified by the bad results [*] and
switches to a different branch, until it finds the same; thus, the bot
pushes the resolution (unbiasing) of the situation over the tree horizon
for as long as possible. This shows in actual games as the bot playing
random throwins and obviously pass moves before resigning.
In case of nakade, the bias is introduced by anti-self-atari
heuristics in the playouts and is probably indeed largely solved by
smarter self-atari detection. In case of various kos, perhaps a
simulation bias for re-taking the ko could help, but this is probably
fairly simple. In case of semeai, the bias is obvious and the solution
is currently totally unobvious.
There are two ways to deal with this - removing the bias from the
simulations by increasing the intelligence within cautiously, and
finding a way to deal with the bias in the tree. I'd say so far all
improvements of simulations since uniform playout could be described
as trying to solve this problem, and to a certain point it greatly
helps increase the convergence to good result, but I think we are behind
that point now and making the simulations smarter is now only pushing
away the inevitable.
I don't know how much hidden ongoing research is being done about
dealing with the bias in the tree, the only result so far I'm aware of
is Remi Coulom's criticality heuristic, and it wasn't that effective;
I personally have some clear ideas I want to start experimenting with as
soon as possible - I think we need a top-down counterpart for the
bottom-up propagation function of RAVE. IMHO a substantial progress
in this direction is the next big thing to happen in computer go.
[*] "Bad results" for the parent node owner - I have seen the bias
as being both unduly positive _and_ unduly negative, though the latter
seems fairly rare - I think I saw it only once in a rather complicated
large temporary seki fight and while the bot obviously won it, the
percentages were horrible, it was lucky they stayed above the resign
threshold until the situation finally got resolved.
--
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
