On emulational equivalence of combinatorial games and the game Hackenforb

Abstract

In combinatorial game theory, two impartial games are considered equiv- alent if their corresponding Grundy values are equal. Although the developed theory is an irreplaceable tool when questions of the winner and the optimal strategy are concerned, it does not tell too much about the structural (dis)similarity between games. In this presentation we shall talk about another notion of equivalence of impartial combina- torial games, the so-called “emulational equivalence." This concept is stronger than the Grundy equivalence, but weaker than the isomor- phism between the game graphs. Intuitively, two games are emulation- ally equivalent if they reduce to the same game when positions that are “essentially the same" are not treated as distinct. We also define a new impartial combinatorial game on graphs called Hackenforb and show that various well-known combinatorial games (such as Nim, Sub- traction game, Notakto, Chomp) are emulationally equivalent to an instance of Hackenforb. We hope that it is not too ambitious to believe that, in some future, Hackenforb can establish itself as a new common “language" for studying many different games, and that this could help in bringing out some new possible directions from which we can ap- proach various open questions on combinatorial games and shed some light on them. Joint work with Bojan Bašić and Nikola Milosavljević.