Transposition Tables

[Chan Rasjid]

Hello,

Maybe Muller should note the way Dr Hyatt does it :-

loss_mate scores stored in TT:-
-infi == checkmate
-infi + 2 == checkmate in 1
-infi + 4 == checkmate in 2
-infi + 6 == checkmate in 3, ...etc

win_mate scores stored in TT:-
infi - 1 == mate in 1
infi - 3 == mate in 2
infi - 5 == mate in 3, etc...

say the best score at root is infi - 7, the hashed score for this position (A) infi - 7;

If in a much earlier search and pos A was probed and has an exact hit, the hashed score would have to be infi -7. if ply was 32(must be even), it would return inf - 7 -32, mate in 20.

Rasjid

[bob]

Then I don't understand anymore what we are talking about.

I thought the whole point was that the non-mating branches never could get any deeper than N-2 ply, when there is a mate-in-N. At least, that was my point.

Come to think of it, I already don't understand your remark "that's not a hashing issue". Of course it is not a hashing issue, nothing is ever a hashing issue. Hashing is transparant, just a trick to reproduce a search result at lower cost than redoing the search. But the results are the same. So why mention the obvious? I must be missing something...

I don't follow any of the above.

1. _all_ branches reach at least depth N. They can never be cut off early by alpha/beta. This is a depth-first search strategy. The only branches that don't reach depth N (ignoring search reductions) are those that end due to hash hits, or forced mates or forced draws...

2. hashing has nothing to do with an engine taking a long time to play a simple forced mate. Not all programs stop the search when they find a mate, on the hope that they can find a shorter mate next iteration, because many testers criticize engines that don't find the shortest mate in problem positions. Hashing has nothing to do with this. I didn't bring it up, you did...

[hgm]

Not in my system, where you can get a beta cutoff before having searched any moves. Then a branch would terminate at lower depth, like branches that end in mate / stalemate /repdraws.

[bob]

Not in my system, where you can get a beta cutoff before having searched any moves. Then a branch would terminate at lower depth, like branches that end in mate / stalemate /repdraws.

If you re-read my post, I gave hash hits as one way to terminate the search early. But not every branch is going to do that, particularly while searching the PV each new iteration.

[hgm]

You keep bringing up hash hits. This has nothing whatsoever to do with hash hits.

Imagine this is an engine _without_ any hash tables.

If there is a mate-in-4 from the root (7 ply) _no_ other branch from the root will be longer than 5 ply. Even if the requested depth at the root is 49. No hash tables. No hash hits. No hash prunings. Just plain alpha-beta + ID, with the best move of the previous iteration searched first.

[bob]

You keep bringing up hash hits. This has nothing whatsoever to do with hash hits.

Imagine this is an engine _without_ any hash tables.

If there is a mate-in-4 from the root (7 ply) _no_ other branch from the root will be longer than 5 ply. Even if the requested depth at the root is 49. No hash tables. No hash hits. No hash prunings. Just plain alpha-beta + ID, with the best move of the previous iteration searched first.

Sorry, in that case you are wrong. If I do a 20 ply search, even after finding a mate in 5, most branches are going to 20 plies. The only ones that won't are the ones that end in a forced mate themselves, or that end in a forced draw. Otherwise there is no way to do a cutoff until you go down to the tip and work your way back up.

Remember. "depth first". So without hash tables, what you are saying will never happen. If it wasn't a depth-first approach, you would have a point, but depth-first behaves exactly as I explained. If you want to try to explain an example, I'll be glad to join in and explain what happens...

[hgm]

Sorry, in that case you are wrong. If I do a 20 ply search, even after finding a mate in 5, most branches are going to 20 plies.

If you want to try to explain an example, I'll be glad to join in and explain what happens...

I would say the quote below pretty much satisfies that request.

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.

.

And... It might be useful if in the future you would actually _read_ what others post before commenting on it. Just a thought...

