Transposition Tables

[bob]

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?

I don't have time to read the PDF. But here is a synopsis of what works:

1. You are searching and complete a ply after searching all nodes, and the best score is limited as alpha < score < beta, so you have a good score. You store that score, and EXACT.

2. You are searching and you find a score >= beta at the current ply. You store LOWER + beta, because beta is now a lower bound. You know the score is >= beta but you don't know how much so beta represents the lower bound on the unknown score.

3. You are searching and you complete all nodes and best score is still <= alpha. You store UPPER + alpha. You know the score is <= alpha but you don't know how much so alpha represents the upper bound on the unknown score.

Now you are searching along and you get a hit.

1. if type = EXACT (all of this assumes the draft is sufficient) you just return the score you retrieved and use that with no more searching at this ply.

2. if type = LOWER, you make sure your current beta bound is greater than or equal to the bound score in the table, which means you are in a position where if you know that the score is >= x, and x is >= your beta value, it will cause a fail high and you can stop searching.

3. if type = UPPER, you make sure your current alpha bound is less than or equal to the bound score in the table, which means you are in a position where you know the score is <= x, and x is <= your alpha value, it will cause a fail low and you can stop searching.

It really is that easy. Only the mate scores and bounds need special adjustments...

[bob]

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 don't like the idea of mucking with the scores. You are essentially saying it is better to win something _now_ than to postpone it a bit. That is contrary to sound practice in chess, where the best idea is to take the material at the most opportune moment, which isn't dependent on where we are in the tree.

But mates are different, because they represent exact scores. If you muck with some, you have to muck with all or you wind up with inconsistencies in the search that will be maddening to uncover...

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?

His comment is based on the idea that this is unsound play. If you are in a dead drawn position, then trading down is a bad idea if you have more material or some slight winning chances, because it makes your opponent's task of drawing you easier. But in normal positions, delaying captures or favoring captures is not what humans normally do. I can recall many games annotated by humans where the GM will say "white cashed in and took the pawn too quickly and dissipated his advantage" or something similar. I certainly don't want to rush a capture by 4 plies (+4 centipawns) and to do so give up 3 centipawns of positional score elsewhere, if I can delay the capture a couple of moves and not give up the 3 centipawns at all...

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.

Delaying a loss might well be OK. I have a "swindle mode" that delays simplified draws when I am material ahead. But using it to encourage quicker captures is certainly wrong. It would seem to me it will encourage you to trade at every opportunity since the longer you wait the worse the score. I don't want to liquidate the center just because I can, I want to wait and use the tension to help me further whatever plan I am following.

[Colin]

Thanks,

You said if score>=beta, then STORE 'LOWER' + beta, but in the pseudocode, it says Store(p,depth,score,flag,move),
so thats storing score, not beta.

I guess that still works, but your way is an improvement?

PS. If you have any psuedocode showing how to incorporate TTs into engine, that could help, its a little tedious for everyone if I have to keep asking if this is right, and if that is right, but every time I find some psuedocode, there seems to be a flaw in it some how.

Thanks anyway

[Jacob]

Have you tried http://www.brucemo.com/compchess/progra ... ashing.htm? There are a bunch of good articles there.

[hgm]

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

Yes, you are right. The system can be refined in many ways. It makes sense to make the bonus proportional to the magnitude of the expected loss. Postponing loss of a Rook is worth more than postponing creation of a doubled Pawn.

In my 1980s engine Usurpator I actually multiplied all negative scores by 15/16, which is equivalent to a bonus of 1/16 of the future loss. This was probably a bit too much. But as 4 ply was already a good search depth in those days, it hardly accumulated. Sacrificing a Pawn to delay the loss of a Queen by 2 moves was good strategy, as it might very well have pushed the loss over the opponent's horizon.

One should perhaps put a threshold to the delayed-loss bonus (applying it only to losses > 50 cP). Using a few extra bits in the score (as maintained and returned by Searc()), but rounding it in the hash might be even better. It would mean there is a noise added to ever hash probe of ~1 cP (you must make sure the rounding does not violate the bound, so direction of rounding would be dictated by the bound type), but tiny delayed loss bonuses would still accumulate until they pass the rounding threshold. So you would not care to delay the formation of a doubled pawn by one or two moves, as the accumulated bdelay bonus would not exceed the rounding threshold. But you might prefer to do so if you can delay it for 10 or 15 moves.

[bob]

Thanks,

You said if score>=beta, then STORE 'LOWER' + beta, but in the pseudocode, it says Store(p,depth,score,flag,move),
so thats storing score, not beta.

Think about it for a minute. If you are failing high, isn't "score" >= beta already?

I guess that still works, but your way is an improvement?

Not quite. You do have two choices. You can actually store beta, or you can store your score. If you are doing normal alpha/beta, they would be the same thing. If you are using fail-soft alpha/beta then score can be > beta, and you could store it instead to get an even better bound. Ditto for the other side. I wasn't trying to get into that however, to keep it simple.

PS. If you have any psuedocode showing how to incorporate TTs into engine, that could help, its a little tedious for everyone if I have to keep asking if this is right, and if that is right, but every time I find some psuedocode, there seems to be a flaw in it some how.

Thanks anyway

[hgm]

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.

Agreed. [But based on what you say later, I start to doubt that I properly understand what you meant to say here. I only agree if with the enhanced 'the' you do not mean that same position as at the root, but another one that comes from it after moving a white and a black piece]

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...

