Transposition Tables

[Tony]

I've found a different pseudocode to deal with transposition tables.
The code is on page 15 of this pdf...
http://www.cs.ualberta.ca/~tony/OldPape ... review.pdf
The code looks a little dated with the BEGIN/END statements, but after comparing it to the code in the last pdf I mentioned...

1. The code is essentially the same, except in this pdf, where the depth=0, only EVAL is called, and no storing takes place.

2. It explicitly shows the hash move being played first

3. I think the code is the wrong way round in this pdf..

Code: Select all

IF&#40;score<=alpha&#41; THEN flag&#58;=UBOUND;
IF&#40;score>=beta&#41; THEN flag&#58;=LBOUND;

I believe UBOUND and LBOUND need to be swapped ?

Can I get a chess programmers seal of approval on this psuedocode before I use it?
Thanks for any help

Forget these wordings. They seem to be confusing not only for non native english speakers.

Use AT_LEAST and AT_MOST and you'll spend a lot less time thinking when reading them in your code.

Tony

[hgm]

Here is what I don't follow. You find a LOWER position in the hash with a mate in 12 bound. You find that at ply=2. How do you use it? Ditto for UPPER and mate in 12. BTW the hash entry was stored at say ply=12. And is getting used at ply=2... That is what I am not following, because the bound needs to change from what it was at ply=12 to what it should be at ply=2 to be used... That is, not only EXACT entries have to be adjusted, but UPPER/LOWER entries as well to properly produce cutoffs when they should and not when they shouldn't.

Why do you say the bounds have to change? I suppse with bounds you mean the actual score, and not the bound type.

But a position that is a mate-in-12, it is a mate-in-12 at both ply=2 and ply=12. Where you encounter it in the tree does not affect how you would play from there to finish the game. That is a property of the position, and not of the path to it. (Assuming you did not bungle that same mate-in-12 on an earlier ply, so that you now have to account for rep-draws.)

If it is a LOWER bound, it means mate-in-12-or-less. If you encounter it at ply=2, you could use it if beta was <= mate-in-12 to effect a cutoff (meaning that on ply=1 the opponent already has found a way to postpone the mate longer than 12 moves, or perhaps not be mated at all, so his score there is already better then or equal to mated-in-12). Or, if beta is above mate-in-12 at ply=2, meaning that this could still be the quickest mate from the root (i.e. the PV), you could use it to up alpha to mate-in-12, as that alpha is used to tell the daughter nodes: "don't bother to figure out how long the mating takes if it takes longer then 12, for I know from the hash that I will find at least one move here that does it in 12 or better, so if you cannot do better than 12, it just means that it was a mistake to search you before searching that other move". Actually is seems unlikely that this would ever happen, as you know from the hash table which move would lead to the mate-in-12-or-less, and you are going to search that hash move first, and that would up alpha anyway. So upping alpha based on the hash seems a bit pointless.

But none of this is any different from what you would do on any hash hit. (Note that the hash probe would be done before adjusting the window-bounds, if the hash store is done after incrementing the score. I forgot to mention that explicitly, as I am used to doing the hash probe before I even call Search().)

Another way of saying it is that the algorithm I described simply builds a DTM tablebase in the hash table. Perhaps that makes it more clear?

[hgm]

Note that the prescription for building a DTM tablebase is:

Code: Select all

Search(Depth)
{
    int Score, BestScore = -INF;
    
    if(Checkmated()) return -CHECKMATE;
    if(Stalemate()) return 0;

    // Determine BestScore by searching all moves
    for(ALL_MOVES)
    {
        Make();
        Score = Search(Depth-1);
        UnMake();

        switch(Score)
        {  // For minimax one would only have Score = -Score here.
            case CHECKMATED_IN_N:
                Score = CHECKMATE_IN_(N+1); break;
            case CHECKMATE_IN_N:
                Score = CHECKMATED_IN_N; break;
            case 0:
                Score = 0; break;
        }
        if(Score > BestScore) BestScore = Score;
    }

    Store(Score);
    return Score;
}

This deviates from pure minimax, as when mated-in-n is the negative of mate-in-n, mate-in-(n+1) cannot be the negative of mated-in-n (or it would be the same as mate-in-(n+1), and all mates of different duration would become indistinguishable).

[Uri Blass]

I think that I understand the idea inspite of not understanding the full details and I will try to explain it in my own words.

You practically have 2 numbers
1)E that it only evaluation of the position that you store in the hash.
E can get value between -Mate and Mate-1
2)H that is the history ply of the game.

Suppose H<10000
Let define
S=f(E,H) to be the value that you return from the search

