Sunday, November 06, 2016

[ulfdtybu] Transposition table key width

We modified the Stockfish chess engine, changing the width of the key stored in a transposition table entry, the key16 field in TTEntry, from 16 bits to 32 bits.  This changes the key width effectively from 16+27 = 43 bits to 32+27 = 59 bits.  The 27 comes from, in experiments below, hash table sizes such that there were 2^27 Clusters.  The hash table was 3840 megabytes for 16-bit (with padding / alignment disabled, otherwise it would have been 4096), and 4608 megabytes for 32-bit.  Hash 5000 was sufficient for both.

The tables below give the ranking of black responses to 1.e4, as reported by MultiPV 500 at various depths.  The top line is 16-bit unmodified Stockfish, 1 Thread.  The second line is 32-bit.  The colors are randomly assigned to moves.

Snapshot of the code used to generate the output below is on github.  Here is a patch against Official Stockfish 1c0c4db6775fae5a8b785630f4fd406c235880d9. 

This is a work in progress.  In the future, we hope to explore even wider hashes, wide enough that hash collisions do not occur.  We may also explore the region between 16 and 32 bits.

Here are more complete logs, including scores and pv.  "before" is 16-bit; "after" is 32-bit.

Previous work: Hyatt and Cozzie, "The effect of hash collisions in a Computer Chess program", which concludes that collisions do not affect performance much.  However, we feel that with computers having gotten much more powerful, and people running very long analyses, the birthday paradox is having a significant effect, as seen below.  Hash table collisions are obscuring the answer to the question, what is the ground truth about a position?  What is the best response to 1.e4?  Open game, French, Sicilian, Caro-Kann, or Nimzowitsch?

Depth 1

d5e5e6d6Nf6Nc6h5g6c5Nh6g5b6c6a5h6a6Na6f6f5b5
d5e5e6d6Nf6Nc6h5g6c5Nh6g5b6c6a5h6a6Na6f6f5b5

Depth 2

d5e5e6d6Nc6h5Nf6c5b6g6Na6c6h6a5g5Nh6f5f6a6b5
d5e5e6d6Nc6h5Nf6c5b6g6Na6c6h6a5g5Nh6f5f6a6b5

Depth 3

d5e5Nc6Nf6h5d6e6h6b6c5Na6c6a5Nh6g6a6g5b5f6f5
d5e5Nc6Nf6h5d6e6h6b6c5Na6c6a5Nh6g6a6g5b5f6f5

Depth 4

d5Nc6e5d6e6c6c5f6f5h5Nh6h6g6a5a6g5b5Na6b6Nf6
d5Nc6e5d6e6c6c5f6f5h5Nh6h6g6a5a6g5b5Na6b6Nf6

Depth 5

Nc6d5Nf6h5c6e5h6a6e6d6b6a5Nh6c5g6Na6b5f6g5f5
Nc6d5Nf6h5c6e5h6a6e6d6b6a5Nh6c5g6Na6b5f6g5f5

Depth 6

d5Nc6e5e6h5c6f5c5d6h6f6Na6Nf6a6g6b6a5Nh6b5g5
d5Nc6e5e6h5c6f5c5d6h6f6Na6Nf6a6g6b6a5Nh6b5g5

Depth 7

e5d5f5c5Nf6d6e6h6a5Nc6h5b6Na6a6c6b5Nh6f6g6g5
e5d5f5c5Nf6d6e6h6a5Nc6h5b6Na6a6c6b5Nh6f6g6g5

Depth 8

d5e5f5Nc6Nf6a6e6c5h5b6d6Na6c6a5h6b5Nh6g5f6g6
d5e5f5Nc6Nf6a6e6c5h5b6d6Na6c6a5h6b5Nh6g5f6g6

Depth 9

e5e6Nf6c5d5a5Nc6c6d6h6h5a6f5b6f6Nh6b5g5Na6g6
e5e6Nf6c5d5a5Nc6c6d6h6h5a6f5b6f6Nh6b5g5Na6g6

Depth 10

e5d5Nc6e6c5a6h5d6c6h6b6g6Nf6f6a5Na6f5Nh6b5g5
e5d5Nc6e6c5a6h5d6c6h6b6g6Nf6f6a5Na6f5Nh6b5g5

Depth 11

e5e6Nc6h6a6c6c5d5Nf6d6b6h5g6a5f5f6Na6Nh6b5g5
e5e6Nc6h6a6c6c5d5Nf6d6b6h5g6a5f5f6Na6Nh6b5g5

Depth 12

e5e6d5a6c6d6c5Nc6h6b6Nf6a5h5Nh6f5Na6g6f6g5b5
e5e6d5c6a6d6Nc6c5h6h5Nf6f5b6a5g6f6g5Nh6Na6b5

Depth 13

e5e6Nc6c6a6c5d5d6h6h5Nf6b6a5g6Nh6Na6f5g5f6b5
e5e6a6c5Nc6d5c6h6d6Nh6b6h5Nf6a5f5g6Na6f6g5b5

Depth 14

e5e6h6c5a6Nc6c6d5Nf6g6d6b6h5a5Nh6g5f5Na6f6b5
e5e6c5a6h6Nf6Nc6c6d6d5h5b6a5g6Na6f5f6g5Nh6b5

Depth 15

e6e5Nc6a6c5c6d5h6Nf6d6g6b6h5Nh6a5g5Na6f6f5b5
e6e5h6c5d5a6c6Nc6d6Nf6g6h5a5b6Na6f6g5Nh6f5b5

