Combinatorial game theory

Combinatorial game theory is a branch of mathematics founded by John Horton Conway around 1970 , which deals with a special class of two-person games .

The characteristics of these games, also known as combinatorial games , are:

• No coincidence .
• There is no hidden information for a single player (as with playing cards ). ie there is perfect information .
• It is drawn alternately.
• The player who manages to make the last move wins.
• Each game ends after a finite number of moves.

Such games, to which Nim and (after minor rule transformations) Go and Chess belong, open up interesting possibilities for mathematical analysis especially when they break down into components in which there is no mutual influence of the possible moves. Examples are nim heaps and some late endgame positions in go; Even in chess, some forced move positions in pawn endings can be interpreted in this way. The assembly of positions is also known as addition.

The mathematical meaning of combinatorial game theory results from the fact that the games of a subclass can be interpreted as numbers . It is possible to construct whole as well as real and even transfinite (i.e. infinitely large and infinitely small) numbers, the entirety of which is also called surreal numbers . Conversely, the games of combinatorial game theory appear as a generalization of surreal numbers .

Example: domineering

The game domineering is one of the games that can be dealt with in the context of combinatorial game theory. It is intended to serve as an illustration and provide concrete examples.

Rules of the game

In domineering, two players take turns placing dominoes on a chessboard-like playing field , with one stone covering exactly two fields that both must be free when placing. As is common in combinatorial game theory, the two players are referred to as left and right . The player on the left always places the dominoes shown in blue in the following figures vertically and the player on the right always places his stones shown in red horizontally on the board. As with all games of combinatorial game theory, the player who can no longer draw loses the game.

If you want to analyze a position, it obviously only depends on the number of empty fields, but not how the fields that are already occupied have been covered.

Sample game

A game on a 3 × 3 board could e.g. B. run as shown in the following figure: Links opened by placing the stone marked with "1". On the right, place the stone marked with a “2”, whereupon the game on the left decides the game by placing the stone marked with a “3”, because the right then no longer has space for a red stone to be placed horizontally.

A. B. C. D. E. F. G H I.

→

2 3 D. 1 G I.

Regarding the game given as an example, it remains to be noted that Links would even have had a possibility to move in the end position reached with the third move. In addition, the number of free fields, which determines all further possible moves, can be broken down into components, provided that these components are not connected by the side edges of fields. For example, the end position could be the decomposition

D. G

I.

be made. This possibility of decomposing a position or the reverse process of juxtaposing positions is a very important property of combinatorial games (see sum of games ).

Mathematical formalization

For a mathematical modeling , every possible game rule within combinatorial game theory is described by mathematical objects , namely in particular by sets . For this purpose, the moves of the two players must be mathematically and formally characterized for each position.

This characterization of the possible moves could be represented especially in the game domineering for each position by the amount of free fields. General, d. H. for any combinatorial game, the possible moves of a position can be characterized by two sets and , each of which contains the positions that the player in question can reach by moving. In the sense of the mathematical model, each position becomes a combinatorial game, which is defined recursively by those games that start with the positions that can be reached by a train. ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {R}}}$

General notation

The notation has changed from z. B. naturalized for the couple if the player on the left has the two options to move to and only the option to move to the right : ${\displaystyle \{L_{1},L_{2}\,|R_{1}\}}$ ${\displaystyle (\{L_{1},L_{2}\},\{R_{1}\})}$ ${\displaystyle L_{1},L_{2}}$ ${\displaystyle R_{1}}$

A. B. C. D.

${\displaystyle ={\Bigg \{}}$

C. D.

${\displaystyle ,}$

A. D.

${\displaystyle {\Bigg |}}$

A. B.

${\displaystyle {\Bigg \}}}$

Based on this notation and the respective identification of a position with the game that starts from this position, one arrives at the following definition

Definition of a game

A game (in the sense of playing position ., Eng game ) is the following self-referential defined structure:

Construction rule

If and are two sets of games , then there is a game . ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle \{{\mathcal {L}}|{\mathcal {R}}\}}$

The quantities and are also called the left and right options of the game and represent the game positions that the left or right player can reach with one move from the current game position. ${\displaystyle {\mathcal {L}}=\{L_{1},L_{2},...\}}$ ${\displaystyle {\mathcal {R}}=\{R_{1},R_{2},...\}}$

As already explained for the initial example, to shorten the notation, the options are usually listed directly and the quantity brackets are omitted:

${\displaystyle \{{\mathcal {L}}|{\mathcal {R}}\}=\{L_{1},L_{2},...|R_{1},R_{2},...\}}$

Elementary games

The foundation of this recursive definition is game 0, in which neither player can move anymore (the set of left and right options is empty). The corresponding position in domineering is the 1x1 “board”.

A.

${\displaystyle 0:=\{|\}}$

The next step is to find more games:

A. B.		A. B.		A. B. C.
${\displaystyle 1:=\{0|\}}$		${\displaystyle -1:=\{|0\}}$		${\displaystyle *:=\{0|0\}}$

Prize tiers

With regard to the profit prospects that can be achieved with good strategies, each position belongs to exactly one of the following four classes:

• Links can win with optimal play, regardless of who starts ( positive )
• Right can win the game regardless of who starts ( negative )
• The player making the first move has a winning strategy ( fuzzy )
• The following player has a winning strategy ( zero )

		Left begins
		Left wins	Right wins
Right begins	Left wins	Positive (left always wins)	Zero (the player following wins)
	Right wins	Fuzzy (the attractive one wins)	Negative (right always wins)

The elementary games already defined can be classified as follows: 1 is positive, −1 is negative, 0 is a zero game and * is fuzzy.

Many of the games examined break down in the course of the game into independent individual components (endgames in Go, rows in Nim). These sub-games are often simple enough to be fully analyzed. Therefore, a central question of combinatorial game theory is how the winning prospects of the overall game can be derived from the information on the partial games. The temperature theory provides an algorithm with which one can play approximately optimally. The maximum deviation from the theoretically best strategy can be limited.

In some cases you can already draw conclusions from the prize categories:

• If the two components of a game are positive, the entire game is positive. The same goes for negative games.
• Null games have the property that as a component they have no influence on the outcome of the game and leave the prize category unchanged. Two games that differ by only one zero game are therefore considered equivalent.

Sum of games

The sum of two games is a central concept of combinatorial game theory, with which the juxtaposition of positions known from the Nim is formalized and generalized: A Nim position consists of several piles of game pieces, and with each move exactly one pile is selected where the current one Train is carried out. The move options only depend on the selected pile. In addition, each move leaves the unselected piles unchanged.

Similarly, one can together two games by adding that they are next to each other and the sets of moves defined such that the moving player select one of the two terms has to be there to perform a permissible train. In particular, a player who cannot move in any of the summands has no more opportunity to move, so that he has lost.

Formally it is the sum of the games and recursively defined as ${\displaystyle G=\{L_{1},L_{2},...|R_{1},R_{2},...\}}$ ${\displaystyle {\widehat {G}}=\{{\widehat {L}}_{1},{\widehat {L}}_{2},...|{\widehat {R}}_{1},{\widehat {R}}_{2},...\}}$

${\displaystyle G+{\widehat {G}}:=\{L_{1}+{\widehat {G}},L_{2}+{\widehat {G}},...,G+{\widehat {L}}_{1},G+{\widehat {L}}_{2},...|R_{1}+{\widehat {G}},R_{2}+{\widehat {G}},...,G+{\widehat {R}}_{1},G+{\widehat {R}}_{2},...\}}$

Comparison of two games

In order to be able to compare two games G and H with one another, the prize class of the difference game is determined . The inverse corresponds to a reversal of the roles of left and right. In domineering, this can be achieved by turning the board 90 degrees. Is formal ${\displaystyle G-H=G+(-H)}$ ${\displaystyle -H}$

${\displaystyle -\{L_{1},L_{2},...|R_{1},R_{2},...\}:=\{-R_{1},-R_{2},...|-L_{1},-L_{2},...\}}$

This definition is also recursive.

If the difference game is two games and a zero game, the total has the same prize class as the total for each game . Therefore, and are considered equivalent. Under identification of equivalence class and representative one writes: ${\displaystyle G_{1}-G_{2}}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle H}$ ${\displaystyle G_{1}+H}$ ${\displaystyle G_{2}+H}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

${\displaystyle G_{1}=G_{2}}$if it is a null game. ${\displaystyle G_{1}-G_{2}}$

The following is also defined:

${\displaystyle G>H}$if is positive. ${\displaystyle G-H}$

${\displaystyle G<H}$if is negative. ${\displaystyle G-H}$

${\displaystyle G\parallel H}$if is fuzzy. ${\displaystyle G-H}$

