Transposition disaster

[Jaco van Niekerk]

Hi all

My chess engine, Vicki, currently plays without a transposition table. As this is rather embarrassing, I've started to implement one. However, Vicki plays substantially weaker with it and I have no idea why. Either there is a bug in the TT or it could be because of timing issues. Vicki often has to "hard stop" when it tries to search one ply deeper after the previous iteration returns immediately. Here is the main search algorithm that I used in shortened form:

Code: Select all

alphabeta(n, alpha, beta)
{
 
  if (position is drawn) return DRAWN

  if (time up)
  {
    quitsearch = 1
    return ZERO
  }
 
  value = probeTranspositionTable(n, alpha, beta, move)

  if (value != UNKNOWN) return value

  if (n <= 0)
  {
    value = quiescentSearch(alpha, beta)
    dumpTranspostionTable(value, 0, EXAXT, NO_MOVE)
  }
 
  genAllMoves()

  possibleMate = 1
  bestmove = 0
  hashtype = ALPHA


  for each move, mv
  {
    makeMove(mv)
    if (illegalMove) // leaves king in check, castling not allowed, etc.
    {
      takeBack(mv)
      continue
    }
    possibleMate = 0 
    value = alphabeta(n-1, -beta, -alpha)
    if (quitSearch) return ZERO

    if (value>=beta)
    {
      dumpTranspostionTable(value, 0, BETA, mv)
      return beta
    }
   
    if (value>alpha)
    {
      bestmove = mv
      alpha = value
      hashtype = EXAXT
    }

  }
   
  if (possibleMate)
  {
    if (kingInCheck) // checkmate
    {
      dumpTranspostionTable(-MATE, 0, EXACT, NO_MOVE)
      return -MATE
    } else { // stalemate
      dumpTranspostionTable(DRAWN, 0, EXACT, NO_MOVE)
      return DRAW
    }
  }

  dumpTranspostionTable(alpha, n, hashtype, bestmove)

}

probeTranspositionTable(n, alpha, beta, move)
{
  HASHENTRY *he = ce_tt[zobrist%TT_SIZE]
  if (he->zob = zobrist)
  {
    if (he->flags==EXACT) return he->value;
    if ((he->flags==ALPHA) && (he->value<=alpha)) return alpha;
    if ((he->flags==BETA) && (he->value>=beta)) return beta;
  }
  return UNKNOWN
}

dumpTranspostionTable(value, 0, type, best_move_in_position)
{
  HASHENTRY *he = ce_tt[zobrist%TT_SIZE]
  store at position based on depth and age
}


As you know so much depend on the transposition table. I desperately want to get this working, so I get rewrite the move ordering routine to give a higher score for the move returned by the TT for a given position. Also, extracting the PV from the TT is also much more elegant.

I would greatly appreciate any help/hints/comments from the forum.

Thank you!!

[Harald Johnsen]

You can simplify a bit your code by not storing the result of QS and your mate/stalemate score.
If I understand your code correctly you don't do a depth check when you probe your hash table (ppl usually don't post their real code).
If that's the case then it explain your problem. When you do a search at depth (d) you don't want to use the result of a search of depth (d-1).
Only result from depth (d) or (d+n) are ok.
Note that depth d is the remaining plies of the search, not really the depth.

HJ.

[Jaco van Niekerk]

Hi Harold

Thanks for replying... much appreciated!

(1) Bad translation on my part - I do check for depth in probeTT. Also the "=" should be a "==" (ouch!)

Hmmm... Thinking about it, you're quite correct. There is no need to store values for ply "0" (mate/stalemate and QS).

