Big List of examples of recreational finite unbounded games

Question

What are some examples of mathematical games that can take an unbounded amount of time (a.k.a. there are starting positions such that for any number $n$, there is a line of play taking $>n$ times) but is finite (every line of play eventually ends.) Also, it would be nice if it were recreational in nature (by this I mean I basically mean its nontrivial, I could conceivably be enjoyed by humans theortically.) One answer per game please, but edit variants into the same answer.

This is a big-list question, so many answers would be appreciated.

Answer 1

One example is Sylver's Coinage played like so:

Player's alternate selecting positive integers ($1, 2, 3, 4\dots$). The rule is that no number is allowed to be expressed as sum (with possible duplicates) of the previous. For example, say $\{4, 8, 5, 7\}$ ($8$ would have had to been said before $4$) was previously said. Then $6$ could be said, but $14$ could not, for it is equal to $5+5+4$ (or $7+7$.) The player who says $1$ loses! (If you prefer normal play convention, outlaw the number $1$ and then the last player who can move wins!)

This game is unbounded ($\{n, n-1, n-2, \dots n/2\}$), but, according to a theorem of arithmetic, finite (if you have trouble even seeing how this game could end, note that when $2$ and $3$ are said, all even numbers, and all odd number more that $3$ are illegal.

Does anyone know any variants (say based on different mathematical structures than positive integers? Ordinals maybe?)

Answer 2

One example is the ring game, which is defined here - in essence, the game (or a slight variant thereon) can be described as:

Start with a Noetherian ring $R$. At each turn, replace $R$ with a quotient thereof. If a player can make no legal moves (i.e. $R$ is a field, thus has no proper quotients).

One can notice that if we play this on $\mathbb Z$, then this is equivalent to the game $*\omega$, since the first move takes it to $\mathbb Z/n\mathbb Z$ which is clearly equivalent to $*k$ where $k$ is the number of (not necessarily distinct) prime factors of $n$. However, as evidenced by certain unanswered questions, the structure of the game can get fairly complicated when we consider more complicated rings. One could generalize to replace "ring" with any algebraic structure they desire - like one could play on groups with no infinite ascending chains of normal subgroups.

Answer 3

Higman's game$^*$

Using finite words on a fixed finite alphabet, two players take turns, in each turn specifying a word that contains no already-specified word as a subsequence. The game terminates when a player (declared the loser) is unable to specify a word, and the other player is declared the winner.

By Higman's Lemma, every such game must eventually terminate; nevertheless, the playing time is arbitrarily large, depending on the initial words chosen.

$^*$ I'm making up the name and the game. Similar games with much longer finite potential playing times could involve specifying trees or graphs (instead of words) that avoid homeopmorphic embeddings, and appealing to Kruskal's Tree Theorem or to the Robertson-Seymour Theorem for proof of termination. These are all examples of the following generalization:

WQO games

More generally, suppose $(X,\le)$ is any well-quasi-order (WQO). Now if players take turns specifying elements of $X$, then eventually one of the players cannot avoid specifying an element $x_j$ such that $x_i\le x_j$ for some already-specified element $x_i$ (i.e., $i<j$), thus terminating the game. The playing time is always finite but arbitrarily large, depending on the initially-chosen elements.

Answer 4

The Hydra problem can be converted in a game with several players. The first player chooses the hydra. Players take turns cutting heads.

Answer 5

Entrepreneurial Chess (Echess). A game of Echess position begins with a Black king vs. a White king and a White rook on a quarter-infinite board, spanning the first quadrant of the xy-plane. In addition to the normal chess moves, Black is given the additional option of “cashing out”, which removes the board and converts the position into the integer x+y, where [x, y] are the coordinates of his king’s position when he decides to cash out.

For each starting position, the game would only last for a finite number of times if both sides play perfectly. In fact white will always win if black does not cash out. But as the starting positions vary, the play time can become arbitrarily long.

References to Echess if you want to know more:

• Entrepreneurial Chess by Elwyn Berlekamp and Richard M. Low
• King and rook vs. king on a quarter-infinite board by Richard M. Low and Mark Stamp