[Uri Blass]

You keep bringing up hash hits. This has nothing whatsoever to do with hash hits.

Imagine this is an engine _without_ any hash tables.

If there is a mate-in-4 from the root (7 ply) _no_ other branch from the root will be longer than 5 ply. Even if the requested depth at the root is 49. No hash tables. No hash hits. No hash prunings. Just plain alpha-beta + ID, with the best move of the previous iteration searched first.

Sorry, in that case you are wrong. If I do a 20 ply search, even after finding a mate in 5, most branches are going to 20 plies. The only ones that won't are the ones that end in a forced mate themselves, or that end in a forced draw. Otherwise there is no way to do a cutoff until you go down to the tip and work your way back up.

Remember. "depth first". So without hash tables, what you are saying will never happen. If it wasn't a depth-first approach, you would have a point, but depth-first behaves exactly as I explained. If you want to try to explain an example, I'll be glad to join in and explain what happens...

This is simply not correct.

If you find a forced mate in 5 you only need to remember the fact that you found mate in 5 to tell you that searching lines of more than 7 plies are useless because they cannot be shorter mate than mate in 5.

You simply decide about rules when not to search based on alpha beta and the ply of the search(you can have rules to change alpha and beta in case that they are mate score based on the ply of the search and when they are mate score you will simply have alpha>=beta and cutoff when the ply is too big).

Uri

[hgm]

Indeed. And this is the reason why it is useful to adjust Alpha and Beta when passing them up the tree, as my scheme does. Wheter you want to reserve that for mate scores of just for any future gain is a matter of taste / tuning, and is discussed in another thread.

[bob]

Sorry, in that case you are wrong. If I do a 20 ply search, even after finding a mate in 5, most branches are going to 20 plies.

If you want to try to explain an example, I'll be glad to join in and explain what happens...

I would say the quote below pretty much satisfies that request.

See below for why this is wrong...

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.

Here is why moves go beyond the depth needed to find the mate.

If you find a mate in 3 from the root, you find that the side on move is mated at ply=6. No arguments there. But you have to realize that almost no branches end in mate scores. And for _every_ branch that does not reach a forced mate, you _must_ search all the way to the tip to get a score that will cause cutoffs as you back up the tree since you have found a forced mate already. But if you are doing a 20 ply search, and find a single mate in 3 from the root, all the rest of the root braches are going to go all the way to ply=20 and there is absolutely no way to prevent that since we are using a depth-first search algorithm. Since in the absence of a mate score on a path, no score is produced until you reach remaining-depth = 0 and call the q-search and ultimately the evaluation procedure.

So, every iteration you search takes longer and longer, and there's no solution to that within the alpha/beta framework.

With all of that, I don't follow any of your reasoning since the tree doesn't miraculously get truncated at ply=6 for all branches, just because you found a mate in 3 on the first branch.

Note also that even the first move which is a forced mate is going to have _many_ branches that must be searched to ply=20 as well, because any branch that doesn't end in a forced mate or draw can't get a score unless it is backed up from the tips. That's why I do not understand your original statement...

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

Being "pruned 2 plies earlier" does not mean they don't get searched to full depth however. You _must_ back up non-mate scores from the tips. Not from magic scores created at interior nodes. Because then you are not doing alpha/beta at all...

The above explanation is simply wrong, as it appears you beleve that now suddenly no search branch goes beyond ply=6 when doing a 20 ply search. And that absolutely does not work that way..

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

Again, that is simply wrong. Just set up a position with your program which is a mate in 2 and print the tree for a 10 ply search. The only way no branch reaches depth=10 is if every possible move that the winning side can play, at any ply, leads to a mate in 2 or better. I've never seen such a position.

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

The only question is, "what" do you get for free. You certainly can't get a tree where no branches extend beyond 6 plies...

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.

.

And... It might be useful if in the future you would actually _read_ what others post before commenting on it. Just a thought...