Do you (or anyone else) know how much improvement I should expect when implementing TT?? My current tests (just to get some sort of indication of improvement) consists of a gauntlet match of 80 games against 39 different engines (from very weak to very strong... Rybka's in there ). Without TT, Vicki scores 22.5/80 in 5 min matches and with TT this DROPS to 17/80. Surely this can't be right?!

BTW. I know my Zobrist keys are working since I've tested them with a modified perft routine.

[Harald Johnsen]

Code: Select all

value = [b]-[/b]alphabeta(n-1, -beta, -alpha)

I think there was a typo and you have a negative sign in your real code.
Also when failling high you store 'value' in your hash table but you return beta, this won't bug your search but you should store and return the same value.
But this does not explain your drop of strenght. I don't know where is the problem.

The improvement you can get from TT depends on what you do with your TT. You are 'only' using it for transposition so you won't get much but your engine should be a lot stronger with TT, you should have an increase in search depth at same time control or a reduction in node count.
You'll get more improvement when you use the move from the TT as a hint for move ordering (and implementing IID at the same time).

HJ.

[Harald Johnsen]

Code: Select all

probeTranspositionTable(n, alpha, beta, move)
{
  HASHENTRY *he = ce_tt[zobrist%TT_SIZE]
  if (he->zob = zobrist)
  {
    if (he->flags==EXACT) return he->value;
    if ((he->flags==ALPHA) && (he->value<=alpha)) return alpha;
    if ((he->flags==BETA) && (he->value>=beta)) return beta;
  }
  return UNKNOWN
}

You can not return alpha here, the hash table tells you that the position is worth less than he->value, and you return a value greater than that, you must return he->value. And you could return he->value too in the other condition too instead of beta (not a bug here but an optimization).


HJ.

[Jaco van Niekerk]

I cannot believe I missed something that simple... You're absolutely right - no wonder Vicki mixed blunders with perfectly valid moves. The valid moves comes from EXACT entries, while the blunders from incorrect cutoffs.

Thank you!

[Jaco van Niekerk]

Nope that's not it... Engine still plays poorly. I know that my Zobrist keys are working correctly... This simply makes no sense at all.... I hate this frustration!

[Harald Johnsen]

Can you post your two functions probeTranspositionTable and dumpTranspostionTable ?
Oh and you are using incorrect depth when storing the results, sometimes you use 'n', sometimes you use 0. It will not bug the search but this is sub optimal.

HJ.

[Jaco van Niekerk]

Hi Herald / forum

I may be opening a big can of worms here... but here is my alpha-beta with the two functions in question as it is now as they are implemented in the program. Straight copy and paste...

This version plays terrible chess. I know there are *lots* to improve in the code below and it is quite terrible, but at this point I just want to get the engine to play a decent game of chess before I tweak / fix the rest.

The moment I take out the transposition table stuff, the engine plays significantly better.

Thank you so much for the help and insight.

Code: Select all

/******************************************************************************/
/* Alpha-Beta search                                                          */
/******************************************************************************/

/* The search routine behind Vicki.
   NOTE: (1) oldpv is the pv line from a previous search on this position
         (2) pv/pvn is used to store current best line and cnt */
int alphaBetaSearch(int* oldPv, int* pv, int* pvn, int n, int alpha, int beta, int isNullMoveRoot)
{
  unsigned int moves[MAX_MOVES];   /* for movegen */
  unsigned int tmp, ttmove=0; 
  int pvLine[PV_MAX];
  int pvCnt=0, cntMoves, i, value, oldStatus=0, isPossibleMate=1;
  int hashType=HASH_ALPHA, side=(ce_status&0x10)?WHITE:BLACK; 
  __int64 oldKey=0;
  CHESSPIECE* king=(side==WHITE)?ce_whiteking:ce_blackking;
 
  nodesCount++;

  if ((ce_status&(1<<5))==(1<<5)) { return 0; } /* dislike draws (3-fold repetition) - note: 50-move rule pending */

  if (hardStop) return 0;
  if ((nodesCount&8191)==0)
  {
     if ((clock()-timeStart)/(CLOCKS_PER_SEC/10)>timeAvailable)
     {
      hardStop=1;
      *pvn=0;
      return 0;
     }
  } 

  /* material draws...
     ...
  */
   
  value=probeTT(ce_zobrist, n, alpha, beta, &ttmove);
  if (value!=HASH_UNKNOWN)
  {
    if (ttmove!=0)
    {
       pv[0]=ttmove;
       *pvn=1;
    }
    return value;
  }

  if (n<1)
  {
    value=quiescentSearch(alpha, beta);   
    dumpTT(ce_zobrist, value, n, HASH_EXACT, 0);
    *pvn=0;
    return value;
  }
 
  /* null move pruning */
  oldStatus=ce_status;
  oldKey=ce_zobrist;
 
  if ( n>=3 && ce_gamestate<GAMESTATE_ENDGAME && !isNullMoveRoot && !isUnderAttack(king->pos, side^0x08) )
  {     
    makeNullMove(); 
    value=-alphaBetaSearch(&(oldPv[1]), pvLine, &pvCnt, (n-NULLMOVE_R), -beta, -beta+1, 1);
     pvCnt=0; pvLine[0]=0;   
    takeBackNullMove(oldStatus, oldKey);   
    if (hardStop) { *pvn=0; return 0; }
     if (value>=beta) return beta;     
  }
 
  cntMoves=genMoves(side, moves); 
  orderMoves(moves, cntMoves, oldPv[0], ce_killers[n], ttmove);
  sort(moves, cntMoves);

  for (i=0; i<cntMoves; i++)
  {
    makeMove(moves[i]);   
     if (!wasLegalMove(king, side, moves[i]))
     {
       takeBack(moves[i], oldStatus, oldKey);
       continue;    
     }      
     isPossibleMate=0;   
     value=-alphaBetaSearch(&(oldPv[1]), pvLine, &pvCnt, n-1, -beta, -alpha, 0);
     takeBack(moves[i], oldStatus, oldKey);
   
     if (hardStop) { *pvn=0; return 0; } /* this should be avoided! */
   
     if (value>=beta) /* tree cut-off */
     {
       tmp=(moves[i]>>27)&0x1f;   
       if (tmp<25 || tmp>28) /* don't store good captures & promotions */
       {
         tmp=moves[i]&0x3ffffff; /* cut of previous ordering */   
        if ((ce_killers[n][0]!=tmp) && (ce_killers[n][1]!=tmp))
        {
            ce_killers[n][1]=ce_killers[n][0];
            ce_killers[n][0]=tmp; 
         }
       }
         
       dumpTT(ce_zobrist, value, n, HASH_BETA, moves[i]);
       return value;
     }
   
     if (value>alpha) /* new better move found */
     {
       pv[0]=moves[i];
       memcpy(&(pv[1]), pvLine, pvCnt*sizeof(int));
       *pvn=pvCnt+1;
       hashType=HASH_EXACT;
       alpha=value;
     }                                
  }
 
  if (isPossibleMate)
  {
     if (isUnderAttack(king->pos, side^0x08)) /* checkmate */
     {
       *pvn=0;
       dumpTT(ce_zobrist, -(100000+n), n, HASH_EXACT, 0);
      return -(100000+n);   /* quickest win/longest defence */
     } else { /* stalemate */
       *pvn=0;
       dumpTT(ce_zobrist, 0, n, HASH_EXACT, 0);
       return 0;
    }
  }
  dumpTT(ce_zobrist, alpha, n, hashType, pv[0]);
  return alpha;     
}

/******************************************************************************/
/* Transposition table                                                        */
/******************************************************************************/

int probeTT(__int64 zobrist, int depth, int alpha, int beta, unsigned int *move)
{
  unsigned int position=(unsigned int)(zobrist&(TT_SIZE-1));
  //assert(position<TT_SIZE);
  HASHENTRY *he=&(ce_tt[position]);
  if (he->zobrist==zobrist)
  {
     *move=he->move;
    if (he->depth>=depth)
     {
       if (he->flags==HASH_EXACT) return he->value;
       if ((he->flags==HASH_ALPHA) && (he->value<=alpha)) return he->value;
       if ((he->flags==HASH_BETA) && (he->value>=beta)) return he->value;
     }
  }
  return HASH_UNKNOWN;
}

void dumpTT(__int64 zobrist, int value, int depth, int flags, unsigned int move)
{
  unsigned int position=(unsigned int)(zobrist&(TT_SIZE-1));
  //assert(position<TT_SIZE);
  HASHENTRY *he=&(ce_tt[position]);
  if (depth>he->depth)
  {
    he->zobrist=zobrist;
    he->value=value;
    he->flags=flags;
    he->depth=depth;
    he->move=move;
    he->sequence=ce_sequence;
  }
}


[Harald Johnsen]

I don't know what you have in your quiescentSearch() (are you returning value or beta ?) but a priori you can not store the result of this search with an exact bound (you are doing a null window search in your null move search so the bounds are artificials).

HJ.

Code: Select all

if (n<1)
  {
    value=quiescentSearch(alpha, beta);   
    *pvn=0;
    return value;
  }

[Jaco van Niekerk]

Hi Herald...

Yes, that makes sense. You're quirte correct. I'll take that out. Of course, I can store an EXACT value where I calll eval() within QS, since this is a static evaluation and a exact value (won't chance, regardless of alpha / beta).

Let me try that... I cannot yet decide how significant this "bug" is... but I think it is significant enough to cause a drop in performance.

Regards

[Sven Schüle]

Hi Jaco,

Code: Select all

void dumpTT(__int64 zobrist, int value, int depth, int flags, unsigned int move)
{
  // ...
  if (depth>he->depth)
  {
    he->zobrist=zobrist;
    he->value=value;
    // ...
  }
}

there might be a problem with your replacement scheme. As soon as your hash table is full, adding new information becomes very unlikely due to the condition "if (depth>he->depth)". So I propose to check this condition, and consider to either skip it completely or change it into something like "if (he->zobrist!=zobrist || depth>he->depth)". The latter would allow reuse of the hash entry for new board positions which are mapped to the same table index.

Another, probably minor issue is that your function alphaBetaSearch() returns 'value' instead of 'beta' at the end of the branch "if (value>=beta)". The pure alpha-beta algorithm would return beta here, although I don't really know the difference between both ways since the level above should handle them identically.

Finally, the changes you've made in your probeTT() function regarding the return values ("he->value" instead of alpha resp. beta) may be unnecessary. In spite of Harald's statement I think it is correct and sufficient to return alpha resp. beta here. Bruce Moreland does it the same way on his page. "he->value" is outside the window in most cases, and as in the case above, I'm not sure which effect this will have. For example, if your iterative deepening relies on a value v returned from a search with "alpha <= v <= beta" then you should not return "he->value" here. Returning values outside the window is an optimization that you can use with the slightly different "falphabeta" algorithm.

Sven

[bob]

Hi all

My chess engine, Vicki, currently plays without a transposition table. As this is rather embarrassing, I've started to implement one. However, Vicki plays substantially weaker with it and I have no idea why. Either there is a bug in the TT or it could be because of timing issues. Vicki often has to "hard stop" when it tries to search one ply deeper after the previous iteration returns immediately. Here is the main search algorithm that I used in shortened form:

Code: Select all

alphabeta(n, alpha, beta)
{
 
  if (position is drawn) return DRAWN

  if (time up)
  {
    quitsearch = 1
    return ZERO
  }
 
  value = probeTranspositionTable(n, alpha, beta, move)

  if (value != UNKNOWN) return value[/quote]

The first question happens here...  What do you do in your probe code?  If you get an exact match, then you have to save and back up the PV if you are using the array approach.  Otherwise, are you checking the table value against the current search bounds and returning UNKNOWN if the table value would not cause a cutoff?  You can't just back up a value from the table without comparing it to the current alpha/beta values, otherwise you can play a worse move than you should.

I could not tell from your code below (probe code) what you store in the table, but the most common error is that when you fail high and do a table store, you are storing a "lower bound", not an "upper bound".  Because on a fail high, you don't know the exact score, only that it is >= the current beta value, which makes storing "beta" a lower bound for the actual score, not an upper bound.


[quote]

  if (n <= 0)
  {
    value = quiescentSearch(alpha, beta)
    dumpTranspostionTable(value, 0, EXAXT, NO_MOVE)
  }
 
  genAllMoves()

  possibleMate = 1
  bestmove = 0
  hashtype = ALPHA


  for each move, mv
  {
    makeMove(mv)
    if (illegalMove) // leaves king in check, castling not allowed, etc.
    {
      takeBack(mv)
      continue
    }
    possibleMate = 0 
    value = alphabeta(n-1, -beta, -alpha)
    if (quitSearch) return ZERO

    if (value>=beta)
    {
      dumpTranspostionTable(value, 0, BETA, mv)
      return beta
    }
   
    if (value>alpha)
    {
      bestmove = mv
      alpha = value
      hashtype = EXAXT
    }

  }
   
  if (possibleMate)
  {
    if (kingInCheck) // checkmate
    {
      dumpTranspostionTable(-MATE, 0, EXACT, NO_MOVE)
      return -MATE
    } else { // stalemate
      dumpTranspostionTable(DRAWN, 0, EXACT, NO_MOVE)
      return DRAW
    }
  }

  dumpTranspostionTable(alpha, n, hashtype, bestmove)

}

probeTranspositionTable(n, alpha, beta, move)
{
  HASHENTRY *he = ce_tt[zobrist%TT_SIZE]
  if (he->zob = zobrist)
  {
    if (he->flags==EXACT) return he->value;
    if ((he->flags==ALPHA) && (he->value<=alpha)) return alpha;
    if ((he->flags==BETA) && (he->value>=beta)) return beta;
  }
  return UNKNOWN
}

dumpTranspostionTable(value, 0, type, best_move_in_position)
{
  HASHENTRY *he = ce_tt[zobrist%TT_SIZE]
  store at position based on depth and age
}


As you know so much depend on the transposition table. I desperately want to get this working, so I get rewrite the move ordering routine to give a higher score for the move returned by the TT for a given position. Also, extracting the PV from the TT is also much more elegant.

I would greatly appreciate any help/hints/comments from the forum.

Thank you!!

[Harald Johnsen]

I sent you a pm Jaco.

HJ.

[Dann Corbit]

I don't know if someone else suggested this already, but you can have two hash calculation routines. The first routine calculates the hash incrementally. The second routine completely recalculates the hash. Then, you can set a flag that will tell you to calculate the hash both ways. That way, if there is some problem in incremental hash generation (typical places are some problem with null move, forgot to remove the e.p. flag and things like that) it will show up because the hash values will not match. Such a thing is easy to write and it will locate a lot of simple problems.

[H.G.Muller]

I had a stupid hashKey error in Fairy-Max, because I changed the encoding of sideToMove to 0 (w) and 16 (b), in stead of 8 vs 16 what it was in uMax. And I forgot that I work the e.p. rights in the key as sideToMove*epSquare, which of course does not work is sideToMove can be zero.

As the e.p. rights in Fairy-Max are also used to distinguish pseudolegal castlings from legal castlings, this had actually disastrous consequences, as some perfectly legal moves (or null moves!) lead to positions that would have been illegal when reached through castling, leading to false in-check verdicts, and thus unjustified check extensions, which again led to infinite recursions...

[Jaco van Niekerk]

Hi all

Firstly, thank you for all your help. It is great to have a forum that actually cares about a tiny little chess engine somewhere out there that has a "disability".

It turned out that this was the culprit:

Code: Select all

if (n<1)
  {
    value=quiescentSearch(alpha, beta);   
    dumpTT(ce_zobrist, value, n, HASH_EXACT, 0);
    *pvn=0;
    return value;
  }


I was doing a normal QS search and storing the hash value as an EXACT value, which of course is terribly wrong! Thanks to Herald for pointing this out.

The difference between returning "value" or "beta" at cut offs are both correct and are referred to as either "return soft" or "return hard". Google it for more information.

I had some serious Zobrist calculation issues as well, but found that you can easily debug that by simply adding assert(zobrist == calcZobrist()) line at the end of makeMove(), where calcZobrist() calculates the entire key from scrach and zobrist is the incrementally created key. Thank you Dann for also suggesting this... but I have this already. Of course, disabling asserts is a good idea before playing tournaments!

I am testing Vicki now in a little tourney that I follow on the web. You guys can have a look too, if you're interested. See www.vicki.co.za/Vicki.html

Thanks again for the help and good luck with your own engines. Now, I can spend some time with the move ordering!