Author: Robert Hyatt
Date: 06:56:33 09/30/98
Go up one level in this thread
On September 30, 1998 at 00:39:30, Don Dailey 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... > >Which is pretty much how I do it. But my main point actually was how >one should THINK about null move selectivity. Thinking of it this way >is a great simplification and can make it easier to understand. > >My program actually does a null move search with a zero width window >around beta, so I don't actually get to raise alpha. In lots of testing >I did this was more efficient, I don't know if anyone else has tried >this or finds it useful. I also do my test at the top of the search >like you do but after making the move passed to the search function. > My null-search is also with beta-1,beta as the window, because I only care about failing high, and wouldn't trust the null-move to "raise alpha" in those few cases where I am not already doing a null-window search in the PVS code. >The prototype looks like this: > >cilk int main_srch( position *prev, int depth, int update_move ); > > >The code is something like this: > > 1. make update move > > 2. repetition testing > > 3. check hash table and return if possible > > 4. NULL MOVE TEST > > 5. try first move serially > > 6. spawn rest of sibling moves. > > 7. return best move found just like my search now...
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.