On Tue, 2008-12-23 at 10:15 +0100, Rémi Coulom wrote:
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 ?
You don't back up a value to the parent, you use it as a test. The idea
behind null move is to prune the tree early and null move is just a
device to decide that it's ok to stop searching - it could just as well
be anything else that detects threats. It just happens that null move
is a pretty good way in some domains. You generally apply null move in
any position where you believe the true score is greater than or
equal to beta, which is where you would get a cutoff anyway. As
Gian-Carlo mentioned you make a null move first because you are
basically seeing if the position is so good that you can afford to do
nothing and the opponent still cannot hurt you.
The reduced depth search you do could be a problem in Go. Null move is
not as effective in positions where there are deep long term threats.
It's more effective in tactical situations and is ideal in Chess. But
even in chess endings it is not quite as effective, but still works
well.
So it has to be evaluated for GO. Apparently, some have reported
success with it in GO.
Gian-Carlo is right about it not being just for alpha/beta - it can be
used as a device to measure threat potential in a position.
I have this feeling that it would work better if your program already is
very good at evaluating threats and problems in the position - because
in GO, null move (and it's reduced depth test search) can lose depth.
In a chess program null move will make your program take extra depth to
solve positions where the threat is not so direct. YMMV.
- Don
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/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
