Debugging negamax search with transposition table

[likeawizard]

I am currently trying to implement transposition tables to my negamax search together with iterative deepening.

I have a on/off switch for testing purposes. I am making several simple assumptions:

• The results should not be affected by turning the TT on/off
• With TT enabled the total number of visited nodes should be lower than with TT off
• The %QS nodes should be lower when using TT (maybe?)

[fen]r1b1k1nr/ppp2ppp/2n5/bN6/3p2q1/3BBN2/PPP2PPP/R2Q1RK1 w kq - 2 10[/fen]

Here is some basic data with TT On:

Code: Select all

Depth: 1 (5.23) Move: [e3g5] (379.1knps, total: 229.0 (1.0 228.0), QN: 99%, evals: 99%)
Depth: 2 (0.88) Move: [f3d4 g8e7] (449.7knps, total: 3.0k (43.0 2.9k), QN: 98%, evals: 98%)
Depth: 3 (0.90) Move: [f3d4 c6e5 d1g4] (443.4knps, total: 5.3k (180.0 5.2k), QN: 96%, evals: 96%)
Depth: 4 (0.90) Move: [f3d4 c6e5 d1g4 c8g4] (613.9knps, total: 122.0k (4.9k 117.1k), QN: 95%, evals: 95%)
Depth: 5 (1.09) Move: [f3d4 g8e7 d4c6 g4d1 a1d1] (803.2knps, total: 205.7k (13.7k 192.1k), QN: 93%, evals: 93%)
Depth: 6 (1.03) Move: [f3d4 c6b4 d1d2 e8d8 d3f5 c8f5] (1.1Mnps, total: 6.0M (312.0k 5.7M), QN: 94%, evals: 94%)
Depth: 7 (1.11) Move: [b5d4 c6d4 e3d4 e8f8 h2h3 g4e6 f3e5] (1.2Mnps, total: 21.4M (1.4M 20.0M), QN: 93%, evals: 93%)

TT Off:

Code: Select all

Depth: 1 (5.23) Move: [e3g5] (870.7knps, total: 229.0 (1.0 228.0), QN: 99%, evals: 99%)
Depth: 2 (0.88) Move: [f3d4 g8e7] (816.2knps, total: 3.0k (43.0 2.9k), QN: 98%, evals: 98%)
Depth: 3 (0.90) Move: [f3d4 c6e5 d1g4] (924.2knps, total: 5.3k (180.0 5.2k), QN: 96%, evals: 96%)
Depth: 4 (0.90) Move: [f3d4 c6e5 d1g4 c8g4] (619.0knps, total: 100.8k (3.8k 97.0k), QN: 96%, evals: 96%)
Depth: 5 (1.30) Move: [f3d4 g8e7 d1g4 c8g4 d3e4] (721.0knps, total: 156.0k (8.4k 147.6k), QN: 94%, evals: 94%)
Depth: 6 (1.06) Move: [f3d4 g8e7 d1g4 c8g4 d3e4 e8d7] (1.1Mnps, total: 2.7M (128.2k 2.6M), QN: 95%, evals: 95%)
Depth: 7 (1.00) Move: [f3d4 g4d1 a1d1 c6e5 d3f5 c8f5 d4f5] (1.3Mnps, total: 22.4M (1.0M 21.4M), QN: 95%, evals: 95%)

My initial analysis of the results is as follows.
Depth=1 to 3 is all the same since it is impossible to have a transposition before 4ply, correct?
At depth 4 all seems to go down-hill. It seems that using transpositions causes the search to visit more nodes. This can not possibly be correct? I will check if I don't incorrectly update alpha/beta and actually cause less cut-offs with the use of TTs. Also after depth 4 the variations the search finds actually differ. I could understand if they would have the same evaluation it could be explained away but this should not really happen, right?

It's somewhat of a broad question without going into the details of code etc. Any suggestions how to best approach debugging the search?

[hgm]

You can have transpositions at 3 ply, when ply 1 and ply 3 are swapped.

[likeawizard]

You can have transpositions at 3 ply, when ply 1 and ply 3 are swapped.

You're absolutely right. I somehow blanked on that one. I have made some progress with my transposition table implementation. But it mostly comes with trial and error and it still seems quite opaque at times. I think I need to rewrite large chunks of my search as it has naturally grown into some ugly mess.

[op12no2]

Do you use history tables for move ordering for example. If so I would think they need to be turned off guarantee to get the same result with and without TT.