No Zobrist key

[bob]

I don't do that in Make/Unmake. I do that at the time I use the signature to probe or store. You don't want to xor in side to move at ply=1, then xor it in again at ply=3, as you just undid the xor.

I don't follow.
After making a move I always xor in the STM key, which makes BTM and WTM positions differ by exactly this key. Why would one not do that?

You can, or you can do as I do and if it is wtm, I use the key as stored, if it is btm, I complement the key and use that... This way I don't have to do anything in Unmake() or Make() regarding side-to-move.

[bob]

I wonder if I can do

Code: Select all

..make move ..
Hash ^= new ep 
Hash ^= new castling right
Hash ^= new stm

Instead of

Code: Select all

Hash ^= old ep (remove old code from hashcode);make(or not) ep
Hash ^= new ep
Hash ^= old castling right; make castling (or not)
Hash ^= new castling right
Hash ^= old stm; change stm
Hash ^= new stm

I do that in Isa , but if we can do the same with only 3 ^ opérations it'll be better

Instead of

Code: Select all

Hash ^= old stm; change stm
Hash ^= new stm

you can certainly always use:

Code: Select all

change stm; Hash ^= stmKey

since you do not need two different stm keys. In WTM positions stmKey is out and in BTM positions it has been XORed into the hash key.

The first of the two methods above is the one explained by HGM. I'm starting to like it since it has potential to both simplify and (slightly) speed up the makeMove code. It requires some other changes but I think I'll give it a try.

And you can lose the memory reference by

if (stm == 0) temp_hash = ~Hash;
else temp_hash = Hash; Turns into one cmov instruction.

[hgm]

That is equivalent to using a hard-coded stm key = -1.

[Uri Blass]

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 ?

You can easily store it with 4*64 bits and allow a lot of crazy illegal positions with more than one king and with 64 pieces on the board.


store the content of every square by 4 bits and store the content of every 2 ranks by one bitboard.

Engines may practically play for the following positions and I wonder if you can compose an illegal position that is basically easier for humans relative to computers.

[D]4k3/pppppppp/pppppppp/pppppppp/PPPPPPPP/PPPPPPPP/PPPPPPPP/4K3 w - - 68 1

[D]rrrrkrrr/qqqqqqqq/pppppppp/pppppppp/PPPPPPPP/PPPPPPPP/QQQQQQQQ/RRRRKRRR w - - 68 1

You may try to play a tournament of engines that can play the last positions to see which engine is the best.

Stockfish can get only small depths in the last position
Some other engines crash and some other engines show strange behaviour like having a score with no move.

Here is the analysis by Spike that easily get depth 80 in this position

[D]rrrrkrrr/qqqqqqqq/pppppppp/pppppppp/PPPPPPPP/PPPPPPPP/QQQQQQQQ/RRRRKRRR w - - 68 1

