Mathematicians playing Konane at a Combinatorial game theory workshop (for technical content, see external link)

This article is on the theory of combinatorial games. For the theory that includes games of chance and games of imperfect knowledge, see Game theory

Combinatorial game theory (CGT) is a mathematical theory that only studies two-player games which have a position which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT does not study games of chance (like poker), but restricts itself to games whose position is public to both players, and in which the set of available moves is also public. CGT principles can be applied to games like chess, checkers, Go, Hex, and Connect6 but these games are mostly too complicated to allow complete analysis (although the theory has had some recent successes in analyzing Go endgames). Image File history File linksMetadata Size of this preview: 800 × 531 pixel Image in higher resolution (1280 × 850 pixel, file size: 178 KB, MIME type: image/jpeg) File links The following pages on the English Wikipedia link to this file (pages on other projects are not listed): Combinatorial game theory... Image File history File linksMetadata Size of this preview: 800 × 531 pixel Image in higher resolution (1280 × 850 pixel, file size: 178 KB, MIME type: image/jpeg) File links The following pages on the English Wikipedia link to this file (pages on other projects are not listed): Combinatorial game theory... Mathematicians playing Konane at a Combinatorial game theory workshop (for technical content, see external link) This article is on the theory of combinatorial games. ... Game theory is often described as a branch of applied mathematics and economics that studies situations where players choose different actions in an attempt to maximize their returns. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... The word theory has a number of distinct meanings in different fields of knowledge, depending on their methodologies and the context of discussion. ... Tug of war is an easily organized, impromptu game that requires little equipment. ... A game of chance is a game whose outcome is strongly influenced by some randomizing device, and upon which contestants frequently wager money. ... A game of Texas holdem, the most popular form of poker, in progress. ... Chess is a recreational and competitive game for two players. ... starting position on a 10×10 draughts board Draughts, also known as checkers, is a group of mental sport board games between two players which involve diagonal moves of uniform pieces and mandatory captures by jumping over the enemys pieces. ... Go is a strategic board game for two players. ... Hex is a board game played on a hexagonal grid, usually in the shape of a 10 by 10 or a 11 by 11 rhombus. ... Connect6 (Chinese: 六子棋; Pinyin: liùzǐqí; Japanese: 六目並べ; Korean: 육목) introduced by Professor I-Chen Wu at Department of Computer Science and Information Engineering, National Chiao Tung University, is a fair and highly complex game. ...

Applying CGT to a position attempts to determine the optimum sequence of moves for both players until the game ends, and by doing so discover the optimum move in any position. In practice, this process is tortuously difficult unless the game is very simple.

CGT should not be confused with another mathematical theory, traditionally called game theory, used in the theory of economic competition and cooperation. Game theory includes games of chance, games of imperfect knowledge and games in which players move simultaneously. Game theory is often described as a branch of applied mathematics and economics that studies situations where players choose different actions in an attempt to maximize their returns. ...

History

CGT arose in relation to the theory of impartial games, in which any play available to one player must be available to the other as well. One very important such game is nim, which can be solved completely. Nim is an impartial game for two players, and subject to the normal play condition, which means that a player who cannot move loses. In the 1930s, the Sprague-Grundy theorem showed that all impartial games are equivalent to heaps in nim, thus showing that major unifications are possible in games considered at a combinatorial level (in which detailed strategies matter, not just pay-offs). 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. ... Nim is a two-player mathematical game of strategy in which players take turns removing objects from distinct heaps. ... 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. ... The 1930s (years from 1930–1939) were described as an abrupt shift to more radical and conservative lifestyles, as countries were struggling to find a solution to the Great Depression, also known in Europe as the World Depression. ... In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game is equivalent to a nimber. ... Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. ...