You can have
S=E-H if E>0
S=E+H if E<0
S=0 if E=0

It means that you practically store different value in the hash not only for mate in 2 and mate in 3 but also for winning a rook in 3 moves and winning a rook in 2 moves.

This mean that you may need to increase the number of bits that you store in the hash table and difference of 1 in my evaluationn is now difference of 10,000.

It means that I will have less space in the hash to store positions.
The advantage may be bigger so I do not claim that it is a bad idea.

I am not close about exact details of implementation so I did not try to implement it.

Uri

[hgm]

It means that you practically store different value in the hash not only for mate in 2 and mate in 3 but also for winning a rook in 3 moves and winning a rook in 2 moves.

This mean that you may need to increase the number of bits that you store in the hash table and difference of 1 in my evaluationn is now difference of 10,000.

Indeed, the way I wrote it (comparing to CurEval in stead of -MATINGSCORES) would also score a position that would win a Rook in 2 moves slightly better than one winning a Rook in 3 moves, ending in the same position.

I am not sure why you want to increase the resolution of the score 10,000 fold. Do you expect your engine ever to see the forced loss of a rook in 10,000 moves (20,000 ply)? It seems 50 moves will be the practical limit to see such gains for some time to come.

In the second place, why would you want these scoring differences to be infinitesimal, i.e. always completely negligible compared to even the smallest evaluation difference? Suppose my engine sees the forced loss of a Rook vs Knight in 20 moves (40 ply), after which position A is reached in an end leaf. It can sacrifice that Rook for a Knight on the next move, and then, after best play, it will end 15 centPawn better in the end leaf B then it had evaluated A. Would you really want it to give the Rook immediately, in order to salvage those 15 cP of positional score?

I know that I wouldn't! For one, the 40-ply 'forced loss' is unlikely to have searched the tree exhaustively to 40 ply, there will be lots of pruned / reduced branches and perhaps one of those will offer an escape that the engine cannot see yet. Once the Rook is gone, I am unlikely to get it back (I will be playing with a weaker piece army...). In the second place, the position where I lose the Rook on ply=40 is searched a lot less deep than that at ply=2. If I am giving the Rook now, I am pretty sure that I won't win it back the following 19 moves. The ply=40 loss might occur in a leaf, and searching a little deeper might bring the counter-attack (which I have 20 moves to prepare) within the horizon. Finally, even if all this would have been revealed in a 100-ply reductionless full-width search, so that it is 100% certain, who says that my opponent can do that. Maybe he doesn't see the combination through which he can gain the Rook at all. If I play RxN, he most likely will not miss the fact that he can recapture that Rook...

So I think that delaying an 'inevitable' loss for 20 moves is well worth 20cP of positional advantage. That is in fact on the low side; with current engine capabilities it might well be worth half a Pawn to delay the loss of a Rook for 10 moves. (The exact tradeoff could be measured through testing). No reason at all to limit the accumulated delay bonus to a small fraction of 1 cP.

[Uri Blass]

You may be right for the example of losing a rook but what about the case when you lose something small.

if you get a bonus for losing small positional value if it only comes later then you may evaluate losing it as better for you if you can delay it relative to winning the same advantage.

The only way to prevent that problem is simply to have delay bonus score that is smaller relative to the difference in normal evaluation.

Uri

[Colin]

Thanks, but I still think there is an error...
Looking at the same code on page 15 of
http://www.cs.ualberta.ca/~tony/OldPape ... review.pdf
At the top of the search method..

Code: Select all

IF(height>=depth) THEN BEGIN
  IF(flag=VALID) THEN
    Return(score); {Forward prune, fully seen before}
  IF(flag=LBOUND) THEN
     alpha=max(alpha,score);  {Narrow the window}
  IF(flag=UBOUND) THEN
    beta=min(beta,score);       {Narrow the window}
  IF(alpha>=beta) THEN
    Return(score);  {Forward prune, no further interest}
END

But at the end of the search method...

Code: Select all

flag:=VALID
IF&#40;score<=alpha&#41; THEN
  flag&#58;=UBOUND;
IF&#40;score>=beta&#41; THEN
  flag&#58;=LBOUND;
IF&#40;height<=depth&#41; THEN       &#123;update hash table&#125;
  Store&#40;p,depth,score,flag,move&#125;;
Return&#40;score&#41;;

I think UBOUND and LBOUND are the wrong way wrong when compared to how they are at the top.
In the other pseudocode, they are swapped around with LOWERBOUND being attached with alpha, UPPERBOUND on beta.
So either this psuedocode above is wrong(I think it is), or the other pseudocode is.
Can anyone check the code above, thanks.

