In
combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the playe ...
, 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.
Some loopy games with combinatorial game theory notation include:
* dud: ("deathless universal draw")
* on:
* 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
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...
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
*
Checkers
Checkers (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers ...
*
Fox and Geese
Fox games are a category of asymmetric board games for two players, where one player is the fox and tries to eat the geese / sheep, and the opposing player directs the geese/sheep and attempts to trap the fox, or reach a destination on the board. I ...
References
Combinatorial game theory
{{improve categories, date=January 2025