Transposition Tables

[cms271828]

Thanks, that helps...

If there is a stored entry, with a 64bit key K, and in the search, I am about to record an entry also with 64bit key K, then do I always overwrite the stored entry, regardless of the depths?

Also, I'm unsure about what I do when there are no moves generated in a node, (Stalemate / Checkmate)...
There was some debate between you (HG Muller) and Bob Hyatt regarding the whole -1000000-D thing for scores.

I've done a quick example...
If first search finds a mate at D=7, I would return -1,000,007.
So in this case, I could just record the value -1,000,000, to indicate a mate.

Then on next search, supposing the node where it is mate is come to, at D=10 say.
Probing the TT, would give the value -1,000,000, since this is checkmate, I can modify the score to -1,000,010, since that would be the true value.

I believe checkmate scores would all have to be stored as EXACT ?
So they will be returned when probed for.

Does my idea make sense? or does it just sound like random waffle?

Thanks again, for all advice.

[hgm]

You always replace the least deep entry of the two, even if its depth was larger than what you want to store now. It is equally important to store recent entries than it is to store deep entries. Deep entries will save you a lot of work upon a hit, but you will get almost no hits upon them. But positions are very likely to be revisited very soon after they are first encountered (e.g. by transposing the last two moves).

I don't do any of the 1,000,000-D stuff, so I could not advice you on it (other then not to use it ). To guarantee the fastest mate will be preferred, I use

Code: Select all

if(Alpha < -MATES) Alpha = Alpha - 1;
if(Beta <= -MATES) Beta = Beta - 1;

as the first thing in my Search() routine, and

Code: Select all

if(BestScore < -MATES) BestScore = BestScore + 1;

just before I return BestScore, where MATES is the lowest mating score.

In fact, in my engines, I use currentEval in stead of -MATES, because I don't only want to encourage the engine to take the fastest mate, but also to take the fastest path to, say, capturing a Queen or Rook, rather than indecisively postpone it until the gain has evaporated.

[cms271828]

Thanks for help...

But I haven't been able to grasp how it works.

I've included some pseudo code below based on
http://www.seanet.com/~brucemo/topics/hashing.htm,
and the code in the last post.

The code obviously doesn't work and there are bits missing, and bits in wrong places.
I'm not sure what MATES is, is this just a fixed value, like where I used the 1,000,000 to indicate a checkmate?

If you can help me put the pseudo code together centered on this different technique for mate scores I would be very grateful.
I don't think I can understand it without seeing the full code first.

Thanks for any help.

Code: Select all

int AlphaBeta(int depth, int alpha, int beta)
{
     /////////////////////////////////////////////////////////
     if(alpha < -MATES) alpha = alpha - 1; 
     if(beta <= -MATES) beta = beta - 1; 
     ////////////////////////////////////////////////////////


      int hashf = hashfALPHA;

      if ((val = ProbeHash(depth, alpha, beta)) != valUNKNOWN) return val;

      if (depth == 0)
      {
            val = Evaluate();
            RecordHash(depth, val, hashfEXACT);
            return val;
      }

      GenerateLegalMoves();

      while (MovesLeft())
      {
            MakeNextMove();
            val = -AlphaBeta(depth - 1, -beta, -alpha);
            UnmakeMove();
            if (val >= beta)
            {
                  RecordHash(depth, beta, hashfBETA);
                  return beta;
            }
 
            if(val > alpha)
            {
                hashf = hashfEXACT;
                alpha = val;
            }
      }

      RecordHash(depth, alpha, hashf);
      
      /////////////////////////////////////////////////////////////////////      
      if(BestScore < -MATES) BestScore = BestScore + 1;
      //////////////////////////////////////////////////////////////////////

      return alpha;
}

[hgm]

As you return alpha (alpha) in stead of BestScore (soft fail), you would have to replace BestScore by alpha. (you will see that you than will always return the original alpha if no moves were found that topped it).

[cms271828]

Thanks, but it will take me forever to figure out by guessing where the code goes, and it will still probably be wrong, so I'm just gonna try and work around my old idea, I think Bob Hyatt said it would work by adjusting the -1000000-D score, so I'll try that.

Thanks

[hgm]

Thanks, but it will take me forever to figure out by guessing where the code goes, ...

What is there lefy to guess? You wrote the code above...

[cms271828]

But what I usually do is, after calling generate moves, I have something like...

Code: Select all

If(no_legal_moves_generated)
{
     if(side_to_move_is_in_check) return -1000000-D; // CHECKMATE
     return 0; // STALEMATE
}

I'm not sure how I fit it together, including the call to RecordHash.

Also, what value is MATES?


Thanks

[hgm]

If no legal moves are generated, you return the mate score, say -1,000,000.

With this value as mate score, you could set MATES to 999,000, as you are unlikely to encounter any mates deeper than mate-in-1000. So everything above 999,000 would be a mate score.

[cms271828]

Ok, does this look right...
I've put lines around the new parts.
I still think it looks confusing, and will probably cause me more problems later.
I still don't see whats so bad about using -1000000-D, it makes sense to me, but does it lack in performance compared with this method?

Code: Select all

int AlphaBeta(int depth, int alpha, int beta) 
{ 
     ///////////////////////////////////////////////////////// 
     if(alpha < -990000) alpha = alpha - 1; 
     if(beta <= -990000) beta = beta - 1; 
     //////////////////////////////////////////////////////// 


      int hashf = hashfALPHA; 

      if ((val = ProbeHash(depth, alpha, beta)) != valUNKNOWN) return val; 

      if (depth == 0) 
      { 
            val = Evaluate(); 
            RecordHash(depth, val, hashfEXACT); 
            return val; 
      } 

      GenerateLegalMoves(); 

      while (MovesLeft()) 
      { 
            MakeNextMove(); 
            val = -AlphaBeta(depth - 1, -beta, -alpha); 
            UnmakeMove(); 
            if (val >= beta) 
            { 
                  RecordHash(depth, beta, hashfBETA); 
                  return beta; 
            } 
  
            if(val > alpha) 
            { 
                hashf = hashfEXACT; 
                alpha = val; 
            } 
      } 

       ///////////////////////////////////////////////////////////////////
       if(NO_MOVES_GENERATED)
       {
              if(CHECKMATE) alpha=-1000000
              else                  alpha=0; // STALEMATE
       }
       ///////////////////////////////////////////////////////////////////

      RecordHash(depth, alpha, hashf); 
      
      /////////////////////////////////////////////////////////////////     
      if(alpha < -99000) alpha = alpha+ 1; 
      /////////////////////////////////////////////////////////////////

      return alpha
}

[hgm]

Yes, that is it. With this code, a mate-in-1 move (and the node from which it is done) will get score 999,999, a mated-in-one move/node -999,999, a mate-in-2 node 999,998, mated-in-2 -999,998, etc. So it will prefer a mate-in-1 move over a mate-in-2 move, and a mated-in-2 move over a mated in-1.

If you want to add 'mate-distance pruning', meaning that you never would search a branch beyond 5 ply if you already found a mate in 5 ply in a parallel branch, you could add:

if(-1000,000 >= beta) return beta;

immediately after the place where you decremented beta. Bob would tell you that this is a waste of time, though.