Disjunctive sum
Encyclopedia
The disjunctive sum of two games
is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn. This is extended to disjunctive sums of any number of games by associativity
, which results in allowing each player to move in just one of the games per turn.
This is the fundamental operation that is used in the Sprague–Grundy theorem
for impartial game
s and which led to the field of combinatorial game theory
for partisan game
s.
The importance of disjunctive sums arises in games that naturally break up into components or regions that do not interact except in that each player in turn must choose just one component to play in. Examples of such games are Go
, Nim
, Sprouts
, Domineering
, and the map-coloring games
.
By analyzing each component, it is possible to find simplifications of the component that do not affect its outcome or the outcome of its disjunctive sum with other games. In addition, the components can be combined by taking the disjunctive sum of two games at a time, combining them into a single game.
The disjunctive sum is a fairly well-studied tool for analysis of normal play
games, in which a player who is unable to play loses. Some progress has been made in analyzing impartial game
s in misère
play, where a player unable to play wins.
Mathematically, the disjunctive sum imposes an Abelian group
structure on games, that can be extended to a field
for an important subclass of games called the surreal numbers. Impartial misère
play games form an commutative
monoid
with only one nontrivial invertible element, called star (*), of order two.
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn. This is extended to disjunctive sums of any number of games by associativity
Associativity
In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
, which results in allowing each player to move in just one of the games per turn.
This is the fundamental operation that is used in the Sprague–Grundy theorem
Sprague–Grundy theorem
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to...
for impartial game
Impartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
s and which led to the field of combinatorial game theory
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
for partisan game
Partisan game
In combinatorial game theory, a game is partisan or partizan if it is not impartial. That is, some moves are available to one player and not to the other.Most games are partisan; for example, in chess, only one player can move the white pieces....
s.
The importance of disjunctive sums arises in games that naturally break up into components or regions that do not interact except in that each player in turn must choose just one component to play in. Examples of such games are Go
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
, Nim
Nim
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap....
, Sprouts
Sprouts (game)
Sprouts is a pencil-and-paper game with interesting mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in 1967.- Rules :...
, Domineering
Domineering
Domineering is a mathematical game played on a sheet of graph paper, with any set of designs traced out. For example, it can be played on a 6×6 square, a checkerboard, an entirely irregular polygon, or any combination thereof. Two players have a collection of dominoes which they place on the grid...
, and the map-coloring games
Map-coloring games
Several map-coloring games are studied in combinatorial game theory. The general idea is that we are given a map with regions drawn in but with not all the regions colored. Two players, Left and Right, take turns coloring in one uncolored region per turn, subject to various constraints...
.
By analyzing each component, it is possible to find simplifications of the component that do not affect its outcome or the outcome of its disjunctive sum with other games. In addition, the components can be combined by taking the disjunctive sum of two games at a time, combining them into a single game.
The disjunctive sum is a fairly well-studied tool for analysis of normal play
Misère game
Misere or misère is a bid in various card games, and the player who bids misere undertakes to win no tricks or as few as possible, usually at no trump, in the round to be played...
games, in which a player who is unable to play loses. Some progress has been made in analyzing impartial game
Impartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
s in misère
Misère game
Misere or misère is a bid in various card games, and the player who bids misere undertakes to win no tricks or as few as possible, usually at no trump, in the round to be played...
play, where a player unable to play wins.
Mathematically, the disjunctive sum imposes an Abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
structure on games, that can be extended to a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
for an important subclass of games called the surreal numbers. Impartial misère
Misère game
Misere or misère is a bid in various card games, and the player who bids misere undertakes to win no tricks or as few as possible, usually at no trump, in the round to be played...
play games form an commutative
Commutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
with only one nontrivial invertible element, called star (*), of order two.