Transposition Tables

[hgm]

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.

And the 'opportune moment' is defined as the moment where you cannot drive up the eventual score any further by postponing the gain...

Which is exactly when this algorithm will decide to cash in. As long as other moves are significantly better, the 1 cP delay bonus does not even compete with the noise.

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

The fact that other scores are non-exact, but might change on deeper search, seem all the more reason to apply the 'no-detours' princilple to these other scores. Gains that are nearby have been verified to much larger depth than the same gain very deep in the tree.

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.

What's that got to do with it??? Trading is not a gain. Going to from a dead drawn position to an even more dead drawn position is not a gain. Even a 'winning' trade (like giving 2P for N in KNPPKNP) is not a gain if it is an easier draw after that trade. If your evaluation says it is, it should receive a major overhaul. But don't blame it on the search!

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

Well, +4 cP is actually 8 plies. Have you ever measured how many CP the score of a position typically changes ply by ply with increasing search depth? It seems to me that 3cP would hardly beat the noise.

I am sure there are also many games were a GM "failed to cash in on his better position in time, after which the opponent escaped". Like other eval parameters, the delayed-loss bonus is a tunable device, that allows you to tune your engine to the fine line between being too greedy and being too indecisive. It is perfectly possible to evne make it dependent on search depth, and give smaller bonus if the 'negative' score was obtained by a deeper search.

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.

Well, in a symmetric search it works both ways. If delaying a loss is good for one side, the other side will automatically try to speed up the loss to take that advantage away.

From what you say here it seems you didn't get the point at all. Trading down is _not_ a gain. Capturing is only encouraged by this scheme if there is no (or not enough) recapture. Otherwise there is no effect.

[Colin]

Thanks, I heard of fail-soft before, but never looked into it.

Looking at this code...
http://www.brucemo.com/compchess/progra ... shing.htm?
It can be seen alpha/beta is stored, I don't understand C/C++ code properly yet, so I'll have to learn it before I can make proper sense out of the record/probe functions given.

Is this pseudocode good to use? And I guess I need to also play the hash move obtained from the probe before I generate/play the other moves, but it doesn't say this in the code.

Also, if playing hash-move first, I may end up playing it again since the move generator will find it if theres no cut off and it ends up generating and playing all the moves.... so is it best to avoid replaying the hash move?

Thanks

[bob]

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.

And the 'opportune moment' is defined as the moment where you cannot drive up the eventual score any further by postponing the gain...

Which is exactly when this algorithm will decide to cash in. As long as other moves are significantly better, the 1 cP delay bonus does not even compete with the noise.

Not if it works as you explain. You have a capture that you can make now, or in 4 moves. If you do the capture right now, your opponent will get a 3 centipawn advantage. If you push it off and make the capture in 4 moves, and defend against the opponents positional threat, he gets no advantage.

Without mucking with the score, you will defer the capture and end up with a score of 0.01... if you do muck with the score, which makes you make the capture now, you end up in 3 moves with a score of -0.03... that isn't a lot, but if it isn't important, why do I have centipawn resolution in my scoring. Uri's idea eliminated this, because the "urgency" score was less than one centipawn, so that you _never_ let the urgency score push you into making a move that gives up any positional edge that can be preserved by delaying the capture...

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

The fact that other scores are non-exact, but might change on deeper search, seem all the more reason to apply the 'no-detours' princilple to these other scores. Gains that are nearby have been verified to much larger depth than the same gain very deep in the tree.

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.

What's that got to do with it??? Trading is not a gain. Going to from a dead drawn position to an even more dead drawn position is not a gain. Even a 'winning' trade (like giving 2P for N in KNPPKNP) is not a gain if it is an easier draw after that trade. If your evaluation says it is, it should receive a major overhaul. But don't blame it on the search!

