Testing Transposition Tables

[cms271828]

Very interesting,

I don't quite get how it works, my original thought was that with two long arrays, I have to make 2 look ups, one into each array.

And with one long array(twice the size), I would still need two look ups into that array.

I don't know how the cpu does it exactly, but when using one long array, and then looking up first entry 2*index, is there like a marker or something that points to that entry, so that when you look at the next one, it doesn't have to do much to find it since its next to it?

Is that right?

I was currently using 2^20 entries, but that was with those TTEntry objects I made, so maybe I can push it more, and have 2^21 or 2^22 entries

Thanks

[hgm]

CPUs have a hardware feature called a cache. When it has to fetch data from memory, it first looks if it is in the cache. If it is, fetching the data takes 3 clock cycles, and during these cycles, other instructions can be executed.

If the data is not in the cache, a tranfer of 64 contiguous bytes from DRAM to the CPU is performed. This takes about 300-500 clock cycles, during most of which the CPU is stalled. But 64 bytes is 8 longs. So if you fetch one long, the long stored next to it in memory is very likely to have been brought into cache together with the long you requested first. Then access to it would be nearly free, while access to a long more than 64 bytes removed from it would take another 500 clocks.

[cms271828]

Thanks, that makes sense.
I considered using a 32 bit hash key, but with 65000 positions, there was a 40% chance of a collision, but with 64 bit key, it was practically negligible, so I'll stick with 64 bit for now.

I ran program with a position, and I got some strange results, but maybe it is correct.
I'm using 8000 for MATE score, so MATE in 3 is 7997 which is better than mate in 10 which is 7990.

Here is the start position from my book.
White to play and win in 6 moves (11 plies)
<3Q1K1k/5p2/6p1/8/8/8/5q2/8>

I have TT included, and hash move always played first.

Depth=1 BEST=Qd5 score=-208 eval_count=20
Depth=2 BEST=Qd5 score=-213 eval_count=45
Depth=3 BEST=Qg5 score=-116 eval_count=368
Depth=4 BEST=Qg5 score=-200 eval_count=850
Depth=5 BEST=Qg5 score=-110 eval_count=5498
Depth=6 BEST=Qd5 score=-125 eval_count=10688
Depth=7 BEST=Qg5 score=-95 eval_count=38853
Depth=8 BEST=Qa8 score=-96 eval_count=36192
Depth=9 BEST=Qa8 score=8 eval_count=68416
Depth=10 BEST=Qa8 score=834 eval_count=44265
Depth=11 BEST=Qa8 score=7989 eval_count=276028

Computer plays Qa8, then I play Qg1

Depth=1 BEST=Kxf7 score=2 eval_count=6
Depth=2 BEST=Kxf7 score=2 eval_count=6
Depth=3 BEST=Kxf7 score=2 eval_count=56
Depth=4 BEST=Kxf7 score=2 eval_count=45
Depth=5 BEST=Kxf7 score=2 eval_count=466
Depth=6 BEST=Kxf7 score=2 eval_count=408
Depth=7 BEST=Qa3 score=7993 eval_count=2228

Computer plays Qa3, then I play Qg5

Depth=1 BEST=Kxf7 score=-125 eval_count=14
Depth=2 BEST=Kxf7 score=-125 eval_count=14
Depth=3 BEST=Qh3+ score=-116 eval_count=93
Depth=4 BEST=Qh3+ score=-116 eval_count=58
Depth=5 BEST=Qh3+ score=-106 eval_count=506
Depth=6 BEST=Qh3+ score=-93 eval_count=389
Depth=7 BEST=Qh3+ score=7993 eval_count=2198

Computer plays Qh3+, then I play Qh5

Depth=1 BEST=Qc3+ score=7995 eval_count=0

Computer plays Qc3+, then I play f6

Depth=1 BEST=Qxf6 score=7997 eval_count=0

Computer plays Qxf6+, then I play Kh7

Depth=1 BEST=Qg7++ score=7999 eval_count=0

Computer plays Qg7++ (GAME OVER)



Without TTs, I would expect to see the scores.. 7989..7991..7993..7995..7997..7999, but its much different above, does this look normal?

Thanks for your help.

[cms271828]

I'm not sure if I need to store the hash entry whenever there is no moves available so that the side to move is in checkmate or stalemate.

If I leave this out, it is able to do problem 1, but not problem 2.
And if I put it in, with flag as hashfEXACT, it can do problem 2, but not problem 1. (Both problems are mates in 11 ply)

I'm getting a little frustrated now, since before I put the TT in, I could debug the program fairly straightforwardly by running a complete test at each node to see where the error is.

But I don't know how to properly test for bugs with a TT, I have a test at each node that builds the full zobrist key, and tests if it matches the incrementally updated key, and this is always passes, so the problem is somewhere else.

