Hashtable packing (e.g. to optimize magic bitboards) is strongly NP-complete

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
niklasf
Posts: 42
Joined: Sat May 16, 2015 9:41 pm

Hashtable packing (e.g. to optimize magic bitboards) is strongly NP-complete

Post by niklasf » Thu Feb 13, 2020 12:50 am

2010 Volker Annuss shared his densely packed overlapping magic bitboards. The method he described was a heuristic based on simulated annealing.

I was wondering if there is a better algorithm to pack hashtables, maybe even an efficient algorithm to find an optimal packing. Probably unsurprisingly to most, the answer turns out to be "no" (unless P=NP). Maybe more intresting: There is not even a pseudo-polynomial algorithm, for example using dynamic programming, as sometimes seen for Knapsack Problems (unless P=NP).

I am aware that chess is a single finite instance, so asymptotic analysis is pointless. But at least:
We can conclude that an optimal solution cannot efficiently be obtained by decomposing the problem and abstractly working with the resulting hashtables. We would have to exploit deep connections between the rules of the game and mask-multiply-shift hash functions (if they even exist).

Such insights seem out of reach. [...]
Draft of the proof: https://backscattering.de/chess/hashtable-packing/

Post Reply