hashing question

[adams161]

I asked earlier about hashing and got a good answer to the fail highs and fail lows and how to track score. Now what concerns me is what value to hash when the king is captured. I return 7500 - side where side is ply searched so a ply 3 mate is 7497. If i hash this score it will be innacurate becase it means the king is captured at that depth and it should be 7500 minus current depth. If i dont hash king captures the score will be returned and king captures will be hashed indirectly at other depths as alpha or beta changes. Any ideas on how to handle this appreciated.

Mike

[Ron Murawski]

Never hash illegal moves! If it turns out a move is illegal it's time to try a different move. If all moves are illegal you are either in stalemate or checkmate.

Ron

[Harald]

I asked earlier about hashing and got a good answer to the fail highs and fail lows and how to track score. Now what concerns me is what value to hash when the king is captured. I return 7500 - side where side is ply searched so a ply 3 mate is 7497. If i hash this score it will be innacurate becase it means the king is captured at that depth and it should be 7500 minus current depth. If i dont hash king captures the score will be returned and king captures will be hashed indirectly at other depths as alpha or beta changes. Any ideas on how to handle this appreciated.

Mike

A few days ago I wrote this as an answer to a very similar question:

When you see silly mate scores in a program with new transposition tables
(hash tables) then you should try this:

When your normal search finds a mate position it gets the
score = mate_score - ply.
You may return this score through the search function back to the root.
If you want to save the position and its score in a hash entry you have to
adjust the score first.
if ( score < -7000 ) hash_score = score - ply
if ( score > 7000 ) hash_score = score + ply
If you read a score from the hash table the first thing to do is to adjust
it again to the current ply.
if ( hash_score < -7000 ) score = hash_score + ply
if ( hash_score > 7000 ) score = hash_score - ply
Then you can use this score to check against alpha and beta or you
return it.

Example:
At ply 8 you see a mate and its score is 8000 - 8 = 7992.
Hash it as hash_score = 7992 + 8 = 8000.
The hashed position has a score "immediate mate"
You may perhaps return the score 7992.
At ply 7 it is seen as -7992.
Hash it as hash_score = -7992 - 7 = -7999.
This hashed position has a score "mated in 1 half move"
You may perhaps return the score -7992.
At ply 6 it is seen as 7992.
Hash it as hash_score = 7992 + 6 = 7998.
This hashed position has a score "mate in 2 half moves"
This is position #pos# in my example.
You may perhaps return the score 7992.
...
At ply 10 in another variant you test the hash table and find the
position #pos# again. It has the hash_score 7998 and therefore
score = 7998 - 10 = 7988
That is a mate in 12 half moves.
You may use or return this score.
...
At ply 4 in another variant you test the hash table and find the
position #pos# again. It has the hash_score 7998 and therefore
score = 7998 - 4 = 7994
That is a mate in 6 half moves.
You may use or return this score.

[bob]

I asked earlier about hashing and got a good answer to the fail highs and fail lows and how to track score. Now what concerns me is what value to hash when the king is captured. I return 7500 - side where side is ply searched so a ply 3 mate is 7497. If i hash this score it will be innacurate becase it means the king is captured at that depth and it should be 7500 minus current depth. If i dont hash king captures the score will be returned and king captures will be hashed indirectly at other depths as alpha or beta changes. Any ideas on how to handle this appreciated.

Mike

Don't hash anything, as that is an illegal position and should not have any searching done after such a move is discovered...

[adams161]

yea but if i return a score say king value minus depth, on the previous ply it may get hashed. And that score is relative to teh depth. Say i value a king at 7500 and find a king capture on depth 5. i return 7495 ( i've fixed it now to return beta if 7495 is >=beta ). on depht 4 or depth 3 that score may become incorporated into the hash table, Problem is at another branch it may not be 7495, so when returned if it changes alpha on depth 3 it gets hashed. Not quite sure i got a handle on this.

Mike

[hgm]

Hashing in a king-capture engine is not really different from in an engine that recognizes checkmate as game end. If you believe that it makes sense to hash QS nodes, (with or without stand-pat cutoff), then it also makes sense to hash nodes where you can capture the King. To figure out if you can capture the King would require you to run the move generator (or at least the capture generator), and and extract the most-valuable victim. That is just as much work as you would have in a QS node where the best capture is futile, and in QS nodes where the eval score causes a beta cutoff there is even less work. But all that work you can save when you have a hash hit on this node. So why not?

To recognize if the move was legal in the parent node, for the purpose of counting legal moves, and deciding between checkmate and stalemate if there are none, you would of course have to realize that the kludge of subtracting the depth from the score makes the illegal-move score depth-dependent.

You might want to add code that accepts the King-capture score irrespected of the requested search depth, though. In principle you could achieve that by scoring it with 'infinite' draft (I used to do that in older micro-Max versions), but that might interfere with your replacement algorithm, cramming-up the depth-preferred part of the table with King-capture positions. While such positions are only slightly more valuable than QS nodes, in terms of the work that a hit will save you. (Slightly more, because they can satisfy any requested search depth with an exact score, while QS nodes can only satisfy other QS probes.)

[adams161]

if i score 7500-9 or 7491 for a king capture on depth 9 and return it then all earlier depths that utitleze that score in the hash table will use 7491 or -7491. lets say it gets added to the hash table at depth 5, how do you figure out when it comes up again how to adjust it. It could also get added somewhere else so you have 7491 or -7491 in twice but at two different depths and i think the information about the true depht is lost, you really just have relative information. I cant just adjust it when i see the score is over 7400 or under -7400 becuase I dont think the true depth is really contained in any way that i can extract it from the score anymore. Parituclarly if i dont hash king captures but only if the score persists when i return 7500 -side or beta whichever is lower.

Mike

[hgm]

What you are pointing out is simply a general drawback of the 'MATE-minus-depth' kludge: you have to correct scores all over the place, as the meaning of the numeric value of the scores is not fixed. This is why I prefer to simply return the Distance To Mate (or, if you want, Distance To King capture) for any node, and store that in the hash table as well.

[adams161]

so when i add a score , say 7491 or 7500-9 got returned, and i'm on depth 3 when i add to hash, knowing the score is 7491 or mate in 9 from root ( not a true mate but actually 1 move beyond mate since king is captures but i think i can ignore that ) now i'm on ply 3 so i know the king is captured in 6 plys, i score distance from king capture ( 6 )? If i find a hashed node over 7400 worth of score i make the score 7500 minus 6 or 7494?

Mike

[bob]

yea but if i return a score say king value minus depth, on the previous ply it may get hashed. And that score is relative to teh depth. Say i value a king at 7500 and find a king capture on depth 5. i return 7495 ( i've fixed it now to return beta if 7495 is >=beta ). on depht 4 or depth 3 that score may become incorporated into the hash table, Problem is at another branch it may not be 7495, so when returned if it changes alpha on depth 3 it gets hashed. Not quite sure i got a handle on this.

Mike

Then you probably are going to have a serious bug. You should not be able to store a score returned as a result of making an illegal move. You normally don't store a score unless you get a beta cutoff or else search all moves and then store the best score (or alpha if none) you found. I don't see how you could legitimately store something after searching a single illegal move, unless all moves are illegal. In which case you should recognize the stalemate/checkmate condition and set the appropriate score...

I'm not sure how you could do what you are saying, legitimately...