-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I don't believe null move pruning will be effective in Go. The basic principle of null move pruning has been described in a couple of ways:
1. threat analysis 2. bounds checking. It does both things - this is more about how to think about it. In bounds checking you are relying on the "null move assumption" which is that it's "always" bad to give up a move. This assumption is more true in Go than it is in chess so that is one argument in favor of null move pruning. The null move test is to play 2 moves in a row for one side and consider the result an upper bound. (or conversely to consider the result a lower bound for the other side.) In order to be a reduction of effort, the null move is combined with a reduced depth search. That's where the trouble begins with Go. More about that in a second. The other way to think about null move pruning is as a "threat test." If I am given 2 moves in a row and I still can't create any problems for my opponent, the assumption is that I have no threats. This is of course combined with a depth reduction effort - the assumption being that with 2 moves in a row, I should be able to create trouble even at a reduced depth. A dangerous assumption in GO! Even in Chess null move pruning can be a problem. It fails most spectacularly in endings and in slow attacks. A slow attack might be a clever knight move, that puts the program one move closer to marching the knight to a critical square on the other side of the board. There are direct threats, there are threats of threats, and threats of threats of threats and so on. Null move pruning (with depth reduction) is GREAT at finding the most direct threats, but cannot see more distant threats. Unfortunately, Go is much like a chess endgame or a slow attack in this regard. A single seemingly innocent move is a powerful but very LONG TERM threat from a finite and limited search point of view. Null move pruning with reductions would fail to consider these moves. The scalable solution is recursive null move pruning, which will pick up all threats eventually if you search deeply enough. This will work in GO, but I'm quite confident that you will need several extra ply of depth to see the same tactics a brute force search would find - and the extra speed is not enough to buy that back. And this will be a very common thing - not like in chess where it still happens, but is relatively rare. It's possible that it could made to work if the evaluation function is really powerful about recognizing long term threat potential - it would have to be really good at statically recognizing life and death as well as being able to sense that life is in trouble. However that's the problem with are trying to solve - this kind of evaluation does not yet exist. - - Don Don Dailey wrote: > I know Hsu from my computer chess days. Of course most of us probably > realize he was on the Deep Blue team. > > I think he is betting on null move proving - but I'm real skeptical that > it will be effective in Computer Go. It will indeed reduce the tree > significantly, but this comes at a qualitative price that is not so bad > in Chess but is a lot in Go. > > I would like to see that kind of hardware (which was described in the > article) applied to 19x19 GO using UCT combined with more research on > UCT, that could produce something that plays in the Dan range, although > I'm very skeptical it will be in the "high Dan" range, certainly not the > stronger than any human player. > > Having said that, one must be very careful about making predictions, > lest one ends up with egg on their face. Computer chess started with > wild optimism, then extreme pessimism then big surprise! I clearly > remember the days when it was ludicrous to imagine chess computers ever > touching even the weak masters. It was just not possible and a simple > calculation on a paper napkin proved that it could never happen. Woops! > In those days you were considered an idealistic fool if you were > optimistic but it turns out the optimistic ones were the most realistic > and the ones who were objectively "reasonable" and pragmatic were the > fools. > > I never did scaling experiments on 19x19 with UCT, but I have no reason > to believe it would not show the same amazing scaling curve. Lazarus > is so weak at 19x19 that it would take a few doublings of speed to get > competitive with reasonably good programs. > > Has anyone else done scaling experiments with 19x19 and UCT? > > - Don > > > Ian Osgood wrote: >> Greetings, > >> I noticed that the following link was recently added to the Computer Go >> Wikipedia article. > >> http://www.spectrum.ieee.org/oct07/5552 Cracking Go, by Feng-hsiung Hsu, >> IEEE Spectrum magazine, October 2007. > >> He claims it should be possible to build a Go machine stronger than any >> human player. > >> Ian >> _______________________________________________ >> 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/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHAnFwDsOllbwnSikRArBkAJ9gkK9UKu4/Sn/AUnY5wgUDWZ8N8gCggR5a FaDaTkDgBhk3cxdxCjkA3qk= =Rbm3 -----END PGP SIGNATURE----- _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
