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/
