Author: Roberto Waldteufel
Date: 11:07:19 10/01/98
Go up one level in this thread
On October 01, 1998 at 08:46:23, Robert Hyatt wrote: >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 Hi Bob, Yes, I have indeed been using MVV/LVA to generate captures one at a time. However, I could easily create a list of captures and then process them. With SEE I assume you only consider captures on one square, using a recursive call to evaluate the capture sequence with a stand-pat option like in the qsearch? At what stage do you search captures that are losing according to SEE? One of these may in fact be good. Do you delay searching these, or do you search them along with the other captures? Since I don't generate a move list ordinarily at present, using SEE would represent a certain amount of extra overhead in node processing, so the reduction in nodes searched would have to be worth more to justify it, but it sounds like it is. Another thing for my "things to do list".....:-) Roberto
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.