Author: Robert Hyatt
Date: 05:46:23 10/01/98
Go up one level in this thread
On September 30, 1998 at 16:59:58, Roberto Waldteufel wrote: > >On September 29, 1998 at 14:12:18, Robert Hyatt wrote: > >>On September 29, 1998 at 11:01:38, Roberto Waldteufel wrote: >> >>> >>>On September 29, 1998 at 10:53:28, Don Dailey wrote: >>> >>>>On September 28, 1998 at 20:02:42, John Coffey wrote: >>>> >>>>>Looking at my copies of old threads maybe I understand better... >>>>> >>>>> >>>>>Just because you're behind in material at a node, doesn't mean you >>>>>won't regain (some of) it in the search below that node. Let's >>>>>imagine that at a node you are behind in material, but are just about >>>>>to deliver mate, and your opponent can't get out of it--even if he's >>>>>given two moves in a row. The null move will return the mate score >>>>>and give you an instant cutoff. Or imagine the oppenent can >>>>>get out of it with those two moves, but only at the loss of a lot >>>>>of material. Again you might get a cutoff. >>>>> >>>>>The null move works as long as the score returned by the null move >>>>>search is greater than or equal to beta. What the current material >>>>>is is...immaterial. >>>>> >>>>>-Dan. >>>>> >>>>> >>>>>>>>>I try them _everywhere_ in the search, before trying any other move. The idea >>>>>>>>>is that if your opponent can't take two moves in a row and crush you, your >>>>>>>>>position is **overwhelming** and doesn't need any further searching to prove that >>>>>>>>>it is probably winning... >>>>> >>>>> >>>>> >>>>> >>>>>...... so even if we are behind in material, a null move search that gives >>>>>my the opposite side two moves in a row could still produce a positive >>>>>result? I.e. I was a rook down, but null move analysis shows that I am >>>>>only a pawn down, chances are I am really crushing the opponent? If so, >>>>>then does this return an evalation that we can use in the tree? >>>>> >>>>>John Coffey >>>> >>>>As was just pointed out to me recently, a simpler way (conceptually) >>>>to view null move searching is to simply look at it as just another >>>>move in the move list. For example, if you have 30 legal moves, then >>>>view the null move (followed by a depth reduced search) as the 31st >>>>move in the list (sorted to the front of course.) Sometimes this >>>>move will give you a beta cutoff, other times it will simply provide >>>>a "best move" which raises alpha and makes the remaining search >>>>faster. >>>> >>>>I don't actually implement it just like this, but this is basically >>>>sound it COULD be implemented this way with no problems. >>>> >>>>- Don >>> >>>Hi Don, >>> >>>I can confirm that this works fine. I recently added null move test in my >>>program, and this is exactly how I implemented it. >>> >>>Best wishes, >>>Roberto >> >>In Cray Blitz, we just added a "0" move to the front of the move list, and >>this does work. But I don't think it is the best way to implement it for >>several reasons: >> >>1. now everytime you try a move you have to ask "is it a null move" and >>if so, reduce the depth by 1 or 2 plies (depending on your "R" value). You >>have to ask this N-1 times which is an efficiency issue. >> >>2. You also have to check to be *certain* that the null move isn't the >>"best" move you found. If you don't, you back up an illegal move and wreck >>things. Another check that is repeated every time you back up a score. >> >>I found it easier, since I wrote Crafty totally from scratch, to have a >>special case at the front of search, where I do the null-move stuff, and >>then I go into the normal "loop" to try the moves one at a time, only if the >>null-move didn't fail high. The code is cleaner and faster and I don't have to >>worry about backing up a null-move as best, for example... > >We seem to misunderstand each other. This is what I do too. Actually, I only >generate one move at a time (no list), so I just slot the null move in at the >beginning before the captures. > >By the way, in a PVS framework, do you know if there is any difference in the >risk of a null move error (eg due to zugzwang) affecting the outcome of the >search depending on whether the null move was made in the PV or not? I wander if >non-PV null moves might be "safer" than PV null moves? If you do it like I do it, where it either fails high or is totally ignored, there seems to be no problem. But if you do it like I did in Cray Blitz, where it is just emitted by the NextMove() function and is searched just like any other move, only to a reduced depth, you can find that a null move is best is a "zug" position. Obviously you don't want to choose a PV with a null-move in it, since that would be illegal and would cause errors later when you reach that position and really have to make a move rather than passing as you'd prefer. If you generate one move at a time, how are you searching the best captures first? MVV/LVA? using SEE can reduce the size of that tree significantly based on tests a couple of us ran 3 years ago... Bob
This page took 0.01 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.