Give me a break. A draw is a draw. A drawn KRP vs KR is no more or less drawn than a KR vs KR. So the search is irrelevant. The evaluation is irrelevant. But if you trick your evaluation to thinking that KRP vs KR is a "better draw" (for the krp side) than KR vs KR, then you have my "swindle mode". It has _zero_ to do with search. It has everything to do with giving my opponent the best opportunity to make a mistake, and mistakes are far easier in KRP vs KR than in KR vs KR. I guess, therefore, that we are somehow talking apples to oranges again, since your comment doesn't fit in here.

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

Well, +4 cP is actually 8 plies. Have you ever measured how many CP the score of a position typically changes ply by ply with increasing search depth? It seems to me that 3cP would hardly beat the noise.

You are completely missing the point. Sometimes, by deferring a capture, I can hold on to a positional edge because the piece I would use to capture has a second function that helps me. If I use it up first, then I might not be able to hold on to the positional edge.

I prefer to let the search run around in the tree space and maximize the evaluations returned. In my world, RxR Nc3 Nf6 is the same as Nc3 Nf6 RxR, and trying to artificially favor one over the other, when the positions are absolutely identical, is what I call "mucking with the score".

I am sure there are also many games were a GM "failed to cash in on his better position in time, after which the opponent escaped". Like other eval parameters, the delayed-loss bonus is a tunable device, that allows you to tune your engine to the fine line between being too greedy and being too indecisive. It is perfectly possible to evne make it dependent on search depth, and give smaller bonus if the 'negative' score was obtained by a deeper search.

So now you must be saying _your_ search is no good. I hope mine doesn't find a way to win something and then lose the way as the game progresses. If it does, that is a search problem, not an evaluation problem. And I want to fix the problem where it is, not somewhere else.

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.

Well, in a symmetric search it works both ways. If delaying a loss is good for one side, the other side will automatically try to speed up the loss to take that advantage away.

From what you say here it seems you didn't get the point at all. Trading down is _not_ a gain. Capturing is only encouraged by this scheme if there is no (or not enough) recapture. Otherwise there is no effect.

Should I show you a position where you trade a pair of rooks, and win a pawn, and lose the game instantly???

[hgm]

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.

How can that be? The bounds in the table and the search are the same. The table is filled with search results.

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,

Not at all. Mate scores are relative to the position that has that mate score. Scoring a position as mate-in-N means: "N moves after the current position (2*N-1 plies) the opponent wil be checkmated".

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.

Not so. In my case both represent a mate from the current position (current tree level). Did you miss that Alpha and Beta are adjusted before they are passed up the tree?

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,

No, the score of that position is CHECKMATED, meaning checkmate-in-0.

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.

No, at every ply different scores will be stored (supposing this is the PV), as the delayed-loss bonus will be applied to it. At ply =12 a checkmated-in-1 score will be stored, at ply=10 a checkmated-in-2, etc.

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.

The odd plies indeed score the opposite signs, so in this case mate-in-6. I would say that is because you backed up one move from a position with score mated-in-5. Where the root was, is irrelevant.

Now you search a different sequence of moves and you find this position at ply=7, rather than at 3 where you stored it.

OK, so I find a mate-in-6 in the table.

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.

No, there will be no adjustment. The position is a mate-in-6, as after doing 6 moves from it, the opponent will be mated.

For bounds you have the same problem.

I have perceived no problem yet. Just a mate-in-6.

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.

Obviously. So I make sure that the bounds are exactly right. (Bounds here meaning Alpha and Beta?)

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.

Well, the problem is that what you describe, although more clearly than before, actually has little to no resemblance to what I do and described here.

So perhaps it is better that I finish your example with the proper description of what really happens:

After backing up the first branch to ply=3 the best score score there is mate-in-6. This will become the new alpha. Searching the second branch (where we will eventually encounter the same mate-in-6 at ply=7), this will be passed to a ply=4 node as beta=checkmated-in-6. This is below the CurEval (which is never a mate score). So it will be decremented, and become mated-in-5. This will repeat on ply=6, where beta will become mated-in-4, and finally propagate to ply=7, where it will become alpha=mate-in-4 (no adjustments in odd plies, as mate scores >> CurEval).

