Iterative deepening does not always find the shortest mate

[AndrewShort]

I have implemented basic iterative deepening (not internal ID), and if at the completion of any iteration the score indicates a forced mate against the human, the search stops with that iteration. I don't bother to keep searching, even if there is time remaining.

In any iteration, the shortest mating path is always favored, and mating scores are adjusted properly in the hash table.

This all works very well, and I know that at the completion of any iteration, if a forced mating score against the human is returned, I know for a fact that in that iteration there could not have been a shorter mating path.

I have discovered, however, that on very rare occasions, the shortest mating path is not necessarily returned, and that it is due to 'free depth' one gets from hashing. For example, after completing an iteration where maxply was 21, it might correctly return a score indicating a forced mating move ending on ply 31. And given the state of the hash table and so forth, I know that mate on ply 31 really is the shortest mate after searching 21 plies. It is perfectly possible, however, that had the iterations continued to a 23 or 25 depth search, the state of the hash tables in that search could have found a mate earlier than ply 31, say on ply 25 instead. So letting the search run deeper would have found a mate 6 plies earlier.

So, in the example above, if after iteration depth=21 returns a mating score suggesting mate on ply 31, then the only way I can *really* know that is the shortest mate would be to search through ply 31 and see if there is anything shorter, and if not, then I know for a fact mate on ply 31 really is the shortest mate.

I assume most engines don't bother doing that?

[michiguel]

I have implemented basic iterative deepening (not internal ID), and if at the completion of any iteration the score indicates a forced mate against the human, the search stops with that iteration. I don't bother to keep searching, even if there is time remaining.

In any iteration, the shortest mating path is always favored, and mating scores are adjusted properly in the hash table.

This all works very well, and I know that at the completion of any iteration, if a forced mating score against the human is returned, I know for a fact that in that iteration there could not have been a shorter mating path.

I have discovered, however, that on very rare occasions, the shortest mating path is not necessarily returned, and that it is due to 'free depth' one gets from hashing. For example, after completing an iteration where maxply was 21, it might correctly return a score indicating a forced mating move ending on ply 31. And given the state of the hash table and so forth, I know that mate on ply 31 really is the shortest mate after searching 21 plies. It is perfectly possible, however, that had the iterations continued to a 23 or 25 depth search, the state of the hash tables in that search could have found a mate earlier than ply 31, say on ply 25 instead. So letting the search run deeper would have found a mate 6 plies earlier.

So, in the example above, if after iteration depth=21 returns a mating score suggesting mate on ply 31, then the only way I can *really* know that is the shortest mate would be to search through ply 31 and see if there is anything shorter, and if not, then I know for a fact mate on ply 31 really is the shortest mate.

I assume most engines don't bother doing that?

Gaviota bothers to do that. It does not add or detract any ELO point, but, if there is time to think, why not searching a little bit more to be more elegant and find the shorter one? Sometimes take a long time, but sometimes is quick because the engine search with alpha and beta set for mates.

If Gaviota sees a mate in ply 31, it stop searching at ply 31. At that point, it is impossible to find a shorter one.

Many times Gaviota is very accurate to see in how many moves it is going to be mated

Miguel

[Harald Johnsen]

I have implemented basic iterative deepening (not internal ID), and if at the completion of any iteration the score indicates a forced mate against the human, the search stops with that iteration.

I don't stop the search in analysis mode.

I don't stop the search as soon as i find a mate score, I stop only when the mate score is identical on the last 2 iterations. But anyway why would you stop the search on mate score ? To spare a few seconds ?

HJ.

[hgm]

Joker only stops iterating when the mate is within the (nominal) horizon. This still is no absolute guarantee there is no shorter mate, as some branches are reduced to below the nominal depth. But I have enever seen a problem because of that.

Micro-Max simply iterates until it reaches its maximum depth (98, or what was set in the sd command), if the time reserved for the move is not used up before that. Close to the mate it still speeds up, because the delayed-loss bonus automatically causes mate-distance pruning as well, and no branch can go deeper than a mate in the PV.

[bob]

I have implemented basic iterative deepening (not internal ID), and if at the completion of any iteration the score indicates a forced mate against the human, the search stops with that iteration. I don't bother to keep searching, even if there is time remaining.

In any iteration, the shortest mating path is always favored, and mating scores are adjusted properly in the hash table.

This all works very well, and I know that at the completion of any iteration, if a forced mating score against the human is returned, I know for a fact that in that iteration there could not have been a shorter mating path.

I have discovered, however, that on very rare occasions, the shortest mating path is not necessarily returned, and that it is due to 'free depth' one gets from hashing. For example, after completing an iteration where maxply was 21, it might correctly return a score indicating a forced mating move ending on ply 31. And given the state of the hash table and so forth, I know that mate on ply 31 really is the shortest mate after searching 21 plies. It is perfectly possible, however, that had the iterations continued to a 23 or 25 depth search, the state of the hash tables in that search could have found a mate earlier than ply 31, say on ply 25 instead. So letting the search run deeper would have found a mate 6 plies earlier.

