Page 1 of 1

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

Posted: Thu Feb 13, 2020 12:50 am
by niklasf
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: