Strongly solving abstract strategy games is generally a computationally intensive task; for large games, computation must be parallelized to complete within a reasonable time. Prior solvers have used tools such as MapReduce to distribute work; however, this approach is hampered by high disk use. This report details the development of a new shard solver, which allows for the efficient solving of certain games on large-scale distributed computing nodes, while significantly reducing memory use. A particular target of this project was a fast and memory-efficient strong solve of the game Connect 4. Optimizations made in this project, as well as the improved solving paradigm provided by the shard solver, allowed for a solve in less than 6 hours on a 960-node system, while using less than one-eighth of the disk space required for a MapReduce Solve. In addition, a new compression scheme was developed for storing the resulting database, reducing the database size from a naive 32 TiB size to 557 GiB.




Download Full History