Gian-Carlo Pascutto wrote:
Rémi Coulom wrote:
Null-move pruning only make sense in alpha-beta. MCTS/UCT are more like
min-max. They do no alpha-beta pruning, so cannot do null-move pruning.
Null move works like this: if after passing and a small search the
position still looks good, do not do a bigger search.
There is absolutely no reason why this can't be used in MCTS/UCT. You
will have some implementation differences, of course.
The problem I see is that null move gives a lower bound on the value of
a node in the tree. What value would you back-up to the parent ? If that
node is given the value of the null move, then it means that the value
of the move that leads to this node will be over-evaluated by the
parent. So, it will be explored more with a MCTS algorithm. It would
seem more effective to me to play a better real move, get a better value
for this node, which will make it more effectively pruned at the parent
level.
Or do you mean that you would prune the node completely after a
null-move search ? That sounds too dangerous. I can't see how it could
be done.
Pruning in MCTS works by estimating how better on move is than another.
With null move, you lose much of that information. I may be wrong, but
this makes me believe that null-move pruning is not compatible with the
spirit of MCTS.
Did you manage to get something to work with null move ?
Rémi
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/