[computer-go] .. if Monte-Carlo programs would play infinite strong

[Magnus Persson]

Quoting Jacques Basaldúa <jacques at dybot.com>:

>
> I am not an MC developer, but as far as I know, UCT keeps a limited 
> (i.e. n-ply) tree
> in memory and intentionally unbiasses the nodes to make the 
> convergence faster, that
> does not change anything, assuming constant tree size.

You have misunderstood UCT. UCT searches to arbitrary depth, and it is 
actually
not possible to say to what depth it does search. Also the evaluation at each
node is the average winrate in the entire subtree, which make it a little hard
to tell exactly what UTC does.


> your play. Of course, if you increase the tree, you reach perfect 
> play, that's not
> the point.

But increasing the tree every simulation *is* the point of UCT.

There are perhaps three types of MC-programs.

1) 1-ply eval of all legal moves.
2) Any kind of alpha-beta/min-max like search to fixed depth (or as deep as
possible using iterative deepening).
3) Best/unexplored-first search that expands the tree as necessary with no
regard for depth.

The difference between 2 and 3 is that 3 tend to find one winning move, 
whereas
2 finds the best winning move. The drawback of 3 is that it may spend a lot of
time on a losing move and misses the winning move.

So with infinite search 2 and 3 will find a winning move if any, but 
the size of
the tree might be very different. Nr 1 will avoid blunders but will reach an
asymptotic level of strength quickly.

Currently 3 is easier to implement than 2, but if move ordering and move
extensions for go become as well understood as for chess then maybe 2 
is better
as the authors of the Mogo team wrote in a recent mail to this list.

A source of confusion is perhaps that when I and several others talks about
MC-programs we think of type 3 because it so superior to type 1, but most
people who tries MC for the first time do type 1 I guess, and in many academic
papers about MC they seem to do something like 1.

If you have not read the UCT page on sensei http://senseis.xmp.net/?UCT 
perhaps
that can clarify things.

-Magnus