Spike 1.4:
0 00:00 0 0 0.00
1 00:00 7 2k 0.00
1 00:00 11 3k 0.00
2 00:00 13 3k 0.00
2 00:00 17 4k 0.00
3 00:00 19 5k 0.00
3 00:00 23 6k 0.00
4 00:00 25 6k 0.00
4 00:00 29 7k 0.00
5 00:00 31 8k 0.00
5 00:00 35 9k 0.00
6 00:00 37 9k 0.00
6 00:00 41 10k 0.00
7 00:00 43 11k 0.00
7 00:00 47 12k 0.00
8 00:00 49 12k 0.00
8 00:00 53 13k 0.00
9 00:00 55 14k 0.00
9 00:00 59 15k 0.00
10 00:00 61 15k 0.00
10 00:00 65 16k 0.00
11 00:00 67 17k 0.00
11 00:00 71 18k 0.00
12 00:00 73 18k 0.00
12 00:00 77 19k 0.00
13 00:00 79 20k 0.00
13 00:00 83 21k 0.00
14 00:00 85 21k 0.00
14 00:00 89 22k 0.00
15 00:00 91 23k 0.00
15 00:00 95 24k 0.00
16 00:00 97 24k 0.00
16 00:00 101 25k 0.00
17 00:00 103 26k 0.00
17 00:00 107 27k 0.00
18 00:00 109 27k 0.00
18 00:00 113 28k 0.00
19 00:00 115 29k 0.00
19 00:00 119 30k 0.00
20 00:00 121 30k 0.00
20 00:00 125 25k 0.00
21 00:00 127 25k 0.00
21 00:00 131 26k 0.00
22 00:00 133 27k 0.00
22 00:00 137 27k 0.00
23 00:00 139 28k 0.00
23 00:00 143 29k 0.00
24 00:00 145 29k 0.00
24 00:00 149 30k 0.00
25 00:00 151 30k 0.00
25 00:00 155 31k 0.00
26 00:00 157 31k 0.00
26 00:00 161 32k 0.00
27 00:00 163 23k 0.00
27 00:00 167 24k 0.00
28 00:00 169 24k 0.00
28 00:00 173 25k 0.00
29 00:00 175 25k 0.00
29 00:00 179 26k 0.00
30 00:00 181 26k 0.00
30 00:00 185 23k 0.00
31 00:00 187 23k 0.00
31 00:00 191 24k 0.00
32 00:00 193 24k 0.00
32 00:00 197 25k 0.00
33 00:00 199 25k 0.00
33 00:00 203 25k 0.00
34 00:00 205 26k 0.00
34 00:00 209 26k 0.00
35 00:00 211 26k 0.00
35 00:00 215 27k 0.00
36 00:00 217 27k 0.00
36 00:00 221 28k 0.00
37 00:00 223 28k 0.00
37 00:00 227 28k 0.00
38 00:00 229 29k 0.00
38 00:00 233 29k 0.00
39 00:00 235 29k 0.00
39 00:00 239 30k 0.00
40 00:00 241 30k 0.00
40 00:00 245 31k 0.00
41 00:00 247 31k 0.00
41 00:00 251 31k 0.00
42 00:00 253 32k 0.00
42 00:00 257 32k 0.00
43 00:00 259 32k 0.00
43 00:00 263 33k 0.00
44 00:00 265 33k 0.00
44 00:00 269 34k 0.00
45 00:00 271 34k 0.00
45 00:00 275 34k 0.00
46 00:00 277 35k 0.00
46 00:00 281 35k 0.00
47 00:00 283 35k 0.00
47 00:00 287 36k 0.00
48 00:00 289 36k 0.00
48 00:00 293 37k 0.00
49 00:00 295 37k 0.00
49 00:00 299 37k 0.00
50 00:00 301 38k 0.00
50 00:00 305 38k 0.00
51 00:00 307 38k 0.00
51 00:00 311 39k 0.00
52 00:00 313 653 0.00
52 00:00 317 661 0.00
53 00:00 319 665 0.00
53 00:00 323 674 0.00
54 00:00 325 678 0.00
54 00:00 329 686 0.00
55 00:00 331 691 0.00
55 00:00 335 699 0.00
56 00:00 337 703 0.00
56 00:00 341 711 0.00
57 00:00 343 716 0.00
57 00:00 347 724 0.00
58 00:00 349 728 0.00
58 00:00 353 736 0.00
59 00:00 355 741 0.00
59 00:00 359 749 0.00
60 00:00 361 753 0.00
60 00:00 365 762 0.00
61 00:00 367 766 0.00
61 00:00 371 774 0.00
62 00:00 373 778 0.00
62 00:00 377 787 0.00
63 00:00 379 791 0.00
63 00:00 383 799 0.00
64 00:00 385 803 0.00
64 00:00 389 812 0.00
65 00:00 391 816 0.00
65 00:00 395 824 0.00
66 00:00 397 827 0.00
66 00:00 401 835 0.00
67 00:00 403 839 0.00
67 00:00 407 847 0.00
68 00:00 409 852 0.00
68 00:00 413 860 0.00
69 00:00 415 864 0.00
69 00:00 419 872 0.00
70 00:00 421 877 0.00
70 00:00 425 885 0.00
71 00:00 427 889 0.00
71 00:00 431 897 0.00
72 00:00 433 902 0.00
72 00:00 437 910 0.00
73 00:00 439 914 0.00
73 00:00 443 922 0.00
74 00:00 445 927 0.00
74 00:00 449 935 0.00
75 00:00 451 939 0.00
75 00:00 455 947 0.00
76 00:00 457 952 0.00
76 00:00 461 960 0.00
77 00:00 463 483 0.00
77 00:00 467 487 0.00
78 00:00 469 490 0.00
78 00:00 473 494 0.00
79 00:00 475 496 0.00
79 00:00 479 500 0.00
80 00:00 481 502 0.00
80 00:00 485 506 0.00

