Author: Alessandro Damiani
Date: 08:29:04 09/10/99
Go up one level in this thread
On September 10, 1999 at 09:36:51, Robert Hyatt wrote:
>On September 10, 1999 at 08:01:35, Alessandro Damiani wrote:
>
>>On September 10, 1999 at 07:48:44, Ed Schröder wrote:
>>
>>>On September 10, 1999 at 00:19:37, Robert Hyatt wrote:
>>>
>>>>Here is an interesting position given to me by Steffen Jakob:
>>>>
>>>> /p/P5p/7p/7P/4kpK/// w
>>>>
>>>> +---+---+---+---+---+---+---+---+
>>>> 8 | | | | | | | | |
>>>> +---+---+---+---+---+---+---+---+
>>>> 7 | *P| | | | | | | |
>>>> +---+---+---+---+---+---+---+---+
>>>> 6 | P | | | | | | *P| |
>>>> +---+---+---+---+---+---+---+---+
>>>> 5 | | | | | | | | *P|
>>>> +---+---+---+---+---+---+---+---+
>>>> 4 | | | | | | | | P |
>>>> +---+---+---+---+---+---+---+---+
>>>> 3 | | | | | *K| *P| K | |
>>>> +---+---+---+---+---+---+---+---+
>>>> 2 | | | | | | | | |
>>>> +---+---+---+---+---+---+---+---+
>>>> 1 | | | | | | | | |
>>>> +---+---+---+---+---+---+---+---+
>>>> a b c d e f g h
>>>>
>>>>
>>>>Obviously black is getting crushed. He has one move, Kh3, which leads to a
>>>>mate in 6. Steffen asked me to try this and Crafty found a mate in 4, which
>>>>doesn't exist. I spent the entire day debugging this thing and here is what
>>>>I found:
>>>>
>>>>If you recall the discussion here a couple of weeks ago, I reported that I store
>>>>absolute mate scores (EXACT scores) in the hash table, and that I adjust them
>>>>so that they are always stored as "mate in N from the current position". This
>>>>has always worked flawlessly for me, and still does.
>>>>
>>>>For bounds, I once tried adjusting the bounds as well, but found quirks, and
>>>>left them alone. Wrong answer. To fix this mate in 4 problem, I decided to
>>>>adjust the bounds as well, but I now set any bound value that is larger than
>>>>MATE-300, by reducing it to exactly MATE-300, but still using the "LOWER"
>>>>flag to say that this is the lowest value this position could have. For bound
>>>>values < -MATE+300, I set them to exactly -MATE+300 and leave the flag as is.
>>>>
>>>>This position is cute. Because not only is it a mate in 6, but there are
>>>>transpositions that lead to mate in 7, mate in 8, and there are shorter (but
>>>>non-forced) mates in 4 and 5. And there are stalemates, and positions with
>>>>1 legal move, and so forth.
>>>>
>>>>You ought to find the following variation as one mate in 6:
>>>>
>>>>Kh3, f2, Kg2, Ke2, Kg3, f1=Q, Kh2, g5, hg, Kf3, g6, Qg2#
>>>>
>>>>If you find a shorter mate, it is wrong. If you find a longer mate, you
>>>>are probably just extending like mad on checks (crafty finds a mate in 8 at
>>>>shallow depths (9 plies, 2 secs on my PII/300 notebook), and doesn't find the
>>>>mate in 6 until depth 10, 3 seconds.
>>>>
>>>>It is a good test as the transpositions are real cute with white's king caught
>>>>in a tiny box, but with several different moves that triangulate and transpose
>>>>into other variations...
>>>>
>>>>If you get it right, you have either handled the bounds right, or else you are
>>>>very lucky. IE Crafty 16.17 gets this dead right. But if I disable the eval,
>>>>it goes bananas, yet the eval is not important when mate is possible.
>>>>
>>>>Have fun...
>>>>
>>>>I did... :)
>>>
>>>A simple solution: do not store a position in the hash table if there is
>>>no best-move. It solves the mate-cases and also repetition cases. Also
>>>there is no speed loss of the search.
>>>
>>>Ed
>>
>>Do you mean by "no best-move"
>> bestmove == 0
>>or
>> best<=alpha, after having searched all moves (best: minimax score)?
>>
>>What I do:
>> if bestmove == 0 then don't store anything, just return the score (mate or
>> stalemate).
>>
>>Alessandro
>
>
>that doesn't make sense to me. If _every_ move at one node in the tree returns
>alpha for the score, which is the best move? And since you don't have one, you
>don't store anything? That hurts performance, because the next time you
>encounter this position, you get to search it again, while I discover that the
>last time I searched it I returned alpha, so I can just do that now and not
>search anything...
No, no. My answer was misleading. What I mean is explained by the following code
(the code is simpilied!). I have marked the important things by an "****". It is
assumed that
- when the king is removed from board its position is -1 ( < 0)
- alpha, beta < INF
Alessandro
int AlphaBeta (int alpha, int beta, int depth) {
//**************************************
// legality check:
if (myKingSquare<0) return -INF;
//**************************************
if (depth==0) return Quiescence(alpha,beta);
// here use info from the transposition table
best= -INF; bestmove= 0; startalpha= alpha;
i= 0; n= GenMoves();
while (i!=n && best<beta) {
// m[i] is the current move
make(m[i]);
value= -AlphaBeta(-beta,-alpha,depth-1);
unmake(m[i]);
if (value>best) {
best= value; bestmove= m[i];
if (best>alpha) alpha= best;
};
i++;
};
//**********************************************
// no best move => mate or stalemate
if (bestmove==0) {
if InCheck(Me) return -MATE+ply;
return STALEMATE;
};
//**********************************************
// here update the transposition table
return best;
}
This page took 0.02 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.