Now we get a hash hit on the mate-in-6 position. Mate-in-6 is a lower score than mate-in-4. So we will hash prune, and return either mate-in-4 (fail hard) or mate-in-6 (fail soft). Supposing the mating side cannot find any better moves in ply=5 (failing low he will try everything) these scores will eventualy propagate to ply=3, where they arrive (due to delay bonus) as mate-in-8 (soft) or mate-in-6 (hard). But in ply=3 we already had a mate-in-6. So one of them is below alpha, the other exactly at alpha (a characteristic for fail hard, all fail lows will always be exactly at alpha). So the second move will not be chosen, and the mate-in-6 (from ply=3) will prevail over the mate-in-8 (as it should). If this remains PV, the score will arrive as mate-in-7 at ply=1, and as checkmated-in-8 in the root (ply=0).

Clear?

[hgm]

(That last sentence should have been 'checkmated-in-7' at the root. )

[bob]

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.

How can that be? The bounds in the table and the search are the same. The table is filled with search results.

You said you are mucking with your score, adding +1 at every other ply. If a hash entry is stored at ply 4 this time around, the score was mucked up by +2 if I read your post right. But if you get a hit on that entry and compare it to something at ply 10 later, your two scores are not comparable... one was mucked by +2, the other was mucked by +5... that's wrong. and that's the case I was talking about. With PVS that kind of change is much worse because mucking a score pushes outside one edge of the window or the other, possibly in the wrong direction since the edges of the window touch.

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,

Not at all. Mate scores are relative to the position that has that mate score. Scoring a position as mate-in-N means: "N moves after the current position (2*N-1 plies) the opponent wil be checkmated".

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.

Correct. That is why we adjust bounds that are mate scores, so that the bound or score is always mate in N from the current ply. You said you are not doing that, or only doing it for 1/2 the positions. There is another half...

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.

Not so. In my case both represent a mate from the current position (current tree level). Did you miss that Alpha and Beta are adjusted before they are passed up the tree?

Possibly I did. why muck the scores forward and backward? It certainly makes traces harder to follow. And it is work done at every node, in and out, where most of us just pass normal scores up and down the tree, and only adjust what we get from the hash table if it represents a mate-type score, all others are left alone.

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,

No, the score of that position is CHECKMATED, meaning checkmate-in-0.

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.

No, at every ply different scores will be stored (supposing this is the PV), as the delayed-loss bonus will be applied to it. At ply =12 a checkmated-in-1 score will be stored, at ply=10 a checkmated-in-2, etc.

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.

The odd plies indeed score the opposite signs, so in this case mate-in-6. I would say that is because you backed up one move from a position with score mated-in-5. Where the root was, is irrelevant.

The root is never irrelevant. When I search down the tree and find a mate in 4 from the root, I return the following at each ply...

at ply=8, I store mated in 0
at ply=7, I store mate in 1
at ply=6, I store mated in 1
at ply=5, I store mate in 2
at ply=4, I store mated in 2
at ply=3, I store mate in 3
at ply=2, I store mated in 3
at ply=1, I store mate in 4

Each and every one of those scores (or they could be bounds as well) are correct for the ply where they are stored. When I get a hash hit, say for the position stored at ply=3, but I hit it in another path at ply=7, then I get mate in 3 from the table, and I change it to mate in 5, since we are two whole moves removed from the root and those moves have to be played before this forced mate score is valid here.

Now you search a different sequence of moves and you find this position at ply=7, rather than at 3 where you stored it.

OK, so I find a mate-in-6 in the table.

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.

No, there will be no adjustment. The position is a mate-in-6, as after doing 6 moves from it, the opponent will be mated.

For bounds you have the same problem.

I have perceived no problem yet. Just a mate-in-6.

What do you do about bounds? "at least a mate in 6, maybe less, or at worst a mate in 6, maybe longer. those kinds of bounds happen everywhere when searching trees with forced mates. And they also have to be corrected for consistency, because comparing two different mate bounds will lead to wrong answers unless one is corrected to match the other...