such as

${\displaystyle G\geq H}$if or ${\displaystyle G>H}$ ${\displaystyle G=H}$

${\displaystyle G\leq H}$if or ${\displaystyle G<H}$ ${\displaystyle G=H}$

According to this symbolism, a "bigger" game is always advantageous for the left player.

Alternatively, the order relations can also be introduced in a more formal way, without reference to the concept of the optimal style of play, which is not detailed.

With these operators and relations, the games (modulo equivalence) fulfill the properties of a commutative group with partial order . Strictly speaking, the totality of all games can not be a group as a real class , since the definition of a group only extends to sets. However, essential relationships that can be derived from the group property in the case of sets can also be transferred to classes.

Simplification of games and normal form

A game can be simplified with the following two rules without changing the value of the game (i.e. without leaving the equivalence class).

Dominated options

Are two left options comparable in the game , e.g. B. So is a dominated option. Correspondingly, a right option is dominated by, if . ${\displaystyle \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$ ${\displaystyle L_{1}\leq L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle R_{1}\geq R_{2}}$

Dominated options can be left out without changing the value of a game:

${\displaystyle L_{1}\leq L_{2}\Rightarrow \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}=\{L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$

${\displaystyle R_{1}\geq R_{2}\Rightarrow \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}=\{L_{1},L_{2},L_{3},...|R_{2},R_{3},...\}}$

Seen clearly, this corresponds to a game situation in which a player has a move that is clearly worse than an alternative move. Under no circumstances will the player choose the worse move - so it makes no difference to the outcome of the game whether the bad move exists or not.

Reversible trains

In a game , the right player's move to is called reversible if there is a left option of with . Ie is at least as good as the original position for links. (Similarly, a move by the left player to is reversible if there is a right option of with .) ${\displaystyle G=\{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{1}^{L}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{1}^{L}\geq G}$ ${\displaystyle R_{1}^{L}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{1}^{R}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{1}^{R}\leq G}$

For a reversible move, the value of the game does not change if one assumes that the move is always answered immediately by the opponent: ${\displaystyle G}$

Is in the game the right option on reversible so true ${\displaystyle \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{1}^{L}=\{...|K_{1},K_{2},...\}}$

${\displaystyle \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}=\{L_{1},L_{2},L_{3},...|K_{1},K_{2},...,R_{2},R_{3},...\}}$.

If the left option is reversible via , then applies ${\displaystyle L_{1}}$ ${\displaystyle L_{1}^{R}=\{K_{1},K_{2},...|...\}}$

${\displaystyle \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}=\{K_{1},K_{2},...,L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$.

Reversible moves can make sense. The player should continue to play in this partial position after the reversal, otherwise the exchange would be a pure loss.

For finite games (those that contain a finite number of positions) a repeated application of these two rules leads to the normal form of the game, which is unique for each equivalence class.

In the general case, the following statement can at least make: Have two games and neither dominated options, yet reversible trains, it follows from that and have the same left and right options. Ie for every left / right option of there is a left / right option of with . ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G=H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle B}$ ${\displaystyle H}$ ${\displaystyle A=B}$

Examples of higher level games

Four fields can be used to form games of the next level in domineering:

A. B. C. D.

${\displaystyle ={\Bigg \{}}$

A. D.

${\displaystyle ,}$

C. D.

${\displaystyle {\Bigg |}\;{\Bigg \}}={\Bigg \{}}$

A.

${\displaystyle +}$

D.

${\displaystyle ,}$

C. D.

${\displaystyle {\Bigg |}\;{\Bigg \}}=\{0+0,1|\}=\{0,1|\}=\{1|\}}$

(The last simplification can be made because and thus is a dominated option.) ${\displaystyle 0\leq 1}$ ${\displaystyle 0}$

On the other hand is too

${\displaystyle 1+1=\{0|\}+\{0|\}=\{0+1,1+0|\}=\{1|\}}$

One defines

${\displaystyle 2:=\{1|\}}$

${\displaystyle 3:=\{2|\}}$

${\displaystyle 4:=\{3|\}}$, etc.

d. H.

${\displaystyle -2=\{|{-1}\}}$

${\displaystyle -3=\{|{-2}\}}$, etc.

The games can be interpreted as a kind of score: The left or right player has not only won, but could even make a certain number of further moves. In addition to the integer games, there are also those that can be interpreted as a score : ${\displaystyle ...,-2,-1,0,1,2,...}$ ${\textstyle {\frac {1}{2}}}$

