The Hashtable Packing Problem (2020)

Summary

The Hashtable Packing Problem This is part of my project aiming to establish theoretical limits for bitboard based move generation in chess and similar games get as close to them as practically possible. The Hashtable Packing Problem is an optimization problem encountered when tuning Magic Bitboards in chess. Anyone trying to tackle it will have suspected that it is a hard problem, but (to my knowledge) so far no one has bothered proving that. But indeed: The abstract Hashtable Packing Problem is strongly \(\mathcal{NP}\)-complete. We can therefore stop looking for optimal solutions and instead use heuristics (and still sleep well). To follow the proof, no knowledge about chess or Magic Bitboards is required. A brief discussion about the implications for Magic Bitboards follows at the end. Definitions Definition: A Hashtable (for our purposes) is a list of integers \(\bar{b_0}, b_0, \ldots, \bar{b_i}, b_i, \ldots, \bar{b_n} \). This means in memory it consists of \(\bar{b_0}\) occupied buckets, followed by \(b_0\) empty buckets, followed by \(\bar{b_1}\) occupied buckets, and so on, alternating, ending with \(\bar{b_n}\) occupied buckets. Now imagine trying to arrange multiple hashtables in memory, possibly overlapping, while trying to minimize the used space. Definition: A Hashtable Packing for a list of hashtables \(B_0, \ldots, B_m\) is a list of integer offsets \(o_0, \ldots, o_m\). A hashtable packing is valid if none of the occupied buckets overlap, when building a combined hashtable by placing the hashtables at the given offsets in memory. That would be a hash collision for the combined table! The first occupied bucket of the combined table is at \(\min_{0 \le i \le m} o_i\). The last occupied bucket of the combined table is at \(\max_{0 \le i \le m} o_i + \sum_{\hat{b} \in B_i} \hat{b} + \sum_{b \in B_i} b \). The size of the hashtable packing is the number of buckets that need to be reserved in memory, including empty buckets between occupied buckets: $$ 1 ...