Solving games in parallel with linear-time perfect hash functions

In this paper, we propose an efficient method of solving one- and two-player combinato-rial games by mapping each state to a unique bit in memory. In order to avoid collisions, a concise portfolio of perfect hash functions is provided. Such perfect hash functions then address tables that serve as a compressed representation of the search space and support the execution of exhaustive search algorithms like breadth-first search and retrograde analysis. Perfect hashing computes the rank of a state, while the inverse operation unrank re-constructs the state given its rank. Efficient algorithms are derived, studied in detail and generalized to a larger variety of games. We study rank and unrank functions for permu-tation games with distinguishable pieces, for selection games with indistinguishable pieces, and for general reachability sets. The running time for ranking and unranking in all three cases is linear in the size of the state vector. To overcome space and time limitations in solving previously unsolved games like Frogs-and-Toads and Fox-and-Geese, we utilize parallel computing power in form of multipl