In the mathematics of combinatorial games, the sum or 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. The sum game finishes when there are no moves left in either of the two parallel games, at which point (in normal play) the last player to move wins. This operation may be extended to disjunctive sums of any number of games, again by playing the games in parallel and moving in exactly one of the games per turn. It is the fundamental operation that is used in the

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 one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as ...

for

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. In other words, the only difference betw ...

s and which led to the field of

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 players ...

for

partisan game In combinatorial game theory, a game is partisan (sometimes 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 ...

Application to common games

Disjunctive sums arise 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 Domineering (also called Stop-Gate or Crosscram) is a mathematical game that can be played on any collection of squares on a sheet of graph paper. For example, it can be played on a 6×6 square, a rectangle, an entirely irregular polyomino, or a ...

, the

Game of the Amazons The Game of the Amazons (in Spanish, ''El Juego de las Amazonas;'' often called Amazons for short) is a two-player abstract strategy game invented in 1988 by Walter Zamkauskas of Argentina.. The game is played by moving pieces and blocking the o ...

, and the

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 ...

. In such games, each component may be analyzed separately for simplifications that do not affect its outcome or the outcome of its disjunctive sum with other games. Once this analysis has been performed, the components can be combined by taking the disjunctive sum of two games at a time, combining them into a single game with the same outcome as the original game.

Mathematics

The sum operation was formalized by . It is a

commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...

and

associative operation In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...

: if two games are combined, the outcome is the same regardless of what order they are combined, and if more than two games are combined, the outcome is the same regardless of how they are grouped. The negation −''G'' of a game ''G'' (the game formed by trading the roles of the two players) forms an

additive inverse In mathematics, the additive inverse of a number is the number that, when added to , yields zero. This number is also known as the opposite (number), sign change, and negation. For a real number, it reverses its sign: the additive inverse (opp ...

under disjunctive sums: the game ''G'' + −''G'' is a zero game (won by whomever goes second) using a simple echoing strategy in which the second player repeatedly copies the first player's move in the other game. For any two games ''G'' and ''H'', the game ''H'' + ''G'' + −''G'' has the same outcome as ''H'' itself (although it may have a larger set of available moves). Based on these properties, the class of combinatorial games may be thought of as having the structure of an

abelian group In mathematics, 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 the order in which they are written. That is, the group operation is commut ...

, although with a

proper class Proper may refer to: Mathematics * Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact * Proper morphism, in algebraic geometry, an analogue of a proper map for ...

of elements rather than (as is more standard for groups) a set of elements. For an important subclass of the games called the

surreal number In mathematics, the surreal number system is a totally ordered proper class containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number. The surreals ...

s, there exists a multiplication operator that extends this group to a

field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...

. For impartial

misère Misère ( French for "destitution"), misere, bettel, betl, or (German for "beggar"; equivalent terms in other languages include , , ) is a bid in various card games, and the player who bids misère undertakes to win no tricks or as few as possi ...

play games, an analogous theory of sums can be developed, but with fewer of these properties: these games form a

monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids ...

with only one nontrivial invertible element, called

star A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...

( *), of order two.

References

*. {{DEFAULTSORT:Disjunctive Sum Combinatorial game theory