Isomorphism theorems for impartial combinatorial games

Mikhail Baltushkin; Dana C. Ernst; Na´ ndor Sieben

doi:10.47443/dml.2025.071

Author(s)

Mikhail Baltushkin Department of Mathematics and Statistics, Northern Arizona University,Flagstaf, Arizona 86011-5717,USA

Dana C. Ernst Department of Mathematics and Statistics, Northern Arizona University,Flagstaf, Arizona 86011-5717,USA

Na´ ndor Sieben Department of Mathematics and Statistics, Northern Arizona University,Flagstaf, Arizona 86011-5717,USA

Abstract

We introduce the category of optiongraphs and option-preserving maps as a model to study impartial combinatorial games. Outcomes, remoteness, and extended nim-values are preserved under option-preserving maps. We show that the four isomorphism theorems from universal algebra are valid in this category. Quotient optiongraphs, including the minimum quotient, provide simplifications that can help in the analysis of games.

Publication Details

Page(s) 59-66

DOI 10.47443/dml.2025.071

Published Journal: Discrete Mathematics Letters, Volume: 16, Issue: 0, Year: 2025

Request the full text from PASTIC

Keywords

congruence relation, minimum quotient, option-preserving map, Isomorphism theorems, impartial game

References

Albert M. H.,Nowakowski R. J.,Wolfe D. .2007 .Lessons in Play: An Introduction to Combinatorial Game Theory. , : .

Baltushkin M.,Ernst D. C.,Sieben N. .2025 .. , : .

Banerji R. B.,Intelligence Artificial,Approach A Theoretical .1980 .. , : .

Banerji R. B.,Ernst G. W. .1972 .Strategy construction using homomorphisms between games. Artificial Intelligence, 3 : 223-249.

B. Basˇi c´ ,Ellis P.,Ernst D. C.,Sieben N. .2024 .Categories of impartial rulegraphs and gamegraphs. Internat. J. Game Theory, 53(4) : 1407-1433.

Berlekamp E. R.,Conway J. H.,Guy R. K. .2003 .. , 2 : .

Conway J. H. .2001 .. , : .

Fraenkel A. S.,Perl Y. .1975 .Constructions in combinatorial games with cycles. Proc. Internat. Colloq. on Infinite and Finite Sets, 10 : 667-699.

Fraenkel A. S.,Yesha Y. .1982 .Theory of annihilation games I, J. Theory Ser. B, 33(1) : 60-86.

Fraenkel A. S.,Y. Yesha, A. S. .1986 .The generalized Sprague-Grundy function and its invariance under certain mappings. J. Combin. Theory Ser. A, 43(2) : 165-177.

P. M. Grundy .1939 .. Eureka, 2 : 6-8.

Guns T. .2019 .Increasing modeling language convenience with a universal n-dimensional array, CPpy as Python-embedded example. Proceedings of the 18th workshop on Constraint Modelling and Reformulation at CP, 19 : .

Larsson U.,Nowakowski R. J.,Santos C. P. .2021 .Impartial games with entailing moves, Integers 21B (. , : A17.

Li S.-Y. R. .1974 .Generalized impartial games. Internat. J. Game Theory, 3 : 169-184.

McKay B. . .. , : .

Foundation OEIS . .Inc. The On-Line Encyclopedia of Integer Sequences, : .

Siegel A. N. .2005 .. Ph.D. thesis, : .

Siegel A. N.,Albert M. H.,Nowakowski R. J .2009 .Coping with cycles. Games of No Chance III, : 91-123.

Siegel A. N. .2013 .. American Mathematical Society, : .

Smith C. A. .1966 .. J. Combin. Theory, 1 : 51-81.

Sprague R. P. .1936 .. , 41 : 438-444.