A. B. C. D.

${\displaystyle ={\Bigg \{}}$

C. D.

${\displaystyle ,}$

A. D.

${\displaystyle {\Bigg |}}$

A. B.

${\displaystyle {\Bigg \}}={\Bigg \{}}$

C. D.

${\displaystyle ,}$

A.

${\displaystyle +}$

D.

${\displaystyle {\Bigg |}}$

A. B.

${\displaystyle {\Bigg \}}=\{-1,0|1\}=\{0|1\}}$

One defines

${\displaystyle \textstyle {\frac {1}{2}}:=\{0|1\}}$.

This assignment is motivated by the following properties:

${\displaystyle 0<\textstyle {\frac {1}{2}}<1}$

${\displaystyle \textstyle {\frac {1}{2}}+\textstyle {\frac {1}{2}}=1}$,

where the second relationship can be calculated as follows:

${\displaystyle \textstyle {\frac {1}{2}}-1=\{0|1\}+\{|0\}=\{-1|1-1,\textstyle {\frac {1}{2}}\}=\{-1|0,\textstyle {\frac {1}{2}}\}=\{-1|0\}=-\textstyle {\frac {1}{2}}}$.

Furthermore, there are also games that do not behave like a played out score. They are "hot" in the sense that any player can improve their situation by moving in the appropriate position:

A. B. C. D.

${\displaystyle ={\Bigg \{}}$

C. D.

${\displaystyle {\Bigg |}}$

A. D.

${\displaystyle {\Bigg \}}={\Bigg \{}}$

C. D.

${\displaystyle {\Bigg |}}$

A.

${\displaystyle +}$

D.

${\displaystyle {\Bigg \}}=\{1|0\}}$

On average has the same value as : ${\displaystyle \{1|0\}}$ ${\displaystyle \textstyle {\frac {1}{2}}}$

${\displaystyle \{1|0\}+\{1|0\}=1}$

In contrast to , however, it cannot be classified precisely, but is fuzzy compared to values ​​in the defined interval: ${\displaystyle \textstyle {\frac {1}{2}}}$ ${\displaystyle \{1|0\}}$

${\displaystyle \{1|0\}>-1,\quad \{1|0\}\parallel 0,\quad \{1|0\}\parallel \textstyle {\frac {1}{2}},\quad \quad \{1|0\}\parallel 1,\quad \{1|0\}<2}$

The number line can therefore only be located in the range from 0 to 1 indefinitely. ${\displaystyle \{1|0\}}$

Surreal numbers

Among the games there are those that can be identified with real numbers because they follow the same arithmetic. More precisely, the games called surreal numbers can be characterized as follows:

A surreal number is a game where ${\displaystyle n=\{l_{1},l_{2},...|r_{1},r_{2},...\}}$

• all left and right options are surreal numbers
• ${\displaystyle l_{i}<r_{j}}$applies to every left option and right option . ${\displaystyle l_{i}}$ ${\displaystyle r_{j}}$

In the context of combinatorial game theory surreal numbers are also abbreviated number (Engl. Number ), respectively. Of the games already defined, and are numbers, but not and . ${\displaystyle ...,-2,-1,0,1,2,...}$ ${\displaystyle \textstyle {\frac {1}{2}}}$ ${\displaystyle *}$ ${\displaystyle \{1|0\}}$

Numbers are characterized by the fact that they are totally ordered, i. H. for two numbers and either , or . Surreal numbers are a rich class with the properties of an ordered field , which not only contains the whole, rational and real numbers, but also has infinitesimal and infinite representatives. More on this in the main article on surreal numbers . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x<y}$ ${\displaystyle x>y}$ ${\displaystyle x=y}$

As a component in a game sum, numbers can be very easily classified strategically according to the following sentence:

Number Avoidance Sentence

If there is a surreal number and a game, but not a surreal number, in a sums game it is always an advantage to draw in the game if possible. ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle n+G}$ ${\displaystyle G}$

In other words, in a game made up of several components, players only draw in one component until a number (practically a final score) is reached. At the end, the remaining numbers are added up: If the sum is positive, left wins, if it is negative, right wins; if it is 0, the player who follows wins.

A direct consequence of the theorem is the following calculation rule:

Translation principle

If a number and not a number, then applies ${\displaystyle n}$ ${\displaystyle G=\{L_{1},L_{2},...|R_{1},R_{2},...\}}$

${\displaystyle \{L_{1},L_{2},...|R_{1},R_{2},...\}+n=\{L_{1}+n,L_{2}+n,...|R_{1}+n,R_{2}+n,...\}}$.

It is assumed here that there is at least one left or right option. Then follows the identity, since the remaining options of the sum are dominated by the number-avoidance theorem. ${\displaystyle G}$

Special case: neutral games

Games in which, in addition to the properties listed above, the options for moves are always identical for both players are called neutral games (the original English term impartial is sometimes also translated as objective ). In terms of profit prospects, each position in a neutral game belongs to one of the first two classes on the list above.

A complete analysis of a neutral game is always possible by assigning to each position an equivalent position of the normal Nim game consisting of just one pile . This possibility of reduction was found independently by Roland Sprague in 1935 and by Patrick Michael Grundy in 1940 and is therefore also known as the Sprague-Grundy theorem. The world chess champion and mathematician Emanuel Lasker had already discussed approaches to reduction .

The size of the Nim heap, which is assigned to a position of a neutral game, is also known as its Grundy number. The Grundy number of a position can be relatively easily recursive, i.e. H. from the Grundy numbers of the positions that can be reached in one move: It is equal to the smallest natural number that is not the Grundy number of a successor position.

Grundy numbers have the following two properties:

• The attractive player has a winning strategy if and only if the Grundy number is not equal to 0.
• The Grundy number of a sum, i.e. H. a position composed of components is equal to the XOR sum of the Grundy numbers of its components, which simplifies the calculation in such cases in terms of complexity .

The two properties generalize the winning strategy found in 1901 by Charles Leonard Bouton for the Nim game , according to which one should always draw so that the XOR sum of the pile sizes is equal to 0.

Application: Endgames at Go

Even if Go is actually not a game in which the last player to draw wins, games can be constructed in the sense of combinatorial game theory, which reproduce the usual Go rules and effectively lead to the same game result. The easiest way to do this is with the historical stone evaluation , in which both players fill the board with stones (except for two eyes per living group) and the player with the most stones on the board is declared the winner. With the additional rule of returning prisoners , the winner is also the person who can move last. Returning prisoners means that the players are not allowed to pass, but instead of taking a regular move they can return a previously caught stone to the opponent (the stone is thus out of the game).

The stone rating differs from the go rules that are common worldwide today in that a “tax” of two points is levied on each group. But the modern rule variants can also be mapped accordingly.

In addition to the conventions of classic combinatorial game theory according to John Conway, there are also alternative formalisms in which the scores and their properties in relation to the components of an (endgame) position are examined directly. This is pursued in the works from the 1950s by Milnor (1953), Hanner (1959), which already contain essential results from temperature theory, and continued by Berlekamp (1996).

In the book Mathematical Go (1994) by Berlekamp and Wolfe, the results of combinatorial game theory are applied to endgames in Go and the resulting game strategies are worked out. It contains findings and guidelines that were not previously part of the canon of knowledge of professional players and is considered one of the few Go publications by western authors who have received attention in Asia.

Remarks

1. ↑ Proof : Let be a zero game and a game for which player A has a winning strategy. This player then also has a winning strategy for the composite game : For every move that the opponent makes, player A replies with the winning strategy of the player who followed. Otherwise he draws in , according to his winning strategy for . ${\displaystyle N}$ ${\displaystyle G}$ ${\displaystyle N+G}$ ${\displaystyle N}$ ${\displaystyle G}$ ${\displaystyle G}$
2. ↑ To this end, the following is defined:
   • ${\displaystyle G\geq H:\Leftrightarrow }$no right option of exists with and no left option of exists with ${\displaystyle G^{R}}$ ${\displaystyle G}$ ${\displaystyle H\geq G^{R}}$ ${\displaystyle H^{L}}$ ${\displaystyle H}$ ${\displaystyle H^{L}\geq G}$
   such as
   • ${\displaystyle G\leq H:\Leftrightarrow H\geq G}$
   • ${\displaystyle G=H:\Leftrightarrow }$( and ) ${\displaystyle G\leq H}$ ${\displaystyle H\leq G}$
   • ${\displaystyle G>H:\Leftrightarrow }$( and not ) ${\displaystyle G\geq H}$ ${\displaystyle G=H}$
   • ${\displaystyle G<H:\Leftrightarrow H>G}$
   • ${\displaystyle G\parallel H:\Leftrightarrow }$(neither nor ) ${\displaystyle G\leq H}$ ${\displaystyle H\leq G}$
   This recursive definition is consistent with the principle of the optimal style of play, because the following statements are equivalent for a game : ${\displaystyle G}$
   • ${\displaystyle G}$ is positive or zero
   • When the right begins, the left can win
   • Right has no "winning move"
   • There is no right option of for which the following applies: if left begins, right can win. ${\displaystyle G^{R}}$ ${\displaystyle G}$
   • There is no right option of being negative or zero ${\displaystyle G^{R}}$ ${\displaystyle G}$
   Ie symbolically no right option of exists with . ${\displaystyle G\geq 0\Leftrightarrow }$ ${\displaystyle G^{R}}$ ${\displaystyle G}$ ${\displaystyle G^{R}\leq 0}$

