-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Several points:
Null move is usually applied to a beta cutoff - but of course this is mostly semantics. In the literature if you can "pass" (play the null move) and still get a beta cutoff then you are in a fruitless line of play because your opponent has the power to avoid this line of play. Null move is pointless without a depth reduction, otherwise it just adds 1 extra node to this level in many cases. When I played around with null move it only hurt the program some - because it does reduced the tree significantly which partially compensates for the reduced quality of the tree. That gives some hope that it's not totally stupid but it would need some bolstering somehow. Null move is nothing more than a test. If there is some other way to estimate an upper or lower bound on the score, it could be used the same way that null move is. Alpha Beta pruning hasn't been explored to it's full potential in computer GO. Translating a chess program to go by itself is not going to work but in my experience there is some pretty strong evidence that you can be a lot more sloppy about selectivity in Go. For instance you can throw out a lot of moves without it killing the search completely. In chess you have to be paranoid about which move you can throw out. The secret is that you don't throw out any move permanently, unless you can prove admissibility. You taper the search. Perhaps with patterns you can eliminate most of the moves NEAR the leaf nodes, but at some point you have to reintroduce them. Null move is a recursive mechanism to re-introduce moves but we probably need something else in GO. One thing is clear - if alpha beta is to be workable it has to be extremely liberal about pruning moves. - - Don Eric Boesch wrote: > On 10/9/07, Andrés Domínguez <[EMAIL PROTECTED]> wrote: >> 2007/10/9, Eric Boesch <[EMAIL PROTECTED]>: >>> Naive null move is unhelpful because throughout much of a go game, >>> almost every move is better than passing, >> I think this is not the point of null move. Null move is "if pass is good >> enough >> to an alpha cut, then will be a _better_ move". It is not important if >> pass is the >> worse move, is important that there is a better (>=) move than pass (not >> zugzwang). Then you bet searching not so deep. > > Sorry, that was sloppy writing in several places. I was not trying to > argue why null-move pruning (NMP) would give the wrong answer, but > why, even if NMP performs as intended and horizon effects don't spoil > its evaluation, it might not prune many moves. The hope is to prune > variations that are bad and lopsided enough that starting at some > point, one side loses the equivalent of a whole move compared to, er, > more or less, correct play by both sides, right? The fraction of > variations that fit that description will increase with the depth of > the tree and the variability of move quality. The depth and > variability are both likely to be lower in global go search than in > global chess search. (As for local go search, as I already explained, > I think that even if NMP is effective when compared with bare-bones > alpha-beta, it is still less effective than other approaches like > lambda search.) > > If all moves except pass for both players are better than nothing, > then if NMP works as intended, no moves will be pruned in the first > two plies of the search (it takes at least two moves by the same > player to fall a full move behind). If an average move is more than > two-thirds as valuable as the best move -- which is usually true in go > for, very roughly, the first 20 moves of a typical 19x19 game -- > you'll have to go six levels deep before you see many NMP cutoffs > (even if white's sequence is below average and cumulatively a move > worse than best, it may not lose a full move to black's imperfect > responses, so only a minority of 6-ply sequences will be eligible, and > then you have to consider how many of those sequences would be cut off > by alpha-beta anyhow -- I would assume the sequences that NMP might > prune would be cut off by ordinary alpha-beta at a greater rate than > more balanced sequences would be). You won't see NMP cutoffs at the > bottom of the tree, either, because it's too late to prune then. If > NMP doesn't prune much near the root or the deepest nodes, and the > tree is not very deep because the branching factor and static > evaluation cost are high enough that there isn't time to search very > deeply, then NMP isn't doing much, period. I think that is at least > part of what has limited the benefits of null move pruning for > full-breadth global search in go. Selective global search allows > deeper searches, but a good selector should prune away most of the > sequences NMP might otherwise have caught. > > None of this is an argument that NMP would be literally useless, just > that it's unlikely to lead to a dramatic strength improvement. Even in > chess, Chrilly Donninger said NMP was good for, what, 100 Elo points? > The only alpha-beta tweak that can add 400 Elo to a chess program on > its own is transposition tables, and everybody already has those. That > makes it difficult to understand why non-go-programmers are sometimes > so willing to believe that just souping up an alpha-beta search could > turn today's top go programs, which I would say are at about the go > equivalent of class B at 19x19, into the go equivalent of > grandmasters. A simple-but-fast full-breadth alpha-beta go solver > would have even further to go to reach grandmaster level, because it > would need to reach the level of being competitive with the top tier > of extant programs first (which no such program currently is). Either > way, in terms of performance measured in human terms, the jump from > the state of the art to world-champion-caliber play would be a far > bigger leap beyond the state of the art than Deep Thought and Deep > Blue ever made. (The "leap" to dan level, if gaining just two stones > can be called that, surely requires only throwing a little more > hardware at existing programs.) > > Okay, enough of that. If people aren't persuaded by other programmers' > experience trying to map computer chess methods to computer go in a > straightforward way, then they're not likely to be convinced by my > hand-waving arguments either. > > [Regarding programmers' experience: when a top chess programmer > (Chrilly) and a successful go programmer (Peter Woitke) collaborated > on a chess-style go program, the result fell -- at last report, anyhow > -- about 600 Elo points short of the top tier of programs at 9x9, and > presumably much farther short at real go. (The 600 figure is derived > from Chrilly's claims of a 60% success record against GnuGo, and > GnuGo's placement nearly 700 Elo points behind Mogo on CGOS -- 9x9 is > not GnuGo's long suit.) That should dispel any residual hopes that > applying state-of-the-art chess-search techniques to a go program > otherwise short on distinguishing ideas could yield a state-of-the-art > go program, let alone something stronger. (I assume Suzie does have > other distinguishing ideas, but surely it would only be weaker without > them.)] > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHDktPDsOllbwnSikRAoNpAJ4sup2J3uYc8hnQY1NGg8CgWbEcTwCgiyPx MhxAlANrJdla0Sy6ahw50ws= =kx0p -----END PGP SIGNATURE----- _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
