Testing Transposition Tables

[cms271828]

Yes, you are right, I overlooked that.

So if you are at a root node, and you probe hash, which immediately returns a value, you then need a best move, which I why I have..

Code: Select all

PROBEHASH()
{
    if(entry  &&   entry.depth >= DEPTH )
    {
             if( DEPTH == MAX_DEPTH ) BESTMOVE_=entry.move;

             ...
    }
}

Does that make sense, since if I miss it out, I have no best move for the root node, and nothing to play

Thanks

[Harald]

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 would not trust that construction. There may be conflicts with extensions
and deeper searches. What happens to your formula in the quiescense
search? I recommend you to use a variable ply that starts with 0 in the
root and is incremented in make_move() and decremented in
undo_move(). You will easily find a place for this little thing in your search
stack. Discussions with other chess programmers will be easier, too.

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.

I would not trust this, too. Even if you change it to if (ply == 0 ) ...
In the root my search funtion would be changed and handle a lot of
special cases. Or I would even use another search_root() function.
In the root I would use the hash entries and their moves for move
ordering only. The few real moves to positions in ply 1 where
everything is normal do not cost too much time. I guess there are
hash entries in that ply 1 for all important moves.

If you really want to use a hashed move in the root then do not only
check for depth but for an existing and valid move in the hash entry.
You should even check if it is a valid move on the board comparing it
with the moves from the move generator.

Harald

[cms271828]

Hmmm, I don't really get it to be honest, it seems to work as it is anyway.

I had an idea regarding TT, I can use an array of longs(64 bits) of size 2^22.
If I use a 50 bit key, then 22 bits will be used to index the entry, so I could just put the other 28 inside the long.

That leaves 36 bits.
I could break this up as:
Value 16 bits
Flag 2 bits
Move(From,To) 12 bits
Depth 6 bits (I don't expect to go over depth 63)


I did the maths for a 32 bit key, and the chance of a collision was terrible, something like 40% with 65,000 positions.

With a 64 bit key, the chance was extremely small, effectively negligible.

So 50 bit key is somewhere in between, I'll work out the chance of collision soon, but it could be acceptable.

So what happens if you get a collision? Engine could return a wrong score, or play an invalid move in search and cause a crash.

Thanks

[cms271828]

With a 50-bit key, theres a 50% of collision with 39,540,000 entries.

Assuming I can search 500,000 per second, thats about 1 collision per minute.

I'm not sure how to deal with this.

[hgm]

In practice nothing will happen, unless your engine can crash on an invalid move. But why would you design it such that it could crash? It is easy enough to have Make / UnMake accept any move (i.e. any combination of (From, To)) without creating an invalid position. The alternative is that you check if the hash move is legal.

50 bit is on the small side, however. In Joker I use 32 bit for the signature (the part of the key stored in the hash table), and 21 bit for the index to select a hash bucket. Each bucket contains 7 entries, of which I probe only three (two from the 6 the depth-preferred part of the table, and one replace-always entry the 6 have in common). Which entries in the bucket are probed is decided by still other bits of the key; I guess this is also worth ~1.5 bit. So effectively I am using a 54.5 bit key (with 128MB hash).

[cms271828]

Thanks, yes 50 bits is a little small...
But it will mean I can double the size of my table,
and...
previously, if you remember, I was using 2 longs per entry,
the first containing the full 64-bit key, the 2nd containing the rest.

So with just 1 long per entry, I only have half the amount of entries to look up, or store into.

I think the extra speed up will probably be worth the more frequent collisions.

I think the main problem is the value,..
Using 16 bits you can store values 0 to 65535,
Or -32768 to 32767.

Its a little awquard to give a maximum value on a position, since I haven't written EVAL method yet, but assuming white has 9 queens, 2 rooks, 2 bishops, 2 knights, 1 king, and black has 1 king..
Then position has value under 12000.

And I could use 13000 as a mate score..
So I could actually use 15 bits for the value, giving a 51 bit key.

As for collision detection, I can just test hash move is legal before playing it.

One more thing, while I'm here...
If I have 2^22 entries, should I look in positions index,index+1,index+2,
Is 3 look ups reasonable, till I find a match?

Thanks

[hgm]

Where you should look depends on how your replacement algorithm works. If you replace the least deep of two, you only have to look in two places. In practice this already combines the good aspects of replays always and depth-preferred. You could try to do better by more complicated replacement schemes, but for simplicity I would not recommend that unless your engine is finished.

If you check the legality of the move, you should reject the entire entry (i.e. consider the hash probe a miss) if the move is illegal, as you apparently have a collision then. This reduces the rate of unnoticed collisions even more, effectively mimicking a longer key. E.g., even on a full board there is only a 1 in 4 probablility that there is a piece of the ide to move on the From square, giving the same effect as 2 extra key bits. In half the cases that piece would be a Pawn, and would be very likely not be allowed to move to the specified To square.

As to the maximum score: in practice positions with more than 3 Queens will never occur, as with 3 Queens it finds the mate in just 2 or 3 moves, never needing more promotions.

[cms271828]

As to the maximum score: in practice positions with more than 3 Queens will never occur, as with 3 Queens it finds the mate in just 2 or 3 moves, never needing more promotions.

Thats true, but if a position is set up with white having 9 queens, just for fun, I still want this to work the same as any other position, with MATE score, being a bit higher than the maximum possible.

I was thinking...
How would one test for a performance improvement, regarding depth searched.
The nodes per second value is not a good indicator of how deep engine can search, but I guess its how small you can make your branching factor?

Currently, when I start engine from starting position, after 1 minute of search, it gets upto ply 10, but does not complete the ply 10 search.

So, I could fiddle with hash table or move ordering, and still get a upto 10 ply, but I won't know if its better than before.

Is there a way to do this? Do I somehow need to look at the branching factor?

Thanks

[hgm]

To see if hash schemes or move ordering give an improvement, I just compare number of nodes and time searched to finish all the iterations.

[cms271828]

I see, makes sense,

I just timed my engine, to see how long it took to complete ply 10.

A) With 2^20 entries in table:
Depth=10 BEST_MOVE=e3 score=-94 nnode=290,833,381 neval=236,804,413
total_nnode=340,373,635 total_neval=278,244,336
TIME TAKEN = 179.954 seconds

B) With 2^21 entries in table:
Depth=10 BEST_MOVE=e3 score=-94 nnode=441,017,974 neval=359,452,142
total_nnode=492,668,899 total_neval=402,521,651
TIME TAKEN = 263.906 seconds

This doesn't look good, it takes much longer with a bigger table.
But if you divide total_nnode (total number of nodes searched for all plies) by the time, you get 1.87M nps for both A) and B).

Surely this is wrong?
But I can't spot any obvious error.

Is there any simple thing I can do to find error.
Thanks