Advances in finding ideal play on poset games. (English) Zbl 1490.91030
Summary: Poset games are a class of combinatorial games that remain unsolved. M. Soltys and C. Wilson [Theory Comput. Syst. 48, No. 3, 680–692 (2011; Zbl 1217.68113)] proved that computing winning strategies is in PSPACE and aside from special cases such as nim and N-free games, P time algorithms for finding ideal play are unknown. This paper presents methods to calculate the nimber of poset games allowing for the classification of winning or losing positions. The results present an equivalence of ideal strategies on posets that are seemingly unrelated.
MSC:
| 91A46 | Combinatorial games |
Citations:
Zbl 1217.68113References:
| [1] | M. H. Albert, R. J. Nowakowski, D. Wolfe, Lessons in Play: An Introduction to Combinatorial Game Theory, CRC Press, Boca Raton, 2019. · Zbl 1410.91001 |
| [2] | S. Byrnes, Poset-Game Periodicity, Integers 3 (2003), Article G3. · Zbl 1128.91310 |
| [3] | J. H. Conway, R. K. Guy, E. R. Berlekamp, Winning Ways for Your Mathematical Plays Volume 1, AK Peters, Natick, 1983. · Zbl 1083.00003 |
| [4] | S. A. Fenner, J. Rogers, Combinatorial Game Complexity: An Introduction with Poset Games, arXiv:1505.07416 (2015). · Zbl 1409.68137 |
| [5] | M. Fisher, R. J. Nowakowski, C. Santos, Sterling Stirling Play, Internat. J. Game Theory 47(2) (2018), 557-576. · Zbl 1416.91059 |
| [6] | B.S.W. Schröder, Ordered Sets, Birkhäuser, Boston, 2003. · Zbl 1010.06001 |
| [7] | M. Soltys, C. Wilson, On the Complexity of Computing Winning Strategies for Finite Poset Games, Theory Comput. Syst 48(3) (2011), 680-692. · Zbl 1217.68113 |
| [8] | D. Zeilberger, Chomp, Recurrences and Chaos, J. Difference Equ. Appl 10(13-15) (2004), 1281-1293. · Zbl 1088.91011 |
| [9] | D. Zeilberger, Three-Rowed Chomp, Appl. Math, 26(2) (2001), 168-179. · Zbl 0977.91008 |
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.
