Author: Don Dailey
Date: 21:39:30 09/29/98
Go up one level in this thread
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. 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
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.