If I misunderstand what you are doing, then fine... If I don't then these things can cause anything from being unable to find the shortest mate or longest mate depending on the side, to nothing more than doing extra searching because the mate bounds are not causing cutoffs like they should...

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.

Obviously. So I make sure that the bounds are exactly right. (Bounds here meaning Alpha and Beta?)

Or the bounds you retrieve from the hash table for LOWER/UPPER type entries...

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.

Well, the problem is that what you describe, although more clearly than before, actually has little to no resemblance to what I do and described here.

So perhaps it is better that I finish your example with the proper description of what really happens:

After backing up the first branch to ply=3 the best score score there is mate-in-6. This will become the new alpha. Searching the second branch (where we will eventually encounter the same mate-in-6 at ply=7), this will be passed to a ply=4 node as beta=checkmated-in-6. This is below the CurEval (which is never a mate score). So it will be decremented, and become mated-in-5. This will repeat on ply=6, where beta will become mated-in-4, and finally propagate to ply=7, where it will become alpha=mate-in-4 (no adjustments in odd plies, as mate scores >> CurEval).

Now we get a hash hit on the mate-in-6 position. Mate-in-6 is a lower score than mate-in-4. So we will hash prune, and return either mate-in-4 (fail hard) or mate-in-6 (fail soft). Supposing the mating side cannot find any better moves in ply=5 (failing low he will try everything) these scores will eventualy propagate to ply=3, where they arrive (due to delay bonus) as mate-in-8 (soft) or mate-in-6 (hard). But in ply=3 we already had a mate-in-6. So one of them is below alpha, the other exactly at alpha (a characteristic for fail hard, all fail lows will always be exactly at alpha). So the second move will not be chosen, and the mate-in-6 (from ply=3) will prevail over the mate-in-8 (as it should). If this remains PV, the score will arrive as mate-in-7 at ply=1, and as checkmated-in-8 in the root (ply=0).

Clear?

I am not sure. Let me have a bit of time to think about it after I fix a couple of cluster problems I am working on...

[Jacob]

Is this pseudocode good to use? And I guess I need to also play the hash move obtained from the probe before I generate/play the other moves, but it doesn't say this in the code.

This pseudo-code works well for me, with a few modifications. My probe function retrieves the hash move so it can be tried, and I set the hash move in Record(). And I use a different replacement scheme (two entries; depth-preferred and always-replace)

Also, if playing hash-move first, I may end up playing it again since the move generator will find it if theres no cut off and it ends up generating and playing all the moves.... so is it best to avoid replaying the hash move?

Yes, I think that'd be best. I test to make sure I don't replay hash or killer moves.

[Harald Johnsen]

Thanks, I heard of fail-soft before, but never looked into it.

Looking at this code...
http://www.brucemo.com/compchess/progra ... shing.htm?
It can be seen alpha/beta is stored, I don't understand C/C++ code properly yet, so I'll have to learn it before I can make proper sense out of the record/probe functions given.

Is this pseudocode good to use? And I guess I need to also play the hash move obtained from the probe before I generate/play the other moves, but it doesn't say this in the code.

Bruce is using fail-hard, I think this won't work well with a null window.

Also, if playing hash-move first, I may end up playing it again since the move generator will find it if theres no cut off and it ends up generating and playing all the moves.... so is it best to avoid replaying the hash move?

Thanks

You probe the hash table first because you can have a usable exact score or a cutoff.
Then you generate your moves, but to play the hash move first you want your sort fucntion to give it a high score.

HJ.

[hgm]

I am not sure. Let me have a bit of time to think about it after I fix a couple of cluster problems I am working on...

OK, I will defer answering your post until after you have pondered this.

In the mean time, let me tell you a story that will teach us a moral lesson.

Suppose I am searching, and at ply=3 the stm finds itself checkmated. The node gets the score mated-in-0. The negamax sign flip makes this into mate-in-1 at ply=2. Suppose there are no escapes to the mate, so the score backs up all the way to the root, adjusted by the delay bonus to mate-in-2.

