Re: [computer-go] Nullmoves in MCTS and UCT?
Gian-Carlo Pascutto wrote: Rémi Coulom wrote: Did you manage to get something to work with null move ? When Leela runs the first simulation in a node, it plays 2 moves for the same side, then does a playout. If the playout loses for the not-passing side, I add x lost games to the RAVE values. I got maybe 10 ELO or so from this. If someone can improve upon it, I'm all ears. Thanks Gian-Carlo, that's an interesting idea. Now I see how it can be done. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Nullmoves in MCTS and UCT?
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/
Re: [computer-go] Nullmoves in MCTS and UCT?
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/
Re: [computer-go] Nullmoves in MCTS and UCT?
Rémi Coulom wrote: Did you manage to get something to work with null move ? When Leela runs the first simulation in a node, it plays 2 moves for the same side, then does a playout. If the playout loses for the not-passing side, I add x lost games to the RAVE values. I got maybe 10 ELO or so from this. If someone can improve upon it, I'm all ears. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Nullmoves in MCTS and UCT?
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. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Nullmoves in MCTS and UCT?
I tested null move pruning in my classical alpha-beta Aya. Depth first, iterative deepening. Search depth is 6 or 7 in middle game. 3 seconds/move. NPS is about 7000/s on CoreDuo 1.83GHz (one core). Against GnuGo 3.7.10 on 9x9 R=2 wins losses winning rate withnull move 126 174 0.42 without null move 108 192 0.36 As far as my program, null move pruning is maybe a bit effective. Hiroshi Yamashita - Original Message - From: David Fotland fotl...@smart-games.com To: 'computer-go' computer-go@computer-go.org Sent: Sunday, December 21, 2008 1:35 PM Subject: RE: [computer-go] Nullmoves in MCTS and UCT? Many Faces of go uses alpha-beta full board search with null move for the levels that don't use monte carlo search. Monte carlo search is used in the 2 kyu level. Alpha beta is used by 4 kyu to 9 kyu. The weaker levels just do a single ply search. Null move helps, but I never tested how much it helps. David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Nullmoves in MCTS and UCT?
Ingo Althöfer wrote: Question: Have nullmove-concepts been tried or analysed in MCTS or UCT-settings? Background of the question: Using alpha-beta tree search, the (asymptotic) percentage of nullmove cutoffs may help as an indicator for the naturality or interestingness of a (newly invented) game. Unfortunately, it is nontrivial to design traditional evaluation functions for newly invented games... Ingo. 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. Still, some programmers tried null move in 9x9 alpha-beta go programs. As far as I remember, they got no strength improvement from it. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Nullmoves in MCTS and UCT?
On Sat, 2008-12-20 at 16:04 +0100, Rémi Coulom wrote: Still, some programmers tried null move in 9x9 alpha-beta go programs. As far as I remember, they got no strength improvement from it. I tried null move once in my very weak alpha/beta go program. The issue with recursive deep search null move is that it is not that good and discovering long term threats, which is way more common in GO than in chess.However, it might work well for discovering certain classes of immediate tactical threats that must be responded to. As a general pruning mechanism, I fear it is not very workable - but I never say never. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Nullmoves in MCTS and UCT?
Many Faces of go uses alpha-beta full board search with null move for the levels that dont use monte carlo search. Monte carlo search is used in the 2 kyu level. Alpha beta is used by 4 kyu to 9 kyu. The weaker levels just do a single ply search. Null move helps, but I never tested how much it helps. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go-boun...@computer-go.org] On Behalf Of Rémi Coulom Sent: Saturday, December 20, 2008 7:04 AM To: computer-go Subject: Re: [computer-go] Nullmoves in MCTS and UCT? Ingo Althöfer wrote: Question: Have nullmove-concepts been tried or analysed in MCTS or UCT-settings? Background of the question: Using alpha-beta tree search, the (asymptotic) percentage of nullmove cutoffs may help as an indicator for the naturality or interestingness of a (newly invented) game. Unfortunately, it is nontrivial to design traditional evaluation functions for newly invented games... Ingo. 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. Still, some programmers tried null move in 9x9 alpha-beta go programs. As far as I remember, they got no strength improvement from it. 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/
