[Computer-go] Anomalies in MCTS

Kahn Jonas jonas.kahn at math.u-psud.fr
Mon Feb 4 02:02:23 PST 2013


> Wesley Turner and me are analysing "pure Monte Carlo" (without
> tree search component) in (artificial) simple games.  Let MC(k) be
> the version where each candidate move gets exactly k simulations. We
> found examples where for instance MC(8) performs better than MC(16),
> but for k to infinity pure Monte Carlo plays perfectly.

I guess that what is needed for that is something like:
* a best move
* several bad moves that look good to MC
* even more intermediate moves that look slightly less good to MC.

So that for MC(8), we typically get a move of the third category, for
MC(16), unless lucky, of the secont category, and of course the best
move for MC(\infty).

> Question to the MCTS programmers (in Go): Do you have example
> positions where MCTS makes good move proposals for short run times
> and bad proposals for medium long run times? (Of course for time to
> infinity it should converge to good moves.)

I guess it would be easier still: make a tactical position, where the
opponent has only one road against a bad move. Until the tree finds it,
it will look better than a good move that gives a few points. And if
there are many slightly less good moves that give more points, they will
be preferred at first.

Of course, since we really have time when we have a tree, we could also
probably create a position with "refutations" at different depths, the
move with shorter-depth refutations having less dire consequences.

Now, that's theory-crafting, I have no example to give.

Jonas



More information about the Computer-go mailing list