Testing Transposition Tables

[cms271828]

Excellent,
This line makes a lot of difference..

Code: Select all

if(score>=8000-MAXD_) break; // Found mate, stop ID

All the puzzles seem to work now, but I got some slightly strange output in this mate in 15 ply puzzle,

[d]1K6/8/k7/8/8/8/1R6/8 w 1-0

Depth=1 BM=Rb7 score=521 eval-count=16 PV=Rb7[1]
Depth=2 BM=Rb7 score=525 eval-count=16 PV=Rb7 --> Ka5[2]
Depth=3 BM=Rb7 score=527 eval-count=318 PV=Rb7 --> Ka5 --> Rc7[3]
Depth=4 BM=Rd2 score=526 eval-count=201 PV=Rd2 --> Ka5 --> Rd6 --> Ka4[4]
Depth=5 BM=Ra2 score=528 eval-count=2138 PV=Ra2 --> Kb5 --> Ra7 --> Kb6 --> Re7[5]
Depth=6 BM=Re2 score=526 eval-count=1353 PV=Re2 --> Ka5 --> Re4 --> Kb6 --> Re6[5]
Depth=7 BM=Ra2 score=528 eval-count=8412 PV=Ra2 --> Kb5 --> Ra1 --> Kb4 --> Ra7[5]
Depth=8 BM=Re2 score=527 eval-count=4789 PV=Re2 --> Ka5 --> Re4 --> Kb5 --> Rf4 --> Ka6[6]
Depth=9 BM=Rf2 score=528 eval-count=28926 PV=Rf2 --> Ka5 --> Rf4 --> Kb6 --> Rf5[5]
Depth=10 BM=Rf2 score=528 eval-count=5959 PV=Rf2 --> Ka5 --> Rf4 --> Kb6 --> Rf5 --> Kc6 --> Kc8 --> Kb6 --> Kb8[9]
Depth=11 BM=Rf2 score=529 eval-count=53842 PV=Rf2 --> Ka5 --> Rf4 --> Kb6 --> Rf5 --> Kc6 --> Kc8 --> Kb6[8]
Depth=12 BM=Rd2 score=529 eval-count=16099 PV=Rd2 --> Kb6 --> Rd1 --> Kc6 --> Rd4 --> Kb6 --> Re4[7]
Depth=13 BM=Rd2 score=529 eval-count=130353 PV=Rd2 --> Kb6 --> Rd1 --> Kc6 --> Rd4 --> Kb6 --> Rc4 --> Kb5 --> Rd4 --> Kc6 --> Rd8 --> Kb6 --> Rd1[13]
Depth=14 BM=Kc7 score=530 eval-count=24709 PV=Kc7 --> Ka5 --> Kc6 --> Ka4 --> Kc5 --> Ka3 --> Rf2 --> Kb3[8]
Depth=15 BM=Kc7 score=7975 eval-count=65055 PV=Kc7 --> Ka5 --> Kc6 --> Ka4 --> Kc5 --> Ka3 --> Rf2 --> Kb3 --> Kd4 --> Kb4 --> Rb2 --> Ka3 --> Kc3 --> Ka4 --> Kc4[15]
Depth=16 BM=Rb7 score=7985 eval-count=13155 PV=Rb7 --> Ka5 --> Ka7 --> Ka4 --> Ka6 --> Ka3 --> Ka5 --> Ka2 --> Ka4 --> Ka1 --> Kb3 --> Kb1 --> Rc7 --> Ka1 --> Rc1[15]

The Depth 16 Rb7, score=7985 is exactly as expected.
But I don't understand the Depth 15, score=7975(thats like mate in 25)

I probably have more bugs, but I can stop banging my head on the wall for a while, since I've fixed that stopping ID too quick bug.

Thanks

[Harald]

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.

[hgm]

The Depth 16 Rb7, score=7985 is exactly as expected.
But I don't understand the Depth 15, score=7975(thats like mate in 25)

