Author: Robert Hyatt
Date: 10:23:18 10/02/98
Go up one level in this thread
On October 02, 1998 at 11:27:36, Roberto Waldteufel wrote:
>
>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
My q-search doesn't find "overloaded pieces". And here's why. For *every*
position you can show me where my q-search screws up and misses an overloaded
piece, I will show you a position where your q-search screws up because the best
reply to a capture is not always a capture. IE a position like this:
+---+---+---+---+---+---+---+---+
8 | R | | | | | | | |
+---+---+---+---+---+---+---+---+
7 | P | P | | P | | | | |
+---+---+---+---+---+---+---+---+
6 | | | | K | | | | |
+---+---+---+---+---+---+---+---+
5 | | | | B | | | | |
+---+---+---+---+---+---+---+---+
4 | | | | | *B| | | |
+---+---+---+---+---+---+---+---+
3 | | | | | | | | |
+---+---+---+---+---+---+---+---+
2 | *P| *P| *P| | | | | |
+---+---+---+---+---+---+---+---+
1 | | *K| *R| | | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
Here it is white to move. In the qsearch, your only choice is Bxd5 which
is an even exchange, and you assume this position is "equal". But I play
Rd1 and you are lost. And since q-searches don't include non-captures, they
make gross mistakes no matter what else you include.
My philosophy is, then, to reduce the q-search to the absolute minimum that
prevents obviously hung pieces, and invest that time in the basic search,
maybe getting an extra ply so that I can find the Rd1 move rather than the
Bxd5 move. I *don't* want my q-search to find cute tactical things, because I
don't trust it. I trust the part of my search where depth > 0 to find the
tactical things, because there I look at everything and extend what seems to
be "interesting". The q-search is *dumb*. *dumb as a rock*. And can't be
trusted to do anything but make mistakes. I try to push those mistakes as far
into the future as possible..
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.