Author: Ed Schröder
Date: 12:58:45 09/10/99
Go up one level in this thread
On September 10, 1999 at 13:17:57, Robert Hyatt wrote:
>On September 10, 1999 at 11:29:04, Alessandro Damiani wrote:
>
>>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;
>>}
>
>
>Same question as before. The above simply doesn't work as you think it
>does. Here is why.
>
>at ply=N you set best to -inf, and then step thru each move and do a search
>after making it. And you pass that search a value for alpha and beta that is
>used to terminate the search when it can prove that the score below that move
>is >= beta (which at our ply=N node means the move we tried is <= alpha.)
>
>So lets assume that after we search the first move, we get a score back that
>is obviously > -infinity, but < alpha. You remember that move as "best". But
>the problem here is that the 'proof' search stopped as soon as it found a score
>> beta. It didn't try _all_ moves to get the largest score > beta, just the
>first score > beta... which is why we refer to the search as returning a bound.
>At least as low, but maybe even lower.
>
>So you end up with a bunch of random bounds that are all <= alpha, and you take
>the largest one and assume that is the best move and store that move in the hash
>table? I will run some tests as this is easy to do, but when I tried this a few
>years ago, my tree got _bigger_. And when I looked into why, I found myself
>searching nonsense moves from the hash table _before_ I got to the winning
>captures (the first of which was a move that would refute the move at the
>previous ply.)
>
>Easy to test. I'll supply some data in a bit, just for fun...
For one moment forget about alpha and beta, you are on the wrong track as
alpha and beta are not a part at all of the code. You need an extra stack
that is set to -INF at each ply. Then before you do A/B you do the bestmove
calculation for that ply. Involved variables: SCORE and STACK, no alpha beta.
Ed
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.