Iterative deepening does not always find the shortest mate

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Iterative deepening does not always find the shortest ma

Post by bob » Wed Apr 23, 2008 11:40 pm

wgarvin wrote:
hgm wrote: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?
There's a definite risk. If you store a mate score with a "infinite" (which implies never replace maybe) depth, you need to be sure that represents the _shortest_ mate from that position, and that is not an easy thing to guarantee with today's extensions and reductions embedded everywhere within the search tree. You have to be able to make progress, and not enter one of those mate in N, mate in N, mate in N debacles where you are unable to make progress because you keep getting the wrong hash score from the hash table...

User avatar
michiguel
Posts: 6389
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Iterative deepening does not always find the shortest ma

Post by michiguel » Thu Apr 24, 2008 3:38 am

bob wrote:
wgarvin wrote:
hgm wrote: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?
There's a definite risk. If you store a mate score with a "infinite" (which implies never replace maybe) depth, you need to be sure that represents the _shortest_ mate from that position, and that is not an easy thing to guarantee with today's extensions and reductions embedded everywhere within the search tree. You have to be able to make progress, and not enter one of those mate in N, mate in N, mate in N debacles where you are unable to make progress because you keep getting the wrong hash score from the hash table...
Maybe it can be stored as a "lower bound" and infinite depth.

Miguel

Harald Johnsen

Re: Iterative deepening does not always find the shortest ma

Post by Harald Johnsen » Thu Apr 24, 2008 8:14 am

wgarvin wrote: 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).
You don't want to keep unreachable positions in your hash table, a lot of the positions stored in your TT are unreachable after a move, and if it's a pawn move then that's a very high number of positions (pieces can be shuffled forever).

Keeping important positions in the hash table is to be handled by your replacement scheme. You have a date entry in your hash table, so don't replace entries from the previous search, and you'll have an higher probability to be able to probe your mate positions with no special hacking.

HJ.

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Iterative deepening does not always find the shortest ma

Post by bob » Sun Apr 27, 2008 4:13 pm

michiguel wrote:
bob wrote:
wgarvin wrote:
hgm wrote: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?
There's a definite risk. If you store a mate score with a "infinite" (which implies never replace maybe) depth, you need to be sure that represents the _shortest_ mate from that position, and that is not an easy thing to guarantee with today's extensions and reductions embedded everywhere within the search tree. You have to be able to make progress, and not enter one of those mate in N, mate in N, mate in N debacles where you are unable to make progress because you keep getting the wrong hash score from the hash table...
Maybe it can be stored as a "lower bound" and infinite depth.

Miguel
That might (or might not) help. That would give you a cutoff, and a fail high, but you could never resolve the score on the re-search, so you have the same problem more or less, in determining which is best (shortest) without getting into a cycle that you hope will be terminated before a draw.

User avatar
michiguel
Posts: 6389
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Iterative deepening does not always find the shortest ma

Post by michiguel » Sun Apr 27, 2008 10:55 pm

bob wrote:
michiguel wrote:
bob wrote:
wgarvin wrote:
hgm wrote: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?
There's a definite risk. If you store a mate score with a "infinite" (which implies never replace maybe) depth, you need to be sure that represents the _shortest_ mate from that position, and that is not an easy thing to guarantee with today's extensions and reductions embedded everywhere within the search tree. You have to be able to make progress, and not enter one of those mate in N, mate in N, mate in N debacles where you are unable to make progress because you keep getting the wrong hash score from the hash table...
Maybe it can be stored as a "lower bound" and infinite depth.

Miguel
That might (or might not) help. That would give you a cutoff, and a fail high, but you could never resolve the score on the re-search, so you have the same problem more or less, in determining which is best (shortest) without getting into a cycle that you hope will be terminated before a draw.
I might help, or maybe not. However, I believe it won't hurt. right?

Miguel

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Iterative deepening does not always find the shortest ma

Post by bob » Mon Apr 28, 2008 12:49 am

michiguel wrote:
bob wrote:
michiguel wrote:
bob wrote:
wgarvin wrote:
hgm wrote: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?
There's a definite risk. If you store a mate score with a "infinite" (which implies never replace maybe) depth, you need to be sure that represents the _shortest_ mate from that position, and that is not an easy thing to guarantee with today's extensions and reductions embedded everywhere within the search tree. You have to be able to make progress, and not enter one of those mate in N, mate in N, mate in N debacles where you are unable to make progress because you keep getting the wrong hash score from the hash table...
Maybe it can be stored as a "lower bound" and infinite depth.

Miguel
That might (or might not) help. That would give you a cutoff, and a fail high, but you could never resolve the score on the re-search, so you have the same problem more or less, in determining which is best (shortest) without getting into a cycle that you hope will be terminated before a draw.
I might help, or maybe not. However, I believe it won't hurt. right?

Miguel
Tough to answer without a lot of thought... If you populate the hash table with lots of "mate in N or less moves" and flag 'em with an infinite draft, I am not sure what the overall effect might be. But since the hash table is trusted completely, the first rule has to be "accuracy is critical". "mate in at least N" should not produce any errors,

Post Reply