igs

igs (impartial game solver) is the Rust library by Piotr Beling for solving impartial games. Currently, only the normal play convention is supported, but support for misère games is planned.

igs can determine both an outcome class (i.e. a player with a winning strategy) and a nimber of any game position. The solver is highly configurable and can use many advanced techniques to speed up calculations, including:

• Pruning branches of search tree using the methods described in:
  • P. Beling, M, Rogalski, On pruning search trees of impartial games, Artificial Intelligence 283 (2020), doi: 10.1016/j.artint.2020.103262;
  • J. Lemoine, S. Viennot, Nimbers are inevitable, Theoretical Computer Science 462 (2012) 70–79, doi: 10.1016/j.tcs.2012.09.002.
• Independent analysis of the components of decomposable game positions through the Sprague–Grundy theorem.
• A transposition table that uses hashing (various implementations are available, including very compact ones) and can optionally be periodically saved to disk, allowing the calculation to be resumed after interruption.
• An endgame database that uses very little space thanks to methods based on perfect hashing, huffman compression or integer compression.
• Game-specific methods, such as heuristic move sorting.

igs has built-in support for the following games: Cram, Chomp (2 models), Grundy's game. Adding support for other games comes down to implementing the appropriate trait.