In the 1960s, Elwyn R. Berlekamp, John H. Conway and Richard K. Guy jointly introduced the theory of partizan games, in which the requirement that a play available to one player be available to both is relaxed. Their results were published in their book Winning Ways for your Mathematical Plays in 1982. However, the first book published on the subject was Conway's On Numbers and Games, also known as ONAG, which introduced the concept of surreal numbers and the generalization to games. On Numbers and Games was also a fruit of the collaboration between Berlekamp, Conway, and Guy. The 1960s decade refers to the years from January 1, 1960 to December 31, 1969, inclusive. ... Elwyn Ralph Berlekamp is professor of mathematics at University of California, Berkeley. ... John Horton Conway (born December 26, 1937, Liverpool, England) is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. ... Richard Kenneth Guy (born 1916) is a Professor Emeritus in the Department of Mathematics at the University of Calgary. ... Winning Ways for your Mathematical Plays (ISBN 1568811306) by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy is a compendium of information on mathematical games. ... On Numbers and Games is a mathematics book by John Horton Conway. ... In mathematics, the surreal numbers are a field containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number, and therefore the surreals are algebraically similar to superreal numbers and hyperreal numbers. ...

John Conway states in ONAG that the inspiration for the theory of partizan games was based on his observation of the play in go endgames. Go is a strategic board game for two players. ...

Examples

The introductory text Winning Ways introduced a large number of games, but the following were used as motivating examples for the introductory theory: Winning Ways for your Mathematical Plays (Academic Press, 1982) by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy is a compendium of information on mathematical games. ...

• Blue-Red Hackenbush - At the finite level, this partisan combinatorial game allows constructions of games whose values are dyadic rational numbers. At the infinite level, it allows one to construct all real values, as well as many infinite ones which fall within the class of surreal numbers.
• Blue-Red-Green Hackenbush - Allows for additional game values that are not numbers in the traditional sense, for example, star.
• Domineering - Various interesting Games, such as hot games, appear in Domineering, due to the fact that there is sometimes an incentive to move, and sometimes not. This allows discussion of a game's temperature.
• Nim - An impartial game. This allows for the construction of the nimbers. (It can also be seen as a green-only special case of Blue-Red-Green Hackenbush.)

The classic game Go was influential on the early combinatorial game theory, and Berlekamp and Wolfe subsequently developed an endgame and temperature theory for it (see references). Armed with this they were able to construct plausible Go endgame positions from which they could give expert Go players a choice of sides and then defeat them either way. Hackenbush is a two-player partisan mathematical game that consists of several colored line segments connected to the ground. ... In mathematics, a dyadic fraction or dyadic rational is a rational number that when written as a vulgar fraction has a denominator that is a power of two, i. ... In mathematics, the surreal numbers are a field containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number, and therefore the surreals are algebraically similiar to superreal numbers and hyperreal numbers. ... Star, written as * or *1, is the value given to the combinatorial game {0 | 0}, where zero is the zero game. ... Domineering is a mathematical game played on a sheet of graph paper, with any set of designs traced out. ... Nim is a two-player mathematical game of strategy in which players take turns removing objects from distinct heaps. ... 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 mathematics, the proper class of nimbers is introduced in combinatorial game theory, where they arise as the sizes of nim heaps. ... Go is a strategic board game for two players. ...

Overview

A game, in its simplest terms, is a list of possible "moves" that two players, called left and right, can make. Every move is in fact, another game, such that each game can be considered a single state that the game can exist in. Image File history File links I created this file for use in the article Combinatorial game theory and release it to the public domain. ...

Each game has the notation {L|R}. L are the games that the left player can move to, and R are the games that the right player can move to. Using Tic-Tac-Toe as an example, if we label each of the nine boxes UL for Upper Left, CC for Center Center, and LR for Lower Right (and so on), and it is possible to put an X or an O in each square, the first game of Tic-Tac-Toe would look like this: Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ...

While choices are given to both left and right, only one player may make a move in any given game, and turns alternate. The game lists valid moves each player could make, if it were that player's turn. For example, the Tic-Tac-Toe game labeled XUL above would be the following: Image File history File links I created this file for use in the article Combinatorial game theory and release it to the public domain. ...

Moving on down the chain, eventually the game might come to this state (a very strange game indeed, but still valid):

The above game describes a scenario in which there is only one move left for either player, which is the Lower Right corner, and if either player makes that move, that player wins. The {|} in each player's move list is called the zero game, and can actually be abbreviated 0. In the zero game, neither player has any valid moves; thus, whoever's turn it is when the zero game comes up automatically loses. Image File history File links I created this file for use in the article Combinatorial game theory and release it to the public domain. ... In combinatorial game theory, the zero game is the game where neither player has any legal options. ...