Are there any techniques I can use to help track down my bug(s).

Thanks

[Harald Johnsen]

I'm not sure if I need to store the hash entry whenever there is no moves available so that the side to move is in checkmate or stalemate.

It's like any other position, you can store it or not. This has no impact on the correctness of the search.

If I leave this out, it is able to do problem 1, but not problem 2.
And if I put it in, with flag as hashfEXACT, it can do problem 2, but not problem 1. (Both problems are mates in 11 ply)

What do you mean ? The engine does not find the mate or it does not find the fastest mate ? (you surely have random mate depth because you don't correct the mate score when you retrieve it from the TT) And btw the mate score is not an 'exact' score, it can be an upper or lower bound like any other score.

I'm getting a little frustrated now, since before I put the TT in, I could debug the program fairly straightforwardly by running a complete test at each node to see where the error is.

...

I can only suggest you to not do a null window search, not do any extension or reduction, no null move etc.

HJ.

[hgm]

This is not normal: at 7-ply ithe search reports a mate-in-7-ply, why in fact the chosen move (Qa3) only leads to mate-in-9-ply.

Print the PV (preferably with scores) to find out how it thinks to do this mate-in-7-ply, so that you can see which defense for black it overlooks. Are you sure you get the results 'you expect without TT' when you actually search without TT?

[cms271828]

Hi,

I've got a bit further, if anyone would care to take a look at this checkmate problem, I would be very grateful.

[d]8/8/8/8/7Q/3p4/3K3p/5b1k w 1-0

There is a simple solution...
1. Qg3, Bh3
2. Qf2, Bg2
3. Qe1, Bf1
4. Qxf1++

I'm using iterative deepening starting at Depth 1, and going up.
So,.. I run the engine, it plays the first 3 moves for white, while I play the corresponding moves for black.. taking me to this position..
Where it is whites turn to play
[d]8/8/8/8/8/3p4/3K3p/4Qb1k w 1-0

So, I'm using iterative deepening, my engine starts at depth 1.
It probes hash table, and gets the move Qxf1++ with value 7999,type hashfBETA, and alpha=-infinty, beta=infinty.

Whilst probing, I have the code (see http://www.seanet.com/~brucemo/topics/hashing.htm)

Code: Select all

if(flag==hashfBETA    &&   val>=beta)  return beta

So, the 7999 value is never returned, and it just does a 1 ply search, and actually plays Qg3(since this is a mate in 6 or so ply).


So I don't know whats going on, perhaps I am storing it wrong.

However If I only record do record hash when depth>=1 (so not actually on leaf nodes (I don't have QS yet)), then engine runs much, since I'm not wasting time storing not very important positions, as well as the fact that I am leaving more space in the TT for the more important positions, and also.....
The puzzles I have been trying now work correctly.

Considering the position I mentioned a couple of posts ago which HG pointed out was totally wrong, I now have the new output...

[d]3Q1K1k/5p2/6p1/8/8/8/5q2/8 w 1-0


Depth=1 BM=Qd5 score=-208 count=20 PV=Qd5[1]
Depth=2 BM=Qd5 score=-213 count=45 PV=Qd5 --> Qd4[2]
Depth=3 BM=Qg5 score=-116 count=649 PV=Qg5 --> Qd4 --> Qxg6[3]
Depth=4 BM=Qg5 score=-200 count=1457 PV=Qg5 --> Kh7 --> Qe5 --> Qd4[4]
Depth=5 BM=Qg5 score=-110 count=13987 PV=Qg5 --> Kh7 --> Qe7 --> Kh8 --> Qxf7[5]
Depth=6 BM=Qd5 score=-125 count=20519 PV=Qd5 --> Qf5 --> Qxf7 --> Qc8 --> Ke7 --> Qc4[6]
Depth=7 BM=Qg5 score=-95 count=119772 PV=Qg5 --> Kh7 --> Qe5 --> f6 --> Qe7 --> Kh6 --> Qxf6[7]
Depth=8 BM=Qa8 score=-96 count=60350 PV=Qa8 --> g5 --> Qh1 --> Qh4 --> Qa1 --> f6 --> Qxf6[7]
Depth=9 BM=Qa8 score=8 count=174713 PV=Qa8 --> g5 --> Qh1 --> Qh4 --> Qa1 --> f6 --> Qxf6 --> Kh7 --> Qxg5[9]
Depth=10 BM=Qa8 score=834 count=92905 PV=Qa8 --> g5 --> Qh1 --> Qh4 --> Qa1 --> Qd4 --> Qxd4 --> f6 --> Qxf6 --> Kh7[10]
Depth=11 BM=Qa8 score=7989 count=664948 PV=Qa8 --> g5 --> Qh1 --> Qh4 --> Qa1 --> Qd4 --> Qxd4 --> f6 --> Qe4 --> f5 --> Qh1[11]

Computer plays Qa8, I reply Qg1(solution from book)

Depth=1 BM=Qd8 score=834 count=1 PV=Qd8[1]
Depth=2 BM=Qd8 score=834 count=1 PV=Qd8[1]
Depth=3 BM=Qd8 score=834 count=5 PV=Qd8[1]
Depth=4 BM=Qd8 score=834 count=4 PV=Qd8[1]
Depth=5 BM=Qd8 score=834 count=56 PV=Qd8[1]
Depth=6 BM=Qd8 score=834 count=390 PV=Qd8[1]
Depth=7 BM=Qd8 score=834 count=7187 PV=Qd8[1]
Depth=8 BM=Qd8 score=834 count=5372 PV=Qd8[1]
Depth=9 BM=Qa3 score=7991 count=43045 PV=Qa3 --> Qg5 --> Qh3 --> Qh5 --> Qc3 --> Qe5 --> Qxe5 --> f6 --> Qh2[9]

Computer plays Qa3, I reply Qg5

Depth=1 BM=Qh3 score=7993 count=0 PV=[0]

Computer plays Qh3, I reply Qh5

Depth=1 BM=Qc3 score=7995 count=0 PV=[0]

Computer plays Qc3+, I reply f6

Depth=1 BM=Qxf6 score=7997 count=0 PV=[0]

Computer plays Qxf6+, I reply Kh7

Depth=1 BM=Qg7 score=7999 count=0 PV=[0]

Computer plays Qg7# (CHECKMATE)

This is an improvement at least, since each time it is whites turn, the correct score comes out.

I kind of have a bad feeling the bug is still in there, and I have just concealed it by not recording at leaf nodes.

I'll try out some more checkmate puzzles, and see how it goes.
Thanks for any help

[hgm]

Whilst probing, I have the code (see http://www.seanet.com/~brucemo/topics/hashing.htm)

Code: Select all

if(flag==hashfBETA    &&   val>=beta)  return beta

So, the 7999 value is never returned, and it just does a 1 ply search, and actually plays Qg3(since this is a mate in 6 or so ply).

I am not sure what you are saying here.

+7999 is your score for a checkmate-in-1 position?

so If beta = +infinity, how could val be greater or equal to beta. It must be the +7999 which is returned. If beta == val, it does not matter which of the two you return.

Or is the problem that you are probing the hash table in the root? That it does return a proper score without search, but not the move? The root is the only node where it is essential what the move was. Some very good programs do not do hash cutoffs on any PV node. This helps for not overlooking rep-draws.

[cms271828]

Thanks, I got mixed up, I think I understand the problem, but don't know to fix it.
I'll restate the problem for clarity.

The mate in 7 ply problem..
[d]8/8/8/8/7Q/3p4/3K3p/5b1k w 1-0
There is a simple solution...
1. Qg3, Bh3
2. Qf2, Bg2
3. Qe1, Bf1
4. Qxf1++

My engine plays the first 3 moves(for white) correctly, and I reply with blacks moves.. this leads to this position, with white to play

[d]8/8/8/8/8/3p4/3K3p/4Qb1k w 1-0

Starting my engine at depth 1, and probing hash table gives..
HashMove= Qxf1++, value= 7999.

Then, inside node 1 still, the hash move is played, along with the other possible moves.

Playing the hash move(Qxf1) returns a score of 659, since at D=0(black node) no moves are generated, so it doesn't know the position is checkmate, and so just returns evaluation.

Continuing through the moves..

Qg3 is played... so at D=0(black node), the hash is probed, and the value -7993 is returned back upto node 1 (as 7993). This makes sense because it was the key move from the very start.

So now... obviously 7993 is better than 659, so...
At Depth 1, the best move is Qg3, instead of the better Qxf1++.

And since this is a mate in N score, the iterative deepening stops,
and Qg3 is the move that is played.


So, this seems to make sense, if it searched to Depth 2, then it would have picked up the fact Qxf1++ was actually a checkmate, and this would score beter than the Qg3.

So, I don't know what I'm doing wrong
Any thoughts? Thanks

[hgm]

The error is that you stop deepening on any mate score. You should only stop deepening if you have searched deep enough that you are sure there cannot be any faster mate scores. Otherwise there is no guarantee that you will find the fastest mate score. Because, as you now discovered, you can sometimes see mates far beyond the search horizon by 'over-deep' hash hits.

So if you get 7993 = mate-in-7-ply as the best score for the 1-ply search, you should cotinue deepening to a two-ply search. Only when you get 7993 from an 7-ply search you can stop, because you cannot possibly find anything faster. (It doesn't matter than that there might be mate-in-7s that you overlooked because you don't recognize mate at d=0; they are at best equally fast.)