hashtables

[daniel anulliero]

hi all!

well I've restarted some work on Yoda , I try to implement the hashtables incrementaly .So It found now the good move in these kind of positions :
5k2/8/4pPp1/3pP1P1/2pP4/2P3K1/8/8 w - - 2 22
8/k7/3p1p2/p2P1P2/P2P4/8/8/TK7 w - - 2 22
etc...
It play more faster in endgames and a lot better but .... It play very weaker in opennings /middlegames . I think I have a big problem of collisions , but I can't understand why it found the good moves in endgames?

So my question is :
What are the parameters to include in hashcoding ? (castle white /black , color of move ... etc)
And :
I want to update the code incrementaly : what is the order of hashing? Because for now , I don't have the same hashcodes incrementaly and not incrementaly ....
I can post my make/unmake move code If you want

thanks for yours answer
and (sorry for my bad english!)
Bests
dany

[crystalclear]

I store the old hashcode in my "undo" information. That makes undoing a move quick and makes sure the hashcode is correctly restored no matter what complications arise during the making of a move: en passant posibilities, castling rights, piece captures etc.

I had a scheme for hashing that I really liked, but ditched it in favour of the hashcodes used by polyglot in order to use standard opening books. In hindsight I don't think I needed to do that, but that's what I have at the moment. The hashcodes are evaluated using exclusive-or and that basically means that the order things are done doesn't matter at all. You just need to make sure that you evaulate things correctly.

I modified my perft software to check hashcodes and I know someone else who did the same so I guess it is standard practice.
In the perft software I check that the incrementally evaluated hashcode is the same as the hashcode generated from scratch.
If it throws up an error, you need to look at the position and move that caused the problem.

For example, if a pawn takes a piece and queens, then you might
1. reset some en-passant rights
2. change some castling rights
3. remove a captured black rook on a8 from the board completely
4. remove a white pawn from b7
5. place the white pawn on a8
6. remove the white pawn from a8
7. create a white queen on a8.
8. Change the side to move.

Some of the steps are unnecessary in the sense that 5 and 6 cancel each other out.
But it is worth noting that it isn't as simple as having the board correct.
That's because for example putting a queen on a8 makes the data for the square a8 correct, even if you don't consiously remove the rook
and whether or not the pawn is put on a8 and removed from a8, or simply removed from b7.