So, in the example above, if after iteration depth=21 returns a mating score suggesting mate on ply 31, then the only way I can *really* know that is the shortest mate would be to search through ply 31 and see if there is anything shorter, and if not, then I know for a fact mate on ply 31 really is the shortest mate.

I assume most engines don't bother doing that?

Your basic assumption is wrong. Here's why. Suppose there are two ways to mate your opponent

The first mate you find has a lot of checks, which causes you to extend your search deep enough to see a mate in 10, for a basic 6 ply search.

The second mate you want to find is a mate in 5, but the first 4 moves are non-checking moves, so you have no search extensions, and you will need at least a 9 ply search to see that this forces mate.

So how can you make your 6 ply search find that mate that has no extensions in the path? It won't happen. The only given is that if there is a mate in N, you need to search to depth 2N-1 to be certain that is the shortest possible mate... Otherwise you will always see the problem you are experiencing...

When you add in search reductions along with extensions, then this will happen even more frequently.

[bob]

I have implemented basic iterative deepening (not internal ID), and if at the completion of any iteration the score indicates a forced mate against the human, the search stops with that iteration. I don't bother to keep searching, even if there is time remaining.

In any iteration, the shortest mating path is always favored, and mating scores are adjusted properly in the hash table.

This all works very well, and I know that at the completion of any iteration, if a forced mating score against the human is returned, I know for a fact that in that iteration there could not have been a shorter mating path.

I have discovered, however, that on very rare occasions, the shortest mating path is not necessarily returned, and that it is due to 'free depth' one gets from hashing. For example, after completing an iteration where maxply was 21, it might correctly return a score indicating a forced mating move ending on ply 31. And given the state of the hash table and so forth, I know that mate on ply 31 really is the shortest mate after searching 21 plies. It is perfectly possible, however, that had the iterations continued to a 23 or 25 depth search, the state of the hash tables in that search could have found a mate earlier than ply 31, say on ply 25 instead. So letting the search run deeper would have found a mate 6 plies earlier.

So, in the example above, if after iteration depth=21 returns a mating score suggesting mate on ply 31, then the only way I can *really* know that is the shortest mate would be to search through ply 31 and see if there is anything shorter, and if not, then I know for a fact mate on ply 31 really is the shortest mate.

I assume most engines don't bother doing that?

Gaviota bothers to do that. It does not add or detract any ELO point, but, if there is time to think, why not searching a little bit more to be more elegant and find the shorter one? Sometimes take a long time, but sometimes is quick because the engine search with alpha and beta set for mates.

If Gaviota sees a mate in ply 31, it stop searching at ply 31. At that point, it is impossible to find a shorter one.

Many times Gaviota is very accurate to see in how many moves it is going to be mated

Miguel

There is one restriction you must have... You can always stop on a mate in N, if this is the first mate you have found. But the _next_ search, after your opponent moves can not stop on the first mate. It must search until it finds a mate in N-1, else you can end up repeating and drawing because you keep finding a mate in N every time you want to make a move, not making any progress...

[hgm]

That might not be feasible. If he finds a mate in 31 ply in a 21-ply search by sheer luck in hash replacements, it might not be able to find a mate in 29-ply on the next move before he actually reaches 29 ply, and might have forfeited on time long before that.

[michiguel]

That might not be feasible. If he finds a mate in 31 ply in a 21-ply search by sheer luck in hash replacements, it might not be able to find a mate in 29-ply on the next move before he actually reaches 29 ply, and might have forfeited on time long before that.

That't right, but if I keep the proper information, i. e. a proper PV and/or the right hashtable entries I should be able to find a mate in 29 plies. I never thought about it, but in the case I return after Iteration deepening a mate score, I better make sure that either I have a PV or the hashtable with the proper mate information has not been erased, which is the hashtable stuffed with the PV entries.

Miguel

[bob]

That might not be feasible. If he finds a mate in 31 ply in a 21-ply search by sheer luck in hash replacements, it might not be able to find a mate in 29-ply on the next move before he actually reaches 29 ply, and might have forfeited on time long before that.

I wasn't suggesting it as something that _must_ be done. I was just suggesting it as a way to not stop searching until you either (a) find the shortest mate (depth=2N-1) or run out of time. That's how I do it in Crafty. If I have time, I will always find the shortest mate, otherwise I will take whatever mate I have found and go with that, requiring that the next search reduce that mate score by 1 to avoid aimlessly checking the opponent without any progress being made.

[wgarvin]

That might not be feasible. If he finds a mate in 31 ply in a 21-ply search by sheer luck in hash replacements, it might not be able to find a mate in 29-ply on the next move before he actually reaches 29 ply, and might have forfeited on time long before that.

Would it be possible, after finding the mate for the first time, to scan every entry in the hash table and if it has a mate score in it, flag it as "never replace this entry for the rest of the game" ? That might increase the chances of those entries still being available after the opponent moves, when you have to search and find that same mate again (or some other mate).

Also, is there any way to tell the difference between old entries with a mate score, and entries with a mate score that actually affected the result of the search? (e.g. if you have a "live on the previous search" bit in the hash entry already for replacement reasons?)

Even if this was possible, could locking mate entries into the hash table somehow cause problems for other parts of the search?