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:
Draft of the proof: https://backscattering.de/chess/hashtable-packing/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. [...]