×

A class of extensions of restricted (\(s\), \(t\))-Wythoff’s game. (English) Zbl 1410.91128

Summary: Restricted (\(s\), \(t\))-Wythoff’s game, introduced by W. A. Liu and X. Zhao [Discrete Appl. Math. 179, 28–43 (2014; Zbl 1303.91054)], is an impartial combinatorial game. We define and solve a class of games obtained from restricted (\(s\), \(t\))-Wythoff’s game by adjoining to it some subsets of its \(P\)-positions as additional moves. The results show that under certain conditions they are equivalent to one case in which only one \(P\)-position is adjoined as an additional move. Furthermore, two winning strategies of exponential and polynomial are provided for the games.

MSC:

91A46 Combinatorial games
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 1303.91054
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Duchêne, E., Fraenkel, A.S., Nowakowski, R.J., Rigo, M., Extensions and restrictions of Wythoff’s game preserving its P-positions, J. Combin. Theory Ser. A, 2010, 117, 545-567.; Duchêne, E.; Fraenkel, A. S.; Nowakowski, R. J.; Rigo, M., Extensions and restrictions of Wythoff’s game preserving its P-positions, J. Combin. Theory Ser. A, 117, 545-567 (2010) · Zbl 1185.91061
[2] Fraenkel, A.S., New games related to old and new sequences, Integers, Electr. J. Combin. Number Theory, 2004, 4, #G6.; Fraenkel, A. S., New games related to old and new sequences, Integers, Electr. J. Combin. Number Theory, 4, #G6 (2004) · Zbl 1089.11017
[3] Berlekamp, E.R., Conway, J.H., Guy, R.K., Winning Ways for Your Mathematical Plays, Volume 1-4, A K Peters, Wellesley, MA, 2001-2004. 2nd edition: vol.1 (2001), vols. 2,3 (2003), vol. 4 (2004).; Berlekamp, E. R.; Conway, J. H.; Guy, R. K.; Peters, A. K.; , Winning Ways for Your Mathematical Plays, 4, 3 (2004) · Zbl 1084.00002
[4] Duchêne, E., Gravier, S., Geometrical extensions of Wythoff’s game, Discrete Math., 2009, 309, 3595-3608.; Duchêne, E.; Gravier, S., Geometrical extensions of Wythoff’s game, Discrete Math., 309, 3595-3608 (2009) · Zbl 1165.91007
[5] Fraenkel, A.S., How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly, 1982, 89, 353-361.; Fraenkel, A. S., How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly, 89, 353-361 (1982) · Zbl 0504.90087
[6] Fraenkel, A.S., Heap games, Numeration systems and Sequences, Annals Combin., 1998, 2, 197-210.; Fraenkel, A. S., Heap games, Numeration systems and Sequences, Annals Combin., 2, 197-210 (1998) · Zbl 0942.91015
[7] Fraenkel, A.S., Borosh, I., A generalization of Wythoff’s game, J. Combin. Theory, Ser. A, 1973,15,175-191.; Fraenkel, A. S.; Borosh, I., A generalization of Wythoff’s game, J. Combin. Theory, Ser. A, 15, 175-191 (1973) · Zbl 0265.90065
[8] Fraenkel, A.S., Zusman, D., A new heap game, Theoret. Comput. Sci., 2001, 252, 5-12.; Fraenkel, A. S.; Zusman, D., A new heap game, Theoret. Comput. Sci., 252, 5-12 (2001) · Zbl 0986.91002
[9] Liu, W.A., Li, H., General Restriction of (s, t)-Wythoff’s Game, Electron. J. Combin., 2014, 21(2), #P2.44.; Liu, W. A.; Li, H., General Restriction of (s, t)-Wythoff’s Game, Electron. J. Combin., 21, 2, #P2.44 (2014) · Zbl 1305.91053
[10] Li, H., Liu, S., Fraenkel, A.S., Liu, W.A., Variants of (s, t)-Wythoff’s game, accepted for publiction.; Li, H.; Liu, S.; Fraenkel, A. S.; Liu, W. A., Variants of (s, t)-Wythoff’s game, accepted for publiction · Zbl 1367.91042
[11] Fraenkel, A.S., Ozery, M., Adjoining to Wythoff’s game its P-positions as moves, Theoret. Comput. Sci., 1998, 205, 283-296.; Fraenkel, A. S.; Ozery, M., Adjoining to Wythoff’s game its P-positions as moves, Theoret. Comput. Sci., 205, 283-296 (1998) · Zbl 0915.90291
[12] Liu, W.A., Zhao, X., Adjoining to (s, t)-Wythoff’s game its P-positions as moves, Discrete Appl. Math., 2014, 179, 28-43.; Liu, W. A.; Zhao, X., Adjoining to (s, t)-Wythoff’s game its P-positions as moves, Discrete Appl. Math., 179, 28-43 (2014) · Zbl 1303.91054
[13] Li, H., Liu, S., Extensions and restrictions of a-Wythoff’s game, submitted for publiction.; Li, H.; Liu, S., Extensions and restrictions of a-Wythoff’s game, submitted for publiction
[14] Fraenkel, A.S., Systems of numeration, Amer. Math. Monthly92 (1985), 105-114.; Fraenkel, A. S., Systems of numeration, Amer. Math. Monthly, 92, 105-114 (1985) · Zbl 0568.10005
[15] Fraenkel, A.S., The vile, dopey, evil and odious game players, Discrete Math., 312 (2012), 42-46, special volume in honor of the 80th birthday of Gert Sabidussi.; Fraenkel, A. S., The vile, dopey, evil and odious game players, Discrete Math., 312, 42-46 (2012) · Zbl 1231.91046
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.