This mate-in-2 now becomes the new alpha in the root, and we start to search the other moves. (For simplicity, suppose this is not PVS but plain alpha-beta.) Passing the window bounds up the tree makes beta = mated-in-1 (the opposite of mate-in-2) at ply=1. But since this is << CurEval, it is preadjusted to mated-in-0.

Now something interesting happens. When we start searching for the best move we initialize BestScore to -INFINITY. (This is fail soft, so we don't start at Alpha.) Now the lowest score a position can ever have, is mated-in-0, so it seems logical to equate the two: mated-in-0 = -INFINITY. But the initial BestScore of -INFINITY now is >= Beta ! It causes a beta cutoff very similar to the stand-pat cutoff in QS, where you would initialize BestScore to CurEval. The ply=1 Node would always return, without searching any moves, no matter what the requested search depth was, just because it was called with a Beta = mated-in-1.

Thus, no matter how deep a search you order from the root, if there is one move in the root that has already found a mate-in-2 (a 3-ply branch), all the other branches will be pruned at ply=1, two ply earlier, reporting a fail low to their parent (in this case the root). And quite justly so: if the osition at ply=1 is not a checkmate itself (which I suppose to be tested before testing for the cutoff), it is completely pointless to search on, as whatever happens, we can never get anything in the root that is better than the mate-in-2 we already have there. (It is not possible to checkmate yourself on your own ply.)

The delayed-loss bonus, without any extra programming, will lead to automatic limitation of the search depth of any branch, to two ply below the earliest confirmed checkmate (i.e. just enough to encounter a shorter checkmate).

You get that FOR FREE, just by implementing the delayed-loss bonus!

[bob]

I am not sure. Let me have a bit of time to think about it after I fix a couple of cluster problems I am working on...

OK, I will defer answering your post until after you have pondered this.

In the mean time, let me tell you a story that will teach us a moral lesson.

Suppose I am searching, and at ply=3 the stm finds itself checkmated. The node gets the score mated-in-0. The negamax sign flip makes this into mate-in-1 at ply=2. Suppose there are no escapes to the mate, so the score backs up all the way to the root, adjusted by the delay bonus to mate-in-2.

This mate-in-2 now becomes the new alpha in the root, and we start to search the other moves. (For simplicity, suppose this is not PVS but plain alpha-beta.) Passing the window bounds up the tree makes beta = mated-in-1 (the opposite of mate-in-2) at ply=1. But since this is << CurEval, it is preadjusted to mated-in-0.

Now something interesting happens. When we start searching for the best move we initialize BestScore to -INFINITY. (This is fail soft, so we don't start at Alpha.) Now the lowest score a position can ever have, is mated-in-0, so it seems logical to equate the two: mated-in-0 = -INFINITY. But the initial BestScore of -INFINITY now is >= Beta ! It causes a beta cutoff very similar to the stand-pat cutoff in QS, where you would initialize BestScore to CurEval. The ply=1 Node would always return, without searching any moves, no matter what the requested search depth was, just because it was called with a Beta = mated-in-1.

Thus, no matter how deep a search you order from the root, if there is one move in the root that has already found a mate-in-2 (a 3-ply branch), all the other branches will be pruned at ply=1, two ply earlier, reporting a fail low to their parent (in this case the root). And quite justly so: if the osition at ply=1 is not a checkmate itself (which I suppose to be tested before testing for the cutoff), it is completely pointless to search on, as whatever happens, we can never get anything in the root that is better than the mate-in-2 we already have there. (It is not possible to checkmate yourself on your own ply.)

The delayed-loss bonus, without any extra programming, will lead to automatic limitation of the search depth of any branch, to two ply below the earliest confirmed checkmate (i.e. just enough to encounter a shorter checkmate).

You get that FOR FREE, just by implementing the delayed-loss bonus!

THe way I update scores and bounds causes the same thing. I never spend/waste time searching for mates that are outside the window. Of course there is always wasted effort in a depth-first approach, but so long as the bounds are properly maintained, the longer-than-desired (or shorter-than-desired if you are losing) mates end up outside the A-B window and are not considered.