TalkChess.com

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 ?

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.

How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?

D Sceviour wrote:

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.

How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?

Yes seems he just forgot the color of pieces , just a small "newbie" détail lol

Daniel Anulliero wrote:

D Sceviour wrote:

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.

How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?

Yes seems he just forgot the color of pieces , just a small "newbie" détail lol

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.

Sven Schüle wrote:

Daniel Anulliero wrote:

D Sceviour wrote:

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.

How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?

Yes seems he just forgot the color of pieces , just a small "newbie" détail lol

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.

Ah ok sorry, didn't think about that lol seems I'm really à newbie
But would it be much slower than zobrist in term of access ?

Daniel Anulliero wrote:

Sven Schüle wrote:

Daniel Anulliero wrote:

D Sceviour wrote:

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.

How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?

Yes seems he just forgot the color of pieces , just a small "newbie" détail lol

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.

Ah ok sorry, didn't think about that lol seems I'm really à newbie
But would it be much slower than zobrist in term of access ?

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.

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.

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]

Henk wrote:I use this key for hash table.

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 &#40;int i = 0; i < SIZE; i++)
            &#123;
                if &#40;rep&#91;i&#93; != key&#91;i&#93;) return false;
            &#125;
            return true;
        &#125;

        

        public override int GetHashCode&#40;)
        &#123;
            int hash, i;
            for &#40;hash = i = 0; i < SIZE; ++i&#41;
            &#123;
                for &#40;int j = 0; j < 4; j++)
                &#123;
                    hash += &#40;int&#41;&#40;rep&#91;i&#93; >> &#40;j * 8&#41;);
                    hash += &#40;hash << 10&#41;;
                    hash ^= &#40;hash >> 6&#41;;
                &#125;
            &#125;
            hash += &#40;hash << 3&#41;;
            hash ^= &#40;hash >> 11&#41;;
            hash += &#40;hash << 15&#41;;
          
          
            return hash;
         &#125;

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]

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" ...

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.

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.