General Restriction of $(s,t)$-Wythoff's Game

  • Wen An Liu
  • Haiyan Li
Keywords: impartial combinatorial game, normal play convention, misère play convention, $P$-position, $(s, t)$-Wythoff's game


A.S. Fraenkel introduced a new $(s,t)$-Wythoff's game which is a generalization of both Wythoff's game and $a$-Wythoff's game. Four new models of a restricted version of $(s,t)$-Wythoff's game, Odd-Odd $(s,t)$-Wythoff's Game, Even-Even $(s,t)$-Wythoff's Game, Odd-Even $(s,t)$-Wythoff's Game and Even-Odd $(s,t)$-Wythoff's Game, are investigated. Under normal or misère play conventions, all $P$-positions of these four models are given for arbitrary integers $s,t\geq 1$. For Even-Even $(s,t)$-Wythoff's Game, the structure of $P$-positions is given by recursive characterizations in terms of the mex function. For other models, the structures of $P$-positions are of algebraic form, which permit us to decide in polynomial time whether or not a given game position $(a,b)$ is a $P$-position.
Article Number