Disjunctive sum

From Wikipedia, the free 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 games and which led to the field of combinatorial game theory for partisan games.

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 games 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 Abelian monoid with only one nontrivial invertible element, called star (*), of order two.