Author: Roberto Waldteufel
Date: 08:27:36 10/02/98
Go up one level in this thread
On October 01, 1998 at 17:53:41, Robert Hyatt wrote: >On October 01, 1998 at 14:07:19, Roberto Waldteufel wrote: > >> >>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? >> > > >my code is a good bit simpler. I simply enumerate the attackers and >defenders for the target square, in the best order possible but preserving >order when pieces are lined up like a queen behind a rook, and then play out >the sequence of captures (not a tree search at all, just least valuable >piece captures first, etc.) and then minimax this to decide when one side >or the other would chose to stop in order to not make the score worse. > > > > > >>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? > > >in the q-search, never. In the normal search, as the last group of moves >are searched (after hash, winning/even captures, killers and up to 4 >history moves). The losing captures come in the next group of moves. > > > >> >>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 > > >always try it first, of course... YMMV... You don't search apparantly losing captures in the qsearch? I search *all* captures in the qsearch, since the capture frequently will decoy another piece away from the defence of a target elsewhere, or the defending piece might be pinned to another piece. How does your qsearch find these tactics? When I was first experimenting with chess programming I remember trying something similar to the SEE (but mine was recursive) and getting some very big errors in the values returned from the qsearch, but when I started looking at all the captures it settled down somewhat. Maybe I was doing something silly in another part of the search code, but the "complete" qsearch certainly seemed to help at the time. Of course many of these captures are indeed very silly, but the "stand pat" option seems to nip the explosion of bad captures in the bud most of the time. Still, no search is faster than some, so if you have found a solution to the decoy/pin type of problems, I would be very interested to hear about it. Best wishes, 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.