See also

• Game theory

literature

• John Horton Conway : About Numbers and Games . Braunschweig, 1983, ISBN 3-528-08434-0 , doi: 10.1007 / 978-3-322-88997-3 .
• Elwyn R. Berlekamp , John H. Conway , Richard K. Guy : Winning. Strategies for Math Games . Braunschweig, 1985/86, 4 volumes:
  • Volume 1, Von der Pike auf , ISBN 3-528-08531-2 , doi: 10.1007 / 978-3-322-83170-5 ;
  • Volume 2, little tree-change-yourself , ISBN 3-528-08532-0 , doi: 10.1007 / 978-3-322-83171-2 ;
  • Volume 3, Case Studies , ISBN 3-528-08533-9 , doi: 10.1007 / 978-3-322-83172-9 ;
  • Volume 4, Solitaire games , ISBN 3-528-08534-7 , doi: 10.1007 / 978-3-322-83173-6 .
• Elwyn R. Berlekamp , David Wolfe: Mathematical Go, Chilling Gets the Last Point . 1994, ISBN 1-56881-032-6
• Jörg Bewersdorff : Luck, Logic and Bluff: Mathematics in Play - Methods, Results and Limits , Springer Spectrum , 7th edition 2018, ISBN 978-3-658-21764-8 , doi: 10.1007 / 978-3-658-21765- 5 (Chapters 2.4 to 2.9).
• Aaron N. Siegel: Combinatorial Game Theory , Graduate Studies in Mathematics, Volume 146, American Mathematical Society 2013, ISBN 978-0-8218-5190-6 , doi: 10.1090 / gsm / 146
• Richard J. Nowakowski: The History of Combinatorial Game Theory , Proceedings of the Board Game Studies Colloquium XI, Lisbon, 2008, online ( Memento from May 31, 2014 in the Internet Archive )

Web links

• Go and math

Individual evidence

1. ^ R. Sprague: About mathematical fighting games , Tôhoku Mathematical Journal, 41 (1935), pp. 438-444 ( online version ).
2. ^ PM Grundy: Mathematics and games , Eureka. 27 (1940), pp. 9-11 ( online version ( Memento of September 27, 2007 in the Internet Archive )).
3. ↑ Emanuel Lasker: Board games of the peoples. Berlin 1931, p. 177 ff.
4. ↑ Quoted in excerpts in: Jörg Bewersdorff: Glück, Logic and Bluff: Mathematics in the game - methods, results and limits , 5th edition, Wiesbaden 2010, pp. 119–121
5. ↑ CL Bouton: Nim, a game with a complete mathematical theory , Annals of Mathematics, (2) 3 (1901), pp. 35–39 ( online at JSTOR )
6. ↑ Elwyn Berlekamp: Introductory overview of mathematical Go endgames , Combinatorial games, Lecture Notes AMS Short Course, Columbus / OH (USA) 1990, pp. 73-100 ( abstract in Zentralblatt MATH )
7. ↑ John W. Milnor: Sums of positional games , Contrib. Theory of Games, II, Ann. Math. Stud., 28 (1953), pp. 291–301, doi : 10.1515 / 9781400881970-017 ( abstract in Zentralblatt MATH )
8. ↑ Olof Hanner: Mean play of sums of positional games , Pacific Journal of Mathematics, 9 (1959), pp. 81-99 ( online version ).
9. ↑ Elwyn Berlekamp: The economist's view of combinatorial games , Games of No Chance, 1996, pp. 365-405 ( online version )