By the time this score reaches the root it would indeed be a mate in N+1. This is worse than the move we had before, leading to the occurrence of this position at ply=2. So we won't pick that move, as we already have a better one. So the root remains a mate-in-N node.

That seems quite natural to me, this whole thing was designed to make the engine chose the fasted path to mate, (or the longest to mated). So that is what it does.

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

I still don't get it. Which table bound (for which node)? For me to understand your question, so I can answer it, you really must be more specific. You suppose the mate in N-1 score was not exact, but a bound? If so, what type of bound? If we are satisfied, with a bound, it was apparently not on the PV. So what was the PV, did it share the first move of the path to the mate at ply=2, but did the opponent have a better alternative (and was this avoiding mate, or just a longer mate)? Or did we already have a shorter mate from the root?

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.

You seem to count from the root. That makes no sense. If a position is a mate-in-1, it means that from that position I can do a single move that checks the King, after which the opponent has no legal moves. If I encounter that same position at ply=9, I can still do that same move, and after that the opponent will still be checkmated. So it is still a mate-in-1. How many moves you made in order to reach that position do have no effect on what the DTM of that position is.

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.

Well, let me make one thing clear: this method works flawlessly since 1980. If you don't believe it, try to let Crafty defend KQK or KRK against uMax. You can have Crafty use EGTBs if you want...

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.

You don't take a cutoff if the hash score >= beta, and you don't up alpha when alphs < lower bound < beta?

Remarkable. I thought this was pretty standard.

[Tony]

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?

Correct, the pseudo code at the top of page 15 of the first paper is wrong.

Tony

[Vempele]

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

No. They aren't associated with alpha and beta. You should associate the words with their meanings instead. I repeat:

The exact score cannot be lower than LOWERBOUND.
The exact score cannot be higher than UPPERBOUND.

If you fail high, you know the true score can't be lower than beta. The score is therefore a lower bound.
If you fail low, you know the true score can't be higher than alpha. The score is therefore an upper bound.

[bob]

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.

Agreed. [But based on what you say later, I start to doubt that I properly understand what you meant to say here. I only agree if with the enhanced 'the' you do not mean that same position as at the root, but another one that comes from it after moving a white and a black piece]

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...

By the time this score reaches the root it would indeed be a mate in N+1. This is worse than the move we had before, leading to the occurrence of this position at ply=2. So we won't pick that move, as we already have a better one. So the root remains a mate-in-N node.

That seems quite natural to me, this whole thing was designed to make the engine chose the fasted path to mate, (or the longest to mated). So that is what it does.

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

I still don't get it. Which table bound (for which node)? For me to understand your question, so I can answer it, you really must be more specific. You suppose the mate in N-1 score was not exact, but a bound? If so, what type of bound? If we are satisfied, with a bound, it was apparently not on the PV. So what was the PV, did it share the first move of the path to the mate at ply=2, but did the opponent have a better alternative (and was this avoiding mate, or just a longer mate)? Or did we already have a shorter mate from the root?

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.

You seem to count from the root. That makes no sense. If a position is a mate-in-1, it means that from that position I can do a single move that checks the King, after which the opponent has no legal moves. If I encounter that same position at ply=9, I can still do that same move, and after that the opponent will still be checkmated. So it is still a mate-in-1. How many moves you made in order to reach that position do have no effect on what the DTM of that position is.

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.

Well, let me make one thing clear: this method works flawlessly since 1980. If you don't believe it, try to let Crafty defend KQK or KRK against uMax. You can have Crafty use EGTBs if you want...

that would be the best test. But just because it has worked so far doesn't make it correct. If you are storing some bounds "as is" and others are munged by your +1 stuff, then there are holes. At worst case, it just makes your search less efficient. At worst it will produce wrong mate scores.

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.

You don't take a cutoff if the hash score >= beta, and you don't up alpha when alphs < lower bound < beta?

Remarkable. I thought this was pretty standard.

OK, that's not what I said. You either have a screwed up bound in the table, or you have a screwed up bound in your search. If you don't correct MATE bounds when you store them, they are then wrong in the table, because mate scores or bounds within the search are relative to the root, but down in the tree you are not at the root. So storing the normal alpha/beta value or bound will store the _wrong_ value.

When I am searching, a value >= beta certainly will produce a cutoff. But When searching for mates, I have to be certain that "value" and "beta" are comparable. That is they _both_ represent a mate in N from the current position, or from the root. If you store some bounds (mates) as is, and you munge up others, then they can not be compared correctly.

A couple of examples.

You search to ply=14 and discover black has been mated at the previous ply as there are no legal moves here and black is in check. The mate score has to be mate in 13/14 depending on how you count, for humans we would call it mate in 7 moves. As you back up thru the tree you are going to store this score at every ply as you work your way backward. When you get back to ply=3, you are going to store mate in 6, because at ply=3 you are one move closer to the mate than at the root. Now you search a different sequence of moves and you find this position at ply=7, rather than at 3 where you stored it. You have to adjust it to say "mate in 9" because the position is a mate in 6, but you find it after making 3 moves first.

For bounds you have the same problem. If you don't get them exactly right, you can think that a mate in 5 is worse than a mate in 6 which would cause you to take an incorrect cutoff and miss the shorter mate.

I don't know how to explain it any better. Anything to do with mate scores or bounds has to be adjusted so that everything is an apples-to-apples comparison. All exact scores, all upper and all lower bounds that have anything to do with mate fall into this category. Failure to do so will absolutely introduce strange behavior into your search.