[bob]

Here is what I don't follow. You find a LOWER position in the hash with a mate in 12 bound. You find that at ply=2. How do you use it? Ditto for UPPER and mate in 12. BTW the hash entry was stored at say ply=12. And is getting used at ply=2... That is what I am not following, because the bound needs to change from what it was at ply=12 to what it should be at ply=2 to be used... That is, not only EXACT entries have to be adjusted, but UPPER/LOWER entries as well to properly produce cutoffs when they should and not when they shouldn't.

Why do you say the bounds have to change? I suppse with bounds you mean the actual score, and not the bound type.

No it isn't, and that's the point. If a position is mate in N at the root, then the position two plies farther down is a mate in N-1. If that _same_ position is found at ply=4, it is a mate in N-1 but we have added 2 moves thru searching so it now becomes a mate in N+1, because we somehow wasted a move...

If that doesn't get reflected in the table bound, then you prune based on the wrong bound and get inconsistent/incorrect mate announcements...

But a position that is a mate-in-12, it is a mate-in-12 at both ply=2 and ply=12.

Again, no it isn't. If a position is a mate in 12, but I look it up at ply=9, it is _not_ a mate in 12 now. It is a mate in 17 because I have made five moves prior to reaching the mate in 12 position. That's the point. Mate scores are relative to the ply where they are found, not relative to the root. The only thing that is relative ot the root is whatever mate score gets backed up to the root.

Where you encounter it in the tree does not affect how you would play from there to finish the game. That is a property of the position, and not of the path to it. (Assuming you did not bungle that same mate-in-12 on an earlier ply, so that you now have to account for rep-draws.)

Perhaps. But what if you find a mate in N that is really a mate in N+3. And the next time around you prune based on that score and all mate scores look worse?

You are apparently overlooking how alpha/beta prunes things away.

If it is a LOWER bound, it means mate-in-12-or-less. If you encounter it at ply=2, you could use it if beta was <= mate-in-12 to effect a cutoff (meaning that on ply=1 the opponent already has found a way to postpone the mate longer than 12 moves, or perhaps not be mated at all, so his score there is already better then or equal to mated-in-12). Or, if beta is above mate-in-12 at ply=2, meaning that this could still be the quickest mate from the root (i.e. the PV), you could use it to up alpha to mate-in-12, as that alpha is used to tell the daughter nodes: "don't bother to figure out how long the mating takes if it takes longer then 12, for I know from the hash that I will find at least one move here that does it in 12 or better, so if you cannot do better than 12, it just means that it was a mistake to search you before searching that other move". Actually is seems unlikely that this would ever happen, as you know from the hash table which move would lead to the mate-in-12-or-less, and you are going to search that hash move first, and that would up alpha anyway. So upping alpha based on the hash seems a bit pointless.

But none of this is any different from what you would do on any hash hit. (Note that the hash probe would be done before adjusting the window-bounds, if the hash store is done after incrementing the score. I forgot to mention that explicitly, as I am used to doing the hash probe before I even call Search().)

Another way of saying it is that the algorithm I described simply builds a DTM tablebase in the hash table. Perhaps that makes it more clear?

It is a _lot_ different from what I do no non-mate hash hits. Those scores are not relative to the ply where they were computed. Mate scores are. And they are thus different in how they have to be handled.

[Vempele]

I think UBOUND and LBOUND are the wrong way wrong when compared to how they are at the top.

They are the same in both.

In the other pseudocode, they are swapped around with LOWERBOUND being attached with alpha, UPPERBOUND on beta.

LOWERBOUND = an earlier search failed high (>= earlier beta) = the exact score is at least this high, therefore we can raise alpha if it's lower than this.
UPPERBOUND = an earlier search failed low (<= earlier alpha) = the exact score cannot be higher than this, therefore we can lower beta if it's higher than this.

Neither assumption is safe in PV nodes, though.

[Colin]

Sorry, but they are different...

On pages 14 and 15 is the pseudocode.
http://homepages.cwi.nl/~paulk/theses/Carolus.pdf
LOWERBOUND is associated with ALPHA,
UPPERBOUND is associated with BETA
(In both the testing flag, and storing parts)

On page 15 here
http://www.cs.ualberta.ca/~tony/OldPape ... review.pdf,
LBOUND is associated with ALPHA for testing flag, and BETA for Storing.
UBOUND is associated with BETA for testing flag, and ALPHA for Storing.

Regardless of the what you call them.. I think it is back to front on the 2nd pdf above, and can be resolved by switching them round in the Storing part.

Does this sound right?