Depth 16

e6d6c5h6e5Nc6Nf6a6c6d5g6h5a5b6Nh6f6Na6g5f5b5
e5e6h6c5Nc6d5d6c6Nf6a6g6b6h5a5Na6g5f6Nh6f5b5

Depth 17

e6e5Nc6d6c5Nf6h6c6d5a6g6b6h5a5Na6Nh6f6g5f5b5
e5e6c5h6c6Nc6d5Nf6b6d6a6g6a5h5Nh6Na6f6g5f5b5

Depth 18

e5c5e6Nc6c6d6h6a6Nf6b6d5a5g6h5Na6Nh6f5g5f6b5
e5Nc6e6c6c5b6Nf6h6a6d6d5g6a5h5Na6Nh6f6b5g5f5

Depth 19

e6e5c5Nc6a6c6b6d6h6Nf6d5g6a5h5Na6Nh6f6g5f5b5
c5e6e5Nc6b6c6h6a6d6d5Nf6g6Na6a5h5Nh6f6g5b5f5

Depth 20

e6c5Nc6e5b6h6c6d6Nf6a6d5g6a5h5Na6Nh6f6g5f5b5
c5e6e5h6c6b6Nc6d6a6d5Nf6g6Na6a5h5Nh6g5f6f5b5

Depth 21

e5e6c5b6c6h6Nc6d6Nf6a6Na6a5d5g6h5Nh6f6f5g5b5
e6c5e5Nc6b6c6d6a6h6Nf6g6d5a5Na6h5Nh6f6g5f5b5

Depth 22

e5e6Nc6c5c6a6b6h6d6Nf6d5Na6g6a5h5f6Nh6b5g5f5
e6e5Nc6c5b6a6c6d6h6Nf6d5g6Na6a5Nh6h5f6f5g5b5

Depth 23

c5e6e5Nc6c6h6d6a6b6Nf6d5Na6g6a5h5Nh6f6g5f5b5
Nc6c5e6b6e5d6a6c6Nf6h6a5d5g6Na6h5Nh6f6g5f5b5

Depth 24

e5c5e6Nc6c6b6d6h6a6Nf6g6Na6d5a5h5Nh6f6g5f5b5
c5e5e6b6Nc6h6c6d6Nf6a6a5d5g6Na6h5f6Nh6f5g5b5

Depth 25

e5e6c5Nc6c6b6h6d6a6Nf6a5d5g6Na6h5f6Nh6b5g5f5
e5e6Nc6c5d6c6b6a6d5h6a5g6Nf6Na6h5Nh6f6g5b5f5

Depth 26

e5e6Nc6c5c6d6b6a6h6Nf6d5g6a5Na6h5Nh6f6g5f5b5
e5e6Nc6c5c6d6a6b6h6d5Nf6a5g6Na6h5f6Nh6g5f5b5

Depth 27

e6e5c5c6Nc6d6a6b6h6g6Nf6d5Na6a5h5f6Nh6g5f5b5
e6e5c5Nc6c6d6a6b6h6d5g6Nf6a5Na6h5Nh6f6f5g5b5

Depth 28

e6c5e5c6Nc6a6d6h6b6g6Nf6a5d5Na6h5Nh6f6g5b5f5
e6e5c6c5Nc6h6b6Nf6a6d6a5d5g6Na6Nh6h5f6b5f5g5

Depth 29

e5Nc6c6e6c5a6d6h6g6Nf6a5b6d5Na6h5Nh6f6b5g5f5
c5e5Nc6e6c6h6d6b6Nf6a6d5a5g6Na6Nh6h5f6g5f5b5

Depth 30

e5e6c5c6Nc6a6d6Nf6h6a5g6d5b6Na6h5Nh6f6b5f5g5
c5e5Nc6e6h6c6Nf6d6a6b6a5d5g6Na6h5Nh6f6b5f5g5

Depth 31

e5e6c5Nc6c6a6Nf6a5d6h6d5g6b6Na6h5Nh6f6f5b5g5
e5c5e6Nc6b6h6c6d6a6Nf6d5a5g6Na6Nh6h5f6f5g5b5

Depth 32

Nc6c5e6e5c6a6b6d6g6Nf6h6a5d5Na6h5Nh6f6f5g5b5
e5e6c5c6Nc6b6Nf6d6d5a6g6h6a5Na6Nh6h5f6f5b5g5

Depth 33

e6Nc6e5c5c6a6b6Nf6h6d6g6d5a5Na6h5Nh6f6f5g5b5
e6e5Nc6c5c6b6Nf6d6a6d5h6g6a5Na6h5Nh6f6f5g5b5

Depth 34

e6e5c5c6a6Nc6a5b6d5Nf6d6h6g6Na6h5Nh6f6f5b5g5
c5e5Nc6c6e6a6d6b6Nf6g6d5a5h6Na6h5Nh6f6f5b5g5

Depth 35

e6c5c6a6Nc6d6e5Nf6a5h6b6d5g6Na6Nh6h5f6f5g5b5
e6e5c5c6Nc6Nf6a6d6a5d5g6h6b6Na6h5Nh6f6f5b5g5

Depth 36

e6c5c6Nc6e5d6Nf6g6a5a6d5h6b6Na6h5Nh6f6f5g5b5
e5e6c5c6Nc6a6Nf6g6d6d5a5b6h6Na6h5Nh6f6f5b5g5
Posted by at
Labels: ,

No comments :

Post a Comment

Subscribe to: Post Comments ( Atom )