Skip to content
This repository has been archived by the owner on May 4, 2024. It is now read-only.
/ magics Public archive

Finding magic factors for bitboard based move generation

License

Notifications You must be signed in to change notification settings

niklasf/magics

Repository files navigation

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.

About

Finding magic factors for bitboard based move generation

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Sponsor this project

 

Packages

No packages published