Skip to content
Finding magic factors for bitboard based move generation
C Python Cuda Makefile
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
cuda
new-results
results
v1
v2
LICENSE.txt
README.md
fig-benchmark-rf8.png
requirements.txt
verify.py

README.md

Finding magic factors for bitboard based move generation

Tool to find factors for Magic bitboards.

Exhaustive search

When looking for magic factors m with shift w it is sufficient to look in the range 2^{64 - w - lsb(r_max)} <= m < 2^{64 - lsb(r_max)} where r_max is the maximum relevant occupancy for the square [1].

Tricks for fast testing

  1. Avoid zero filling table (like Stockfish).
  2. Dynamically reorder relevant occupancies to fail earlier on average.

Performance comparison

Performance based on search of improved rook magics for f8.

Tools

verify.py <CANDIDATE>

Verifies a magic candidate.

v1/magics <CHUNK>

Select BISHOP or ROOK, SQUARE and EASY_SHIFT in v1/Makefile, make and run ./magics <CHUNK>. Tests all candidates in the specified range.

v2/daq

Select BISHOP or ROOK, SQUARE and SHIFT in v2/Makefile, make and run ./daq. Counts all magics with the specified settings.

cuda/test

Select square, piece type and shift in generate.py. make and run ./test to find magic factors with the specified shift or disprove their existence. Works best for bishop squares (with small shifts and small table sizes).

References

  1. Disproving the existence of some magics. 2017.
  2. No bishop magics with fixed shift 8. 2018.
You can’t perform that action at this time.