Debugging a transposition table

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
xr_a_y
Posts: 198
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Debugging a transposition table

Post by xr_a_y » Fri Jun 01, 2018 3:02 pm

hgm wrote:
Wed May 30, 2018 8:23 pm
And reaching the position again would mean a repetition, and would assign a draw score rather than the TT score.
Can you elaborate a little on this subject please ? In your engines, you give null score at the first repetition during search (don't wait for the third) ? Can't a repetition threat be used to "force" opponent to try another move in case contempt score is a little high ?

User avatar
hgm
Posts: 22572
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Debugging a transposition table

Post by hgm » Fri Jun 01, 2018 3:37 pm

xr_a_y wrote:
Fri Jun 01, 2018 3:02 pm
In your engines, you give null score at the first repetition during search (don't wait for the third) ?
In all my newer engines I indeed do that. Only Joker searched on to the third occurence, and it gave nothing but trouble. It was mainly used to cause horizon effect by artificially reducing the search depth. If a superficially good forced action turned out to end in disaster at higher search depth, it just included one or more forced single-repetition detours in it, to make sure the poisoned final position was searched at low depth.

User avatar
Kotlov
Posts: 179
Joined: Fri Jul 10, 2015 7:23 pm
Location: Russia

Re: Debugging a transposition table

Post by Kotlov » Fri Jun 01, 2018 4:08 pm

xr_a_y wrote:
Fri Jun 01, 2018 3:02 pm
Can't a repetition threat be used to "force" opponent to try another move in case contempt score is a little high ?
My engine do this. Works good.
3-repetition is a human rule.
For computers - 2 is enough.
Eugene Kotlov
Hedgehog 1.9 64-bit

User avatar
xr_a_y
Posts: 198
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Debugging a transposition table

Post by xr_a_y » Sat Jun 02, 2018 6:22 am

hgm wrote:
Fri Jun 01, 2018 3:37 pm
xr_a_y wrote:
Fri Jun 01, 2018 3:02 pm
In your engines, you give null score at the first repetition during search (don't wait for the third) ?
In all my newer engines I indeed do that. Only Joker searched on to the third occurence, and it gave nothing but trouble. It was mainly used to cause horizon effect by artificially reducing the search depth. If a superficially good forced action turned out to end in disaster at higher search depth, it just included one or more forced single-repetition detours in it, to make sure the poisoned final position was searched at low depth.
Thanks for that advice ! It seems to gain quite some search time. On Fine#70, this allow Weini to get the good move in 32ms (1thread, 1Go TT, only PSQT).

konsolas
Posts: 69
Joined: Sun Jun 12, 2016 3:44 pm
Contact:

Re: Debugging a transposition table

Post by konsolas » Mon Jun 04, 2018 3:14 pm

Ronald wrote:
Fri Jun 01, 2018 2:09 pm
Great again.!
I think your mating problem has to do with correcting the matescore when you put it into the hashtable (and when you get it out). In your source you don't do that will probably be the problem. When you get a matescore for your position you correct the matevalue with the ply you are in. If you store that value in the hash and retrieve it later at another plydepth you will not have the correct matevalue. The best thing to do is correct the matevalue with the current plydepth before storing it in the hash, and correct the value again after retrieving it from the hash.

When storing the hash entry I first do the following correction to the score sc

Code: Select all

void putHashTableEntry(U64 hk, moveStruct mv, eval sc, int8_t d, U8 n, U8 ply) {
    if (sc >= MINCHECKMATE) sc += ply;
    else if (sc <= -MINCHECKMATE) sc -= ply;
    ..
    
After retrieving the hash entry from hash I first make the following correction before using the entry:

Code: Select all

     if (hashEntry.score >= MINCHECKMATE) hashEntry.score -= ply;
        else if (hashEntry.score <= -MINCHECKMATE) hashEntry.score += ply;
   
MINCHECKMATE is the lowest possible value which is a checkmate:
MINCHECKMATE = CHECKMATEVALUE - MAXDEPTH
Thank you, that makes sense, and my engine seems to be handling mate situations correctly now.

User avatar
xr_a_y
Posts: 198
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Debugging a transposition table

Post by xr_a_y » Mon Jun 11, 2018 6:22 pm

xr_a_y wrote:
Sat Jun 02, 2018 6:22 am
hgm wrote:
Fri Jun 01, 2018 3:37 pm
xr_a_y wrote:
Fri Jun 01, 2018 3:02 pm
In your engines, you give null score at the first repetition during search (don't wait for the third) ?
In all my newer engines I indeed do that. Only Joker searched on to the third occurence, and it gave nothing but trouble. It was mainly used to cause horizon effect by artificially reducing the search depth. If a superficially good forced action turned out to end in disaster at higher search depth, it just included one or more forced single-repetition detours in it, to make sure the poisoned final position was searched at low depth.
Thanks for that advice ! It seems to gain quite some search time. On Fine#70, this allow Weini to get the good move in 32ms (1thread, 1Go TT, only PSQT).
But using this one repetition thing, the engine might think it can get a draw from a loosing position just repeting the position once, and this way it can totally lose a piece ...

Like in this game https://lichess.org/fh7nZzjI at move 52.

If we have a look at evaluation of both engine (the "ref" one is using 3 repetitions, while the "9" one is using only one repetition)

42. Rxf5+ {-2.68/10 0.48s} Kxd4 {+4.71/10 0.47s} 43. Rxe3 {-2.14/10 0.24s}
Rxe3 {+5.01/9 0.31s} 44. Rf4+ {-1.96/10 0.41s} Re4 {+5.01/9 0.39s}
45. Rf2 {-2.24/10 0.41s} Re3 {+5.01/10 0.40s} 46. Rf4+ {-1.11/9 0.22s}
Re4 {+5.01/10 0.40s} 47. Rf2 {0.00/11 0.13s} Kd5 {+5.01/9 0.40s}
48. Rf5+ {-2.34/11 3.0s} Re5 {+5.01/9 0.30s} 49. Rf4 {-2.34/11 0.37s}
Re2+ {+5.18/10 0.25s} 50. Kb1 {-2.26/9 0.20s} Re4 {+5.21/10 0.27s}
51. Rf5+ {-2.23/10 0.33s} Kd4 {+5.64/9 0.35s} 52. Rf4 {0.00/10 0.20s}
Rxf4 {+15.02/10 0.23s} 53. Kc2 {-78.42/11 0.59s} c3 {+18.09/9 0.18s}

we cleary see the the white engine is thinking it can get a draw...

How do you avoid that ??

Sven
Posts: 3651
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Debugging a transposition table

Post by Sven » Mon Jun 11, 2018 9:40 pm

xr_a_y wrote:
Mon Jun 11, 2018 6:22 pm
xr_a_y wrote:
Sat Jun 02, 2018 6:22 am
hgm wrote:
Fri Jun 01, 2018 3:37 pm

In all my newer engines I indeed do that. Only Joker searched on to the third occurence, and it gave nothing but trouble. It was mainly used to cause horizon effect by artificially reducing the search depth. If a superficially good forced action turned out to end in disaster at higher search depth, it just included one or more forced single-repetition detours in it, to make sure the poisoned final position was searched at low depth.
Thanks for that advice ! It seems to gain quite some search time. On Fine#70, this allow Weini to get the good move in 32ms (1thread, 1Go TT, only PSQT).
But using this one repetition thing, the engine might think it can get a draw from a loosing position just repeting the position once, and this way it can totally lose a piece ...

Like in this game https://lichess.org/fh7nZzjI at move 52.

If we have a look at evaluation of both engine (the "ref" one is using 3 repetitions, while the "9" one is using only one repetition)

42. Rxf5+ {-2.68/10 0.48s} Kxd4 {+4.71/10 0.47s} 43. Rxe3 {-2.14/10 0.24s}
Rxe3 {+5.01/9 0.31s} 44. Rf4+ {-1.96/10 0.41s} Re4 {+5.01/9 0.39s}
45. Rf2 {-2.24/10 0.41s} Re3 {+5.01/10 0.40s} 46. Rf4+ {-1.11/9 0.22s}
Re4 {+5.01/10 0.40s} 47. Rf2 {0.00/11 0.13s} Kd5 {+5.01/9 0.40s}
48. Rf5+ {-2.34/11 3.0s} Re5 {+5.01/9 0.30s} 49. Rf4 {-2.34/11 0.37s}
Re2+ {+5.18/10 0.25s} 50. Kb1 {-2.26/9 0.20s} Re4 {+5.21/10 0.27s}
51. Rf5+ {-2.23/10 0.33s} Kd4 {+5.64/9 0.35s} 52. Rf4 {0.00/10 0.20s}
Rxf4 {+15.02/10 0.23s} 53. Kc2 {-78.42/11 0.59s} c3 {+18.09/9 0.18s}

we cleary see the the white engine is thinking it can get a draw...

How do you avoid that ??
Please check your repetition detection code. There is no repetition involved at 52.Rf4, at least the white king has already moved from c2 to b1 in the meantime. When implementing it correctly you should not get the kind of problem you mentioned. One way to completely avoid it would be to only return a draw score if the first occurrence of the repeated position is at ply 1 or below, so neither at root nor above. But according to my experience this is not strictly necessary.
Sven Schüle

User avatar
xr_a_y
Posts: 198
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Debugging a transposition table

Post by xr_a_y » Tue Jun 12, 2018 4:49 am

You're right for move 52 ! thanks. But my question still holds at move 47 (a repetition of position after 44)?

User avatar
JVMerlino
Posts: 956
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Debugging a transposition table

Post by JVMerlino » Tue Jun 12, 2018 4:09 pm

An engine would not be incorrect in giving a draw score to 47.Rf2, because it is the best available move and it is a repetition.

But 46.Rf4+ should also have been given a draw score, but it was scored as -1.11? If you have designed your engine to give draw scores to repetitions, then there is a bug here.

But, indeed, 52.Rf4 being scored as a draw is clearly a bug, as you have seen.

User avatar
hgm
Posts: 22572
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Debugging a transposition table

Post by hgm » Tue Jun 12, 2018 5:31 pm

To avoid engines think repeating a position from the game immediately is a draw, you can remove / invalidate all positions that occurred only once in the game from the key stack, and only leave those that already occurred twice, before you start searching.

In engine-engine games this doesn't bring any solace, however. If a position is obviously lost. the opponent will punish you the first time it occurs, and there will be no repeat of such a position.

Post Reply