Additionally, the game which is labeled the rather complex "XUL_OUR_XCC_OCR_XLC_OLL_XCL_OUC" above also has a much simpler notation, and is called the star game, which can also be abbreviated *. In the star game, the only valid move leads to the zero game, which means that whoever's turn comes up during the star game automatically wins. Star, written as * or *1, is the value given to the combinatorial game {0 | 0}, where zero is the zero game. ...

An additional type of game, not found in Tic-Tac-Toe, is a loopy game, in which a valid move of either left or right is a game which can then lead back to the first game. A game that does not possess such moves is called nonloopy.

Formal definitions

A structure is called a collection of games if

and

where is the power set of , In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ...

and

Because G is uniquely determined by L(G) and R(G), G is often denoted .

The elements of are called games and by convention they are denoted by the upper case Latin letters G,H,K,.... A game represents a contest between two players conventionally named Left and Right (sometimes known as bLue and Red), and (respectively ) means that player Left (respectively Right) is allowed to move from game G to game H.

Define the binary relation, (for successor) between games by In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ...

if and only if .

The transitive closure of is denoted , for position. We say H is a position of G, denoted , when it is possible to get from G to H via a nonempty sequence of moves by Left and Right, not necessarily alternating players. is called loopy if ; otherwise is nonloopy. A non-loopy collection is well-founded when there is no infinite sequence with . It has been suggested that this article or section be merged with Logical biconditional. ... In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ...

If there exists an element of , with , then we call it the zero element. The zero element, if it exists, is unique.

If is a collection of games and then the game G₀ can be 'played' as follows. The first player, say Left, chooses an element (if one exists). Then Right chooses an element (if one exists). Then Left chooses an element and so on. If a player cannot move (i.e. the relevant or set is empty) then, by definition, that player loses the game. The game G₀ can similarly be played with Right as the first player by exchanging the roles of and .

Well-founded collections of games

If is well-founded, then it contains a zero element. In mathematics, a well-founded relation is an order relation R on a set X where every non-empty subset of X has an R-minimal element; that is, where for every non-empty subset S of X, there is an element m of S such that for every element...

Let be the smallest well-founded collection of games containing 0 and such that In mathematics, a well-founded relation is an order relation R on a set X where every non-empty subset of X has an R-minimal element; that is, where for every non-empty subset S of X, there is an element m of S such that for every element...

For all well-founded collections , there exists such that .

Then all well-founded collections of games are isomorphic to a subcollection of . We can work solely with . In mathematics, a well-founded relation is an order relation R on a set X where every non-empty subset of X has an R-minimal element; that is, where for every non-empty subset S of X, there is an element m of S such that for every element... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ...

Define a binary operator In mathematics, a binary operation, or binary operator, is a calculation involving two input quantities and one kind of a specific operation. ...

recursively by See: Recursion Recursively enumerable language Recursively enumerable set Recursive filter Recursive function Recursive set Primitive recursive function This is a disambiguation page — a list of pages that otherwise might share the same title. ...

and .

This definition of addition of games (also called the disjunctive sum of the games) is well-defined for well-founded games and it is commutative. Intuitively, one should think of the game G + H as consisting of the two games G and H being played "side by side": Each player in turn may make a move in either G or H, but not both. The analysis of this operator is motivated by games such as Go, Sprouts, and Domineering, which split into parts that are independent except in that a player may move in only one part per turn. In mathematics, the term well-defined is used to specify that a certain concept (a function, a property, a relation, etc. ... In mathematics, a well-founded relation is an order relation R on a set X where every non-empty subset of X has an R-minimal element; that is, where for every non-empty subset S of X, there is an element m of S such that for every element... In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ... Go is a strategic board game for two players. ... Sprouts is a pencil-and-paper game with interesting mathematical properties. ... Domineering is a mathematical game played on a sheet of graph paper, with any set of designs traced out. ...

The negative of a game is defined recursively as follows:

.

This definition is similarly well-defined. Intuitively, − G is just "G with Left and Right reversed".

Define a set of games recursively as follows: In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ...

if and only if .

A player loses precisely when they run out of moves. The above definition characterizes games such that with Left to move, no matter what Left does, Right can respond so that Left will eventually run out of moves. One might call them "Left to play and lose" games. It has been suggested that this article or section be merged with Logical biconditional. ...

One can similarly define P_R, and we note that . Next, define

.

P is the set of second-player-win games (whoever moves first, the second player can force a win). A useful exercise at this point is to show that . This observation motivates the following:

Define a relation by if and only if . This is an equivalence relation; and it respects the addition and negative operations. Therefore, the operations + and - can be defined on the quotient set defined by the equivalence relation . Finally one can show that the addition is an abelian group operation. It has been suggested that this article or section be merged with Logical biconditional. ... In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x in X | x ~ a } The notion of equivalence classes is useful for constructing sets... In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ... In mathematics, an abelian group, also called a commutative group, is a group such that for all a and b in G. In other words, the order of elements in a product doesnt matter. ...

