A new approach to equivalence of games

Abstract

The well-known Sprague-Grundy theory states that every impartial combinatorial game played under the so-called normal play convention is equivalent to a single Nim heap. However, this theory does not tell anything about the structure of game graphs of the concerned games, and does not work under the misère play convention. We suggest a new notion of equivalence of games, named emulational equivalence. It is stronger than the Sprague-Grundy equivalence and weaker than the isomorphism of game graphs, and it can be applied regardless of whether the game is played under normal or under misère convention. Additionally, we introduce a new game on graphs named Hackenforb, which turns out to have a great emulational potential, namely, for various impartial games we were able to construct Hackenforb instances emulationally equivalent to them.

(Joint work with Bojan Bašić and Nikola Milosavljević)