×

Recursive comparison tests for dicot and dead-ending games under misère play. (English) Zbl 1490.91040

Summary: In partizan games, where players Left and Right may have different options, there is a partial order defined as preference by Left: \(G \geqslant H\) if Left wins \(G+X\) whenever she wins \(H+X\), for any game position \(X\). In normal play, there is an easy test for comparison: \(G \geqslant H\) if and only if Left wins \(G-H\) playing second. In misère play, where the last player to move loses, the same test does not apply – for one thing, there are no additive inverses – and very few games are comparable. If we restrict the arbitrary game \(X\) to a subset of games \(\mathcal{U}\), we may have \(G \geqslant H\) “modulo \(\mathcal{U}\)”; but without the easy test from normal play, we must give a general argument about the outcomes of \(G+X\) and \(H+X\) for all \(X \in \mathcal{U}\). In this paper, we use the novel theory of absolute combinatorial games to develop recursive comparison tests for the well-studied universes of dicots and dead-ending games. This is the first constructive test for comparison of dead-ending games under misère play, using a new family of end-games called perfect murders.

MSC:

91A46 Combinatorial games

References:

[1] M.R. Allen, Peeking at partizan misère quotients, in R.J. Nowakowski (Ed.) Games of No Chance 4, MSRI Publ. 63 (2015), 1-12. · Zbl 1380.91037
[2] P. Dorbec, G. Renault, A.N. Siegel, and E. Sopena, Dicots, and a taxonomic ranking for misère games, J. Combin. Theory Ser. A 130 (2015), 42-63. · Zbl 1303.91052
[3] E.R. Berlekamp, J.H. Conway, and R.K. Guy, Winning Ways for Your Mathematical Plays, Vol. 2., A.K. Peters Ltd., MA, 2001. · Zbl 1005.00004
[4] A. Dwyer, R. Milley, and M. Willette, Misère domineering on 2×n boards, Integers, to appear.
[5] A. Dwyer, R. Milley, and M. Willette, Dead-ending day-2 games under misère play, Games of No Chance 6, MSRI Publ., submitted.
[6] J.M. Ettinger, Topics in Combinatorial Games, PhD Thesis, University of Wisconsin-Madison, 1996.
[7] S. Huntemann, The class of strong placement games: complexes, values, and temperature. PhD Thesis, Dalhousie University, 2018.
[8] U. Larsson, R.J. Nowakowski, and C.P. Santos, Absolute combinatorial game theory, in S. Huntemann and U. Larrson (Eds.) Games of No Chance 6, MSRI Publ. (2021), to appear.
[9] U. Larsson, R.J. Nowakowski, and C.P. Santos, Game comparison through play, Theoret. Comput. Sci. 725 (2018), 52-63. · Zbl 1402.91090
[10] U. Larsson, R.J. Nowakowski, C.P. Santos, manuscript.
[11] G.A. Mesdal and P. Ottaway, Simplification of partizan games in misère play, Integers 7 (2007), #G6. · Zbl 1165.91008
[12] R. Milley and G. Renault, Dead ends in misère play: the misère monoid of canonical numbers, Discrete Math. 313 (2013), 2223-2231. · Zbl 1293.91035
[13] R. Milley and G. Renault, Restricted developments in partizan misère game theory, in U. Larsson (Ed.) Games of No Chance 5, MSRI Publ. 70 (2018).
[14] T.E. Plambeck, Taming the wild in impartial combinatorial games, Integers 5 (2005), #G5. · Zbl 1092.91012
[15] T.E. Plambeck and A.N. Siegel, Misère quotients for impartial games, J. Combin. Theory Ser. A 115 (2008), 593-622. · Zbl 1142.91022
[16] A.N. Siegel, Misère canonical forms of partizan games, in R.J. Nowakowski (Ed.) Games of No Chance 4, MSRI Publ. 63 (2015). · Zbl 1380.91052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.