In combinatorial game theory, a branch of mathematics, a loopy game is one in which a previous state is reachable from descendent options.

By contrast, a loop-free game is a game where players can never reach previous positions. A loop-free finite game is also called a short game.[1]

Some loopy games with combinatorial game theory notation include:

  • dud: {dud|dud} ("deathless universal draw")
  • on: {on|}
  • off: {|off}

Some interesting properties arise from these definitions. For example, on + off = dud, or dud + G = dud for any game G.

Like transfinite games, the infinite nature of loopy games gives an extra outcome to loopy games: a tie. A player 'survives' a game if they either tie or win.

Impartial loopy games are susceptible to analysis by the generalized Sprague-Grundy theorem.

Definition

A loopy game is a pair G = (V, x), where V is a bipartite graph with named edge-sets (that is, some edges of the bipartite graph are Left, and other edges are Right) and x is the start vertex (initial position) of a game. This labeled bipartite graph is called a bigraph in combinatorial game theory.

  • If V is finite, the game G must be finite.
  • If both edge sets of V are equal, G is impartial.

Stoppers

Stoppers are loopy games that have no subpositions with infinite alternating runs. Unlike generic loopy games, stoppers can never tie.

Examples

References

  1. ^ Siegel, Aaron (20 November 2023). Combinatorial Game Theory. American Mathematical Society. ISBN 978-1-4704-7568-0.
No tags for this post.