Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Interesting mate test for hashing

Author: Robert Hyatt

Date: 13:45:59 09/10/99

Go up one level in this thread


On September 10, 1999 at 16:21:48, Alessandro Damiani wrote:

>On September 10, 1999 at 15:58:45, Ed Schröder wrote:
>
>>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
>
>I think the best way to explain is to write a small piece of code in pseudo C,
>else we talk around the point.
>
>Alessandro


OK... here is what I did:

Normal alpha/beta first:

int Search(int alpha, int beta, etc...) {
  best=-infinity;
  bestmove=0;
  foreach (move in movelist) {
    MakeMove();
    value=-Search(-beta,-alpha,etc.)
    if (value > best) {
      best=value;
      bestmove=current.move;
    }
    if (value > alpha) {
      if (value >= beta) {
        return(value);
      }
      alpha=value;
    }
  }
  HashStore(bestmove,alpha, etc...)
}



So what I did was to simply take the score for each search made after trying
one of the moves at this ply, and remember the 'best' score and associated move.

All I am saying is "this does not work".  It is a characteristic of the alpha/
beta search.  It isn't a "it might work if ..."  it simply won't work.  Because
the searches below this node (again, assuming this is a fail-low node where _no_
move produces a score > alpha, which is the case where I claim there is never a
best move to try here) return a bound on the value for that move.  And I have no
idea how to choose between a move with a bound <=200 and another move with a
bound <= 150.  Because the first could have a score well below 200.  I simply
don't know as I told the search below this node to stop whenever you find a
score > X, where X is my negated alpha bound.

Now, we have code.  Did I misunderstand what you are saying?  If not, then I
can certainly explain further why that 'best' and 'bestmove' above are no good
in this context.  You can think of "best" as a random number that is <= alpha,
nothing more.  Which means "bestmove" is a random move chosen from the moves
searched at this ply.  And that is _not_ the move we want to try first when we
get back to this position and it is suddenly not a fail-low position where all
moves have to be tried, but rather it is a fail high position where the best
move will let us cut off quickly...



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.