My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
I wonder if it is important to change that. Would my engine run much faster using Zobrist key ?
No Zobrist key
Moderators: hgm, Rebel, chrisw
-
- Posts: 570
- Joined: Mon Jul 20, 2015 5:06 pm
Re: No Zobrist key
How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
-
- Posts: 759
- Joined: Fri Jan 04, 2013 4:55 pm
- Location: Nice
Re: No Zobrist key
Yes seems he just forgot the color of pieces , just a small "newbie" détail lolD Sceviour wrote:How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: No Zobrist key
Sorry Dennis and Daniel but 8 bitboards are sufficient if you use 6 for the piece types and 2 for the colors. It is also slightly more efficient since all these bitboards fit into one cache line and testing only for the color of a piece on a given square does not require OR-ing of 6 bitboards. Of course it is also a matter of your piece encoding.Daniel Anulliero wrote:Yes seems he just forgot the color of pieces , just a small "newbie" détail lolD Sceviour wrote:How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
-
- Posts: 759
- Joined: Fri Jan 04, 2013 4:55 pm
- Location: Nice
Re: No Zobrist key
Ah ok sorry, didn't think about that lol seems I'm really à newbieSven Schüle wrote:Sorry Dennis and Daniel but 8 bitboards are sufficient if you use 6 for the piece types and 2 for the colors. It is also slightly more efficient since all these bitboards fit into one cache line and testing only for the color of a piece on a given square does not require OR-ing of 6 bitboards. Of course it is also a matter of your piece encoding.Daniel Anulliero wrote:Yes seems he just forgot the color of pieces , just a small "newbie" détail lolD Sceviour wrote:How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
But would it be much slower than zobrist in term of access ?
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: No Zobrist key
I did not understand exactly what Henk does. If he uses 8 x 64 = 512 bits as a hash key for TT access then I don't know how this should be working. So maybe he means that he uses 512 instead of 64 bits to compare two positions, e.g. for repetition detection. That may be ok, if this is slower at all then you won't notice it much, I think, since repetition detection is done once per node and for few positions on average.Daniel Anulliero wrote:Ah ok sorry, didn't think about that lol seems I'm really à newbieSven Schüle wrote:Sorry Dennis and Daniel but 8 bitboards are sufficient if you use 6 for the piece types and 2 for the colors. It is also slightly more efficient since all these bitboards fit into one cache line and testing only for the color of a piece on a given square does not require OR-ing of 6 bitboards. Of course it is also a matter of your piece encoding.Daniel Anulliero wrote:Yes seems he just forgot the color of pieces , just a small "newbie" détail lolD Sceviour wrote:How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
But would it be much slower than zobrist in term of access ?
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: No Zobrist key
As Gerd Isenberg and Fabio Gabbato will tell you: 4 is as dense as possible. You store a single colour bitboard (usually for the side to move, but it depends), and three other bitboards for various combinations of pieces. Then the single piece types can be obtained by ANDing and NOTs and necessary.
Whether this extra computation outweighs the fewer memory accesses is up for debate, though these bitboards can be fairly trivially flipped after each move to implement colour-agnostic move generation.
Whether this extra computation outweighs the fewer memory accesses is up for debate, though these bitboards can be fairly trivially flipped after each move to implement colour-agnostic move generation.
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: No Zobrist key
I use this key for hash table.
And I wonder if it does make my engine slow and if Zobrist key would be much better. But hash table is not used in qSearch.
[Don't ask how GetHashCode works for it's abracadabra to me now]
Code: Select all
public Key(IChessBoardBits board)
{
rep = new ulong[SIZE];
rep[0] = board.Pawns;
rep[1] = board.Kings;
rep[2] = board.Knights;
rep[3] = board.Bishops;
rep[4] = board.Rooks;
rep[5] = board.Queens;
rep[6] = board.WhitePieces;
rep[7] = board.Other;
}
public bool Equals(Key key)
{
for (int i = 0; i < SIZE; i++)
{
if (rep[i] != key[i]) return false;
}
return true;
}
public override int GetHashCode()
{
int hash, i;
for (hash = i = 0; i < SIZE; ++i)
{
for (int j = 0; j < 4; j++)
{
hash += (int)(rep[i] >> (j * 8));
hash += (hash << 10);
hash ^= (hash >> 6);
}
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
[Don't ask how GetHashCode works for it's abracadabra to me now]
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: No Zobrist key
That's 32 memory accesses to rep (hopefully most from cache) plus 152 shifts (j * 8 is like j << 3), 80 "+=" and 40 "^=" operations, plus some loop control stuff. A lot of calculation, even if almost everything is done in registers, and it will certainly burn many CPU cycles. "Beware of nested loops" ...Henk wrote:I use this key for hash table.
And I wonder if it does make my engine slow and if Zobrist key would be much better. But hash table is not used in qSearch.Code: Select all
public Key(IChessBoardBits board) { rep = new ulong[SIZE]; rep[0] = board.Pawns; rep[1] = board.Kings; rep[2] = board.Knights; rep[3] = board.Bishops; rep[4] = board.Rooks; rep[5] = board.Queens; rep[6] = board.WhitePieces; rep[7] = board.Other; } public bool Equals(Key key) { for (int i = 0; i < SIZE; i++) { if (rep[i] != key[i]) return false; } return true; } public override int GetHashCode() { int hash, i; for (hash = i = 0; i < SIZE; ++i) { for (int j = 0; j < 4; j++) { hash += (int)(rep[i] >> (j * 8)); hash += (hash << 10); hash ^= (hash >> 6); } } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); return hash; }
[Don't ask how GetHashCode works for it's abracadabra to me now]
Btw, where are the other properties of the position like side to move, castling rights, ep target square, that need to have an influence on the hash key?
I would ask some different questions first before asking about the performance: does this hash function distribute well over the whole index range (so your hash table will reach 100% "used" entries after some moves), and what is your collision rate?
Speed-wise it is clear that this way is slow since you always have to calculate the hash key from scratch while the Zobrist method allows to do that incrementally based on very few XORs. But if there are massive functional drawbacks then the speed argument would not matter any longer, of course ...
The distribution properties of the hash function could be analyzed by running a simulation where you allocate a table of N entries (N = your typical number of hash table entries) with 1 bit per entry (or, to save programming effort, one byte representing a bool), initialize the table to 0, generate many "realistic random positions" (more than N), calculate your hash function for each position, take its index bits as indicated by N, and set table[index] to 1. Then count how often you store a "1" where you already had a "1" before, and how many entries remain at "0" in the end.
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: No Zobrist key
Properties side to move, castling rights, ep target square are stored in
If you know a much simpler and still effective formula to compute a hash key then that would be better. For I don't like mystic code. Might be I found it somewhere on internet. Can't remember.
Code: Select all
rep[7] = board.Other;