[pkumar]

Another "mystic" code that works:

Code: Select all

class Zobrist
{
public:
    uint64 hash_pc[2][MAX_PIECETYPES][64], hash_castle[16], hash_ep[8];
    Zobrist();

private:
    uint32 w;
    uint32 z;
    uint32 rand32();
    uint64 rand64();
    void initKeys();
};

// Zobrist has a simple random number generator based on
// George Marsaglia's MWC (multiply with carry) generator.
// Although it is very simple, it passes Marsaglia's DIEHARD
// series of random number generator tests.
// See http://www.codeproject.com/Articles/25172/Simple-Random-Number-Generation

Zobrist::Zobrist()
{
    // These were the default seed values Marsaglia used.
    // Any pair of unsigned integers should be fine.

    w = 521288629;
    z = 362436069;
    initKeys();
}

uint32 Zobrist::rand32()
{
    z = 36969 * (z & 65535) + (z >> 16);
    w = 18000 * (w & 65535) + (w >> 16);
    return &#40;z << 16&#41; + &#40;w & 65535&#41;;
&#125;

uint64 Zobrist&#58;&#58;rand64&#40;)
&#123;
	uint64 key = rand32&#40;);
	key = &#40;key<<32&#41; + rand32&#40;);
	return key;
&#125;

void Zobrist&#58;&#58;initKeys&#40;)
&#123;
   for&#40;int side = 0; side<2; ++side&#41;
	&#123;
		for&#40;int piece = EMPTY; piece<=KING; ++piece&#41;
		&#123;
			for&#40;int sqr = 0; sqr<64; ++sqr&#41;
				hash_pc&#91;side&#93;&#91;piece&#93;&#91;sqr&#93; = rand64&#40;);
		&#125;
	&#125;

	for&#40;int i = 0; i<16; ++i&#41;
		hash_castle&#91;i&#93; = rand64&#40;);

	for&#40;int column = 0; column<8; ++column&#41;
		hash_ep&#91;column&#93; = rand64&#40;);
&#125;

[stegemma]

Is that about Zobrist hash key computation ?

[For making and unmaking a move I currently have to update these bit boards and also a chessboard of squares]

Yes, it is about the incremental update of the hash signature. That was what you were originally asking about I thought...

The computational cost for this should be near zero.

The updating itself has a cost of about zero but there could be a little cost if you need to extract the piece type and then the index, to get the key to xor from the move. If you only store src/dst squares as 64 bit values, then it is not obvious how to extract the piece type, for sample (you have to query the six bitboards, to know what piece moves).

[stegemma]

[...]
Because in my logic, I do (for exemple white have to play) :

Code: Select all

Make move
Hash ^= stm (white) remove white stm from hashcode
Change the color to black (now stm = black)
Hash ^= stm ( black)

And I do that for ep and castle rights too.
Some lights by Bob are welcome

If you use two different value for white/black stm, then you can also use a single xor:

Code: Select all

static const uint64_t stmwb = stm(white) ^ stm(black);
...
make move
Hash ^= stmwb;

Me too I don't do that and I xor the color only when I need the key (but it is not so important).

[Henk]

A fast hash function does not help much. But usage of short keys cost less memory.

[Henk]

A 70 elo change will cost you a day but a two elo change two weeks.