Author: Don Dailey
Date: 11:00:57 02/08/98
Go up one level in this thread
Hi Christophe, I was going to make the same basic post you did but now I don't need to! In my opinion all the good programs use some form of (what you call) the null move observation even if they are not doing a literal null move. I have analyzed Marty's program and he seems to focus primarily on the quies search which is really based on resolving all kinds of attack sequences and checks. There are some tricks here that go beyond null move observation but I cannot legally talk about them. Probably most of you are aware of them anyway but there are more pruning techniques than just NMO, although I don't think they are used much. In my program I use a static attack test near leaf nodes of the main search (but I'm not talking about quies like Bob does.) This has proven to be MUCH better than null move if used only on last 1-3 ply. If I go back farther it starts becoming worse. The success of the algorithm is based on the fact that it's better in some ways than the null move assumption. This is because the null move assumption doesn't take into consideration that most of the time you get something back for your trouble, even if you do lose the attacked piece. My static routine does, so I get a big speedup. Qualitatively it's not quite as good, but there are many cases where it see's things a null move misses. Probably the main reason it fails at deep levels is that it is incapable of finding deep threats. Also in king and pawn endgames I thrown out all null move prunning and go into something I consider much better. It's MUCH better than killing selectivity altogether (which some programs do) or limiting the hell out of it. AGAIN though, it's based pretty much on similar principles. It's based on observations about how many ply would be required to win pawns or get a passed pawn. It's not perfect but is much better than null move because it can measure long term threats without dropping plys. And Zugzwang is a non issue. You can control how aggressively it prunes by how aggressive your assumptions are. I added this routine after the Dutch Championship where we should have lost a game to Nimzo but didn't due to a poorly played king and pawn ending. We now see deeper AND more accurately in king and pawn endings. In my humble opinion the terminology should be something like "measuring threat potential" instead of "null move observation." This phrase more accurately conveys what is really going on. It's more general but would be truly domain independant (unlike null move) since the principle could be applied to other games. Basically if you have any way of accurately estimating a bound on the score in any game (2 player, perfect information, advisarial) you have a mechanism for implementing selectivity. With chess, null move works fairly well. - Don On February 07, 1998 at 22:52:34, Christophe Theron wrote: >On February 07, 1998 at 19:49:58, Robert Hyatt wrote: > >>On February 07, 1998 at 18:48:18, Thorsten Czub wrote: >> >>>>I'm not so sure. Ed has said "no null move" for Rebel. I believe Marty >>>>said the same about Mchess. Looking at Hiarcs output, it seems that it >>>>doesn't either, based on the depth of search reported... >>>>The only one I >>>>am certain about if Fritz, of course, that is a known null-mover. Bruce >>>>and I are also big users of course. I've used it since Beal's first >>>>paper >>>>on the subject in 1980-81 or so... >>> >>>If null-move is so beuatiful and works so effective and without >>>overseeing important stuff, and gives more depth , why do you think is >>>rebel and mchess and hiarcs not using it ? >>>How can rebel9 and hiarcs6 lead the ssdf-list without null-move? >>> >> >>null move is a form of forward pruning, but not the only form. The >>advantage for null-move is that it is a "domain independent" form or >>pruning... it has nothing to do with chess and works just as well in >>other games. One simple comparison is current Crafty vs Blitz IV, circa >>1977 or so. The code that selects moves to search (or, which moves to >>toss out, depending on your perspective) was over 30,000 lines of code. >>The search for Crafty, in contrast, is a few hundred lines at best. So >>the attractiveness, for me, is that it lets me write a simple, bug-free >>search, and get on to other things. It exhibits a failure here and >>there. >>So does Rebel and the others. My thinking is that if I am going to have >>to >>accept errors here and there, I'd just as soon do it with the simplest >>code >>I can. > >The "null move observation" (NMO) can be used in other ways than just >doing a null move. > >I call the "null move observation" (NMO) the fact that in chess, with >little exceptions, there is always a move that is better than doing >nothing (which is not allowed, but let's skip this detail). Please note >that this is not very "domain independent". For example, NMO doesn't >apply to Othello/Reversi. > >When you understand this brilliant idea, you can write different >algorithms to use it. > >Real null movers really do a "null" move, and call the search >recursively to see if the opponent can do something wrong to them. If >not, and if the score of this null move is "enough", they stop studying >the variation. The move just before the "null" is not a very good one, >since you refute it by doing nothing! > >I think every chess player uses this idea. When I analyze a position, I >often imagine I can do several moves in a row, with no reply from my >opponent. If this sequence of move does nothing, it's not worth thinking >about it any more. This is the case when you try to figure out how to >attack the opponent's king: "First, I move my knight near the king, then >I move my queen to threaten mate". If this works, you start thinking >about: "now, what can the opponent do after I move my knight to stop the >attack?". > >But there are others ways to make a good usage of the NMO. > >For example, you can just look at the position with your static exchange >evaluator to see if you have a piece "en prise". If the score of the >position is very good for you (eval>=beta) and your opponent doesn't >make any threat, it's not useful to study this line (the opponent's >previous move(s) was(were) not very good). Do this kind of pruning only >when you are quite deep in the search, because it is less accurate than >a real null move! > >Another related pruning technique is "Fail High Reduction". If the score >of the position is very good for you (eval>=beta) and your opponent >makes no threat, instead of pruning the line you just decrease the >search depth a little bit. Your search is faster, and (I hope) you make >few errors. This is described by R. Feldmann in "Advances in Computer >Chess 8". > >As you see, the general idea behind null move and a huge familiy of >pruning techniques is trying to detect the threats. > >I would bet that many people claiming that they don't use null move are >only playing with the words. They use some kind of algorithm, like the 2 >mentionned above, that is only a variation around the "null move >observation". > >I think that no serious chess program can be written without taking >advantage of the NMO. Of course, you see which programs I am thinking >about. > >There are other ways to do forward pruning, but I think you can use them >together with the NMO pruning. > >BTW, we can reach here the old debate between fast and slow programs. A >"real" null mover does not have to evaluate threats statically, so >doesn't need to use a (always slow) exchange evaluator. A program taking >advantage of the NMO by evaluating threats in every node will be slower, >but will look at less nodes. > >But the two are in fact using the same idea, and from my experience it's >not clear which way is the best. You can talk about it forever. IMO the >only point is to realize the power of the NMO idea. > > > > >>>Could we discuss null move, or is null move so SURE that we don't have >>>to discuss it ? And if it is so sure, why the hell don't they use it >>>?!!? > >I think they use NMO, which is the same idea. They can also use other >tricks, of course. > > > > > Christophe
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.