This is normal. Transposition tables allow you to 'look over the horizon', because you might get a hash hit at the end of the tree (say at d=15) on a position that also occurred close to the root (say at d=4) and were a mate-in-10-ply from there, (so mate-in-14-ply from the root) because the first 2 black moves were bad and hastened the mate. And if the search can force the opponent to such a mate-in-10-ply position at d=15, it (justly) concludes that it can force a mate-in-25. That doesn't mean that there can't be any faster mates (between 15 and 25 ply), through positions at d=15 that did not occur close to the root, but are close to a mate.

Especially in KRK and KPK this situation occurs very often, as the way to force a win is lengthy, and can be hastened a lot if the opponent cooperates. So many positions close to the mate (or promotion) have already occurred close to the root, in the branches where the bare King voluntarily marches towards the corner, or moves out of the way of the Pawn in stead of taking opposition.

[cms271828]

Thanks, thats pretty much what I worked out a few days ago.

I don't have a 'ply' variable, I just have MAX_DEPTH, and DEPTH.
So essentially I have ply = MAX_DEPTH - DEPTH, and thats what I use.


I have another trivialish question:
When I am at the root node, in which case DEPTH is always equal to MAX_DEPTH...
I start with a probe into hash table.
Suppose I get an entry with an EXACT score bound, then this value is returned immediatley.

So the search completes with that score being returned.

So inside the PROBE_HASH( ), should I include this line to set the Best Move..

Code: Select all

if(DEPTH==MAX_DEPTH) BESTMOVE=hashMove;

This is what I've always used before, and engine crashes if I don't include it in the PROBE_HASH( )

Is this right? Thanks again.

[Dann Corbit]

Thanks, thats pretty much what I worked out a few days ago.

I don't have a 'ply' variable, I just have MAX_DEPTH, and DEPTH.
So essentially I have ply = MAX_DEPTH - DEPTH, and thats what I use.


I have another trivialish question:
When I am at the root node, in which case DEPTH is always equal to MAX_DEPTH...
I start with a probe into hash table.
Suppose I get an entry with an EXACT score bound, then this value is returned immediatley.

So the search completes with that score being returned.

So inside the PROBE_HASH( ), should I include this line to set the Best Move..

Code: Select all

if(DEPTH==MAX_DEPTH) BESTMOVE=hashMove;

This is what I've always used before, and engine crashes if I don't include it in the PROBE_HASH( )

Is this right? Thanks again.

Normally, you will see something like this:

Code: Select all

    Entry = HashProbe(Board);
    if (Entry && Entry->depth >= depth) {
      BestMove = Entry->move;
      score = (int)Entry->score;
    }

It sounds really weird that all the entries in your hash table have the same depth.

[Harald Johnsen]

...I don't have a 'ply' variable, I just have MAX_DEPTH, and DEPTH.
So essentially I have ply = MAX_DEPTH - DEPTH, and thats what I use.


I have another trivialish question:
When I am at the root node, in which case DEPTH is always equal to MAX_DEPTH...
I start with a probe into hash table.
Suppose I get an entry with an EXACT score bound, then this value is returned immediatley.

So the search completes with that score being returned.

So inside the PROBE_HASH( ), should I include this line to set the Best Move..

You are at the root, you don't probe the hash to cut the search but only to find a move (you are in the PV anyway so you never use the hash score).

HJ.

[cms271828]

Thanks, well at the root, the depth will always be bigger than any other depth used or stored, even with Iterative Deepening.

So that means

Code: Select all

hash.depth>=depth

should always fail at the root ?????

Is that correct?

If so, then you play the hashMove, and can set the Best Move from there, same as with the other moves.

I think, I may have a bug, since I think I might have been returning values at the root,should be easy to test for though.

[hgm]

You might have a deeper or equally deep hash entry left from a previous search. You migth be in the root position for the second time, with less time/move left on the clock.

[cms271828]

Well, if you start program, with empty hash table..

Search at depth 1,
Then at depth 2,
Then at depth 3, you are in the root node, the current depth is 3, so in this case how can any hash entry have depth >= 3????

Thanks

[hgm]

Yes, but unless you clear the table between moves, you can have root hits in searches for later moves.