If you get an incorrect hashcode, you can compare it with the correct hashcode (eg by exclusive or-ing in the case of Polyglot's Zobrist hashcodes).
In the example above, if the difference corresponded to a value for en passant, then one could look to see if one had forgotten to cancel enpassant rights
the move after a pawn pushes forwards two squares.

Initially, you can verify that your static evaluation of the hash key is correct.
Here are a few values (with no guarantees) calculated by my program.

Code: Select all

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - Zob 463B96181691FC9C;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - - Zob 5DCCC1E5133B8729;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 b - a3 Zob D5D69496B7DE6C04;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - b6 Zob BFD6AAD0CC37BDFE;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 b - c3 Zob A52074970E9C6B42;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - d6 Zob 41551F362F831788;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 b - e3 Zob 6A2BA291B6C140A9;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - f6 Zob 8D28839F462F7C5B;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 b - g3 Zob D2DCC68323AFA6A3;
4k3/8/8/PpPpPpPp/PpPpPpPp/8/8/4K3 w - h6 Zob 3A6F8C49506DD222;
r3k2r/8/8/8/8/8/8/R3K2R w - - Zob 86981467BEABCFBA;
r3k2r/8/8/8/8/8/8/R3K2R w K - Zob B74F09A9DA190CAA;
r3k2r/8/8/8/8/8/8/R3K2R w Q - Zob 77FDA1E061224E2A;
r3k2r/8/8/8/8/8/8/R3K2R w k - Zob 23E6775E63873C1A;
r3k2r/8/8/8/8/8/8/R3K2R w q - Zob 986EF2BC0F3DD173;
r3k2r/8/8/8/8/8/8/R3K2R w KQkq - Zob FDA239CC692A6053;
7k/8/8/8/8/8/8/K7 w - - Zob 523760C49712209D;
7K/8/8/8/8/8/8/k7 w - - Zob 9D59E1F9C78EE65;
K7/8/8/8/8/8/8/7k w - - Zob DFDAA843ACD9BD6D;
k7/8/8/8/8/8/8/7K w - - Zob 16D152196D11E3F1;
4k3/8/8/8/8/8/P7/4K3 w - - Zob 4A29F78EE09643B0;
4k3/8/8/8/8/8/N7/4K3 w - - Zob 8C32E094493AE3F9;
4k3/8/8/8/8/8/B7/4K3 w - - Zob 4FB436D2EEEEF356;
4k3/8/8/8/8/8/R7/4K3 w - - Zob 1055B3040A2207F3;
4k3/8/8/8/8/8/p7/4K3 w - - Zob 53FB3B27CF9E48D6;
4k3/8/8/8/8/8/n7/4K3 w - - Zob 20685F77C324391F;
4k3/8/8/8/8/8/b7/4K3 w - - Zob 69E7079F3364B22F;
4k3/8/8/8/8/8/r7/4K3 w - - Zob 854737CFD3933679;
4k3/8/8/8/8/8/q7/4K3 w - - Zob 7F65F02AB12D0D79;


[daniel anulliero]

hello!

Many thanks for your answer!
So I don't care with the order to hashing...
for exemple for castling :
hash ^= king e1 , hash^= King g1 , hash ^= Rook h1 , hash ^= rook f1 , hash ^= castleW , hash ^= white (or black here?)
give the same code of :
hash ^= king g1 , hash^= king e1 , hash ^= rook f1, hash ^= Rook h1,hash ^= castleW ,hash ^= white (or black here?)
or :
hash ^= castleW ,hash ^= king e1 , hash^= King g1 , hash ^= Rook h1 , hash ^= rook f1, white (or black here?)
? (of course the hash opérations in UnMake_move must be inverted right?)

I'll take a look at search , and probe TT and save TT too ,such things are always quite "complex" (and buggy? ) for me ...

thanks for your lights !

PS : is your engine avalaible crystalclear ?


dany

[crystalclear]

When I make a move I store the hash key of the current position in the undo information and when I undo a move I simply restore the old hash value to ensure the hash value is correct instead of undoing each of the hash key changes one by one.

In a debug version of your software you can verify that your incrementally updated hash key after making a move is the same as the hash key evaluation for the position calculated from scratch. If it isn't, print the position and the move and look to see what your software is calculating incorrectly. That will slow the software enormously, but it's just temporary until the incremental hash key updating is debugged.

Before that, verify that the "from-scratch" evaluation function works well by testing some known position and hash code combinations.

I assume that the values I gave earlier are correct, but no one has confirmed them.
I base my assumption on the fact that Stockfish can read my opening books and my program can read Stockfish's.

===

I've been writing a little graphical user (M$ windows) interface tool that allows someone to enter the FEN of a position. The tool calculates the (polyglot) hash key of the position.
You also enter an opening book file name. The tool finds the closest entry in the book to the chosen position and displays that entry in the file.
The hash code displays green if it's a direct hit in the book.

Input: (King's gambit position)
book_myEngine.bin
rnbqkbnr/pppp1ppp/8/4p3/4PP2/8/PPPP2PP/RNBQKBNR b KQkq f3 0 2

Output:
Entry Number 374622 of 391112
hash key F552EE1777658429
move e5f4
weight 28
learn 0

A little slider shows you the percentage of the way through the file and allows rapid repositioning in the file. Alternatively, an "entry number" spinbox allows you to go to a specific location in the file, or step backwards and forwards an entry, eg to see other moves for a position or neighbouring entries in the file.

The GUI basically makes some calls to my text interface chess engine.
If you (daniel anulliero) want a copy, let me know an email address and I could try to package up the two together in a way that you could run the GUI.
I know it's a noddy program, but I wanted to start looking at GUI writing rather than always calling printf!

[daniel anulliero]

Hello
Thanks again for your help
Well I do the hash update incrémentaly and I have the same hashcode When make
and unmake moves , But not from scratch Okay I must fix
that before
So I'll glad to have a copy of your GUI I have a seven 64bits PC
My email :
dany_1962@live.fr
Best regards
Dany

Ps: do you have an engine avalaible ?

[crystalclear]

Is anyone here using symmetrical keys for hashing, or would like to chat about doing so?




At the moment I have some sort of symmetrical keys. The hashcode for one of these positions is easily determined from the hashcode for the other by applying a left right reflection. What I am wondering is whether the hashcodes should be the same. I currently have the same hash codes for situations like this.




That is: my three hash key transformations for vertical reflection, piece colour swapping, and changing the side to move, combine to just gives the identity "No Op" transformation. (The Glass Opening Book format has this property too, so that if white loses a tempo by a bishop being chased back a little by a pawn, or a pawn moving to third and then fourth rank in two moves, the opening moves might still be in the book as things that black might have played.)
But my left right reflection transformation has order 2.

I am wondering if there is some symmetrical key scheme that will give me a speed up with positions like this due to the LR symmetry.



I have seen pawn endings where the pawn layout wasn't exactly symmetric, but could have become some with the right sequence of moves - moves that a program would probably have considered. I want to get my keys right, as I think it should be possible to use them to index a custom endgame tablebase. For each non-pawn piece my 128 piece square keys for 64 squares and two colours are all generated from 10 keys for the a1,d1,d4 triangle so it sort of seems logical that there will be a way to index a custome endgame tablebase using some bits from my hashkey, if I set things up right.

[crystalclear]

I've thought some more about it and I understand it better now.

I've mentioned before that the Glass Opening Book format uses symmetrical keys. For example, the hash codes for the position after 1.e4 c5 with white to play, and for the position after 1. c3 e5, 2.c4 with black to play, are identical. If white can play Nf3 in the first case, then it is equally sensible that black can play Nf6 in the second. The way this is handled in the Glass Opening Books, is that the book contains an entry which is equivalent to N-KB3. i.e the Glass Opening Books have a sort of symmetrical representation of chess moves.
Without the symmetrical move idea, using the same hash key for the two related positions will create problems. For example if the hash tables say white should play Nf3, then in the sort of mirror position, black might try to play an illegal Nf3.

Now if I think about my question of left-right symmetry, it is clear that the hash codes for two mirror image positions need to be different even if they are related. With the hash codes the same, things could only work sensibly with some sort of left right mirror move codes, eg a code saying something like put your knight in front of your king. That would be equally meaningful whichever side of the board your king was on. But I don't think anyone is using anything like that except perhaps for endgame tablebases.

So I'm now happy to keep the hashing keys for pieces on the left and on the right of the board different but related by a simple transformation of order 2. Glass uses byte reversal as one of its transformations, but there are many to choose from: bit order reversal, ones complement, word swapping, etc.

Since my move information for black and white lacks the symmetry of the chess notation N-KB3 and resembles the algebraic notation Nf3, I can't have the same hash codes for colour reversed positions, and I've knocked the hashcodes out of alignment by using a simple non-zero "side to move" key code. My program is playing chess again, using the symmetrical keys at the moment, with the side-to-move change added.

It means I've lost some of the symmetry, but I can recover it if I ever need to. I am thinking that the keys might be useful for indexing a custom endgame tablebase or bitbase in the future.

=

My chess program used to crash occasionally without me knowing why. With the symmetrical keys I started getting similar crashes more often. I believe they were from hash key clashes which I am guessing now happen more often. Every upside in chess program seems to have a corresponding downside! The good news for me is that I've hopefully now found what happens when the hash codes clash and fixed a bug!

[crystalclear]

I am just chatting to myself on here it seems, but never mind.

I am wondering about hashing schemes again and I am thinking of trying to hand craft some hash keys. Before I do, I am thinking about how to minimise the chances of collisions or of knowing better where collisions might occur. To do that, I am thinking of constructing some small simple hash keys and then combining them in some way to get a longer hash code for a whole board. So I am looking at simple cases first and planning to build up from there.

If I take a pair of white bishops, they are probably of different castes, a light squared bishop and a dark squared bishop. Using that, I could hash the position of a pair of bishops into 10 bits so that any combination of bishop squares generates a different code. Simply, I could number the 32 light squares in any way I like from 0-31 and number the dark squares from 0-31 too. Then for a position, I could create 10 bits using the dark square's number for the upper 5 bits (of a 10 bit key - the rest zero) and using a light square's number for the lower 5 bits of a hash key. As a pair of white bishops move around the board, I would be sure not to get a hash clash. I could use the hash code for fast indexing of a custom endgame tablebase. That's a possible future aim of my hand crafted hash key idea. For various combinations of board pieces I might have to select a different collection of bits from the position's hash code, but it would be nice I could get something like that to work for me.

Now I am wondering if there is a simple scheme where I can hash the positions of a pair of rooks or knights into 11 bits?
Or even a complicated scheme. Is there a branch of maths that simply predicts whether such a scheme even exists? I suspect that for 2 pieces 11 bits might not be enough, even though for a normal pair of bishops I can do it in 10.