Nimbers

An impartial game is one where, at every position of the game, the same moves are available to both players. For instance, Nim is impartial, as any set of objects that can be removed by one player can be removed by the other. However, Tic-Tac-Toe is not impartial, because a move by one player leaves a different position than a move to the same square by the other player. For any ordinal number, one can define an impartial game generalizing Nim in which, on each move, either player may replace the number with any smaller ordinal number; the games defined in this way are known as nimbers. The Sprague-Grundy theorem states that every impartial game is -equivalent to a nimber. 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. ... Nim is a two-player mathematical game of strategy in which players take turns removing objects from distinct heaps. ... Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ... Ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ... In mathematics, the proper class of nimbers is introduced in combinatorial game theory, where they arise as the sizes of nim heaps. ... In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game is equivalent to a nimber. ...

See also

• Surreal number
• Zero game
• Fuzzy game
• star (game)
• Game complexity
• Connect6
• Go (board game)
• Chess

In mathematics, the surreal numbers are a field containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number, and therefore the surreals are algebraically similar to superreal numbers and hyperreal numbers. ... In combinatorial game theory, the zero game is the game where neither player has any legal options. ... This article may be too technical for most readers to understand. ... Star, written as * or *1, is the value given to the combinatorial game {0 | 0}, where zero is the zero game. ... In combinatorial game theory, game complexity is a measure of the complexity of a game. ... Connect6 (Chinese: 六子棋; Pinyin: liùzǐqí; Japanese: 六目並べ; Korean: 육목) introduced by Professor I-Chen Wu at Department of Computer Science and Information Engineering, National Chiao Tung University, is a fair and highly complex game. ... Go is a strategic board game for two players. ... Chess is a recreational and competitive game for two players. ...

External links

• List of combinatorial game theory links at the homepage of David Eppstein

• An Introduction to Conway's games and numbers by Dierk Schleicher and Michael Stoll

• Combinational Game Theory terms summary by Bill Spight
• Combinatorial Game Theory Workshop, Banff International Research Station, June 1995

David Eppstein is a computer scientist at the Computer Science Department, Donald Bren School of Information and Computer Sciences, University of California, Irvine. ...

References

• John Horton Conway (1976). On Numbers And Games. Academic Press. ISBN 0-12-186350-6. 
  • --- (2001). On Numbers And Games (2nd ed.). A K Peters Ltd. ISBN 1-56881-127-6. 
• E. Berlekamp, J. H. Conway, R. Guy (1982). Winning Ways for your Mathematical Plays. Academic Press. ISBN 0-12-091101-9, ISBN 0-12-091102-7. 
  • --- (2001--2004). Winning Ways for your Mathematical Plays (2nd ed.). A K Peters Ltd. ISBN 1-56881-130-6, ISBN 1-56881-142-X, ISBN 1-56881-143-8, ISBN 1-56881-144-6. 
• Elwyn Berlekamp & David Wolfe (1997). Mathematical Go: Chilling Gets the Last Point. A K Peters Ltd. ISBN 1-56881-032-6. 
• Jorg Bewersdorff (2004). Luck, Logic and White Lies: The Mathematics of Games. A K Peters Ltd. ISBN 1-56881-210-8, §§ 21-26.