On tame, pet, domestic, and miserable impartial games

作者：Gurvich Vladimir; Ho Nhan Bao^*

来源：Discrete Applied Mathematics, 2018, 243: 54-72.

DOI：10.1016/j.dam.2017.12.006

• Impartial games
• Normal and misere play
• Sums of impartial games
• Sprague-Grundy function
• Tame
• Pet
• Domestic
• Miserable

Playing impartial games under the normal and misere conventions may differ a lot. However, there are also many "exceptions" for which the normal and misere Sprague-Grundy functions are very similar. The first such example, the game of NIM, was considered by Bouton as early as in 1901. In 1976 Conway introduced a large class of such games that he called tame games. Here we introduce a proper subclass, pet games, and a proper superclass, domestic games. For each of these three classes we provide efficiently verifiable characterizations. These games are closely related to another important subclass of the tame games introduced in 2007 by the first author and called miserable games. We show that tame, pet, and domestic games turn into miserable games by "slight modifications" of the definitions. We also show that the sum of miserable games is miserable and find several other classes that respect summation. The developed techniques allow us to prove that very many well-known impartial games fall into classes mentioned above. Such examples include all subtraction games, which are pet; game EUCLID, which is miserable (and, hence, tame), as well as many versions of the WYTHOFF game and NIM, which may be miserable, pet, or domestic.

• 出版日期2018-7-10