# 组合博弈论

，由Steve Luo审校中，给您阅读带来不便，请见谅。

Mathematicians playing Konane at a combinatorial game theory workshop

Mathematicians playing Konane at a combinatorial game theory workshop

Combinatorial game theory (CGT) 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 in which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players.[1] However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing.[2] Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

Combinatorial game theory (CGT) 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 in which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

Combinatorial games include well-known games such as chess, checkers, and Go, which are regarded as non-trivial, and tic-tac-toe, which is considered as trivial in the sense of being "easy to solve". Some combinatorial games may also have an unbounded playing area, such as infinite chess. In CGT, the moves in these and other games are represented as a game tree.

Combinatorial games include well-known games such as chess, checkers, and Go, which are regarded as non-trivial , and tic-tac-toe, which is considered as trivial in the sense of being "easy to solve". Some combinatorial games may also have an unbounded playing area, such as infinite chess. In CGT, the moves in these and other games are represented as a game tree.

Combinatorial games also include one-player combinatorial puzzles such as Sudoku, and no-player automata, such as Conway's Game of Life, (although in the strictest definition, "games" can be said to require more than one participant, thus the designations of "puzzle" and "automata".[3])

Combinatorial games also include one-player combinatorial puzzles such as Sudoku, and no-player automata, such as Conway's Game of Life, (although in the strictest definition, "games" can be said to require more than one participant, thus the designations of "puzzle" and "automata".)

Game theory in general includes games of chance, games of imperfect knowledge, and games in which players can move simultaneously, and they tend to represent real-life decision making situations.

Game theory in general includes games of chance, games of imperfect knowledge, and games in which players can move simultaneously, and they tend to represent real-life decision making situations.

CGT has a different emphasis than "traditional" or "economic" game theory, which was initially developed to study games with simple combinatorial structure, but with elements of chance (although it also considers sequential moves, see extensive-form game). Essentially, CGT has contributed new methods for analyzing game trees, for example using surreal numbers, which are a subclass of all two-player perfect-information games.[3] The type of games studied by CGT is also of interest in artificial intelligence, particularly for automated planning and scheduling. In CGT there has been less emphasis on refining practical search algorithms (such as the alpha–beta pruning heuristic included in most artificial intelligence textbooks), but more emphasis on descriptive theoretical results (such as measures of game complexity or proofs of optimal solution existence without necessarily specifying an algorithm, such as the strategy-stealing argument).

CGT has a different emphasis than "traditional" or "economic" game theory, which was initially developed to study games with simple combinatorial structure, but with elements of chance (although it also considers sequential moves, see extensive-form game). Essentially, CGT has contributed new methods for analyzing game trees, for example using surreal numbers, which are a subclass of all two-player perfect-information games. The type of games studied by CGT is also of interest in artificial intelligence, particularly for automated planning and scheduling. In CGT there has been less emphasis on refining practical search algorithms (such as the alpha–beta pruning heuristic included in most artificial intelligence textbooks), but more emphasis on descriptive theoretical results (such as measures of game complexity or proofs of optimal solution existence without necessarily specifying an algorithm, such as the strategy-stealing argument).

CGT与“传统”或“经济”博弈论的重点不同，后者最初是研究具有简单组合结构但具有机会元素的博弈的（尽管它也考虑了顺序移动，请参阅扩展形式的博弈)。本质上，CGT 提供了分析博弈树的新方法，例如使用超现实数字，它是所有两人完全信息博弈的一个子类。CGT研究的游戏类型在人工智能中也很受关注，特别是在自动计划和调度方面。在CGT中，很少强调改进实用的搜索算法(例如大多数人工智能教科书中包含的 alpha-beta剪枝算法) ，而更多强调描述性的理论结果(例如对策复杂性的度量或最优解存在性的证明，而无需指定算法，例如策略窃取论点)。

An important notion in CGT is that of the solved game. For example, tic-tac-toe is considered a solved game, as it can be proven that any game will result in a draw if both players play optimally. Deriving similar results for games with rich combinatorial structures is difficult. For instance, in 2007 it was announced that checkers has been weakly solved—optimal play by both sides also leads to a draw—but this result was a computer-assisted proof.[4] Other real world games are mostly too complicated to allow complete analysis today, although the theory has had some recent successes in analyzing Go endgames. 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 torturously difficult unless the game is very simple.

An important notion in CGT is that of the solved game. For example, tic-tac-toe is considered a solved game, as it can be proven that any game will result in a draw if both players play optimally. Deriving similar results for games with rich combinatorial structures is difficult. For instance, in 2007 it was announced that checkers has been weakly solved—optimal play by both sides also leads to a draw— ’’’ but this result was a computer-assisted proof ’’’. Other real world games are mostly too complicated to allow complete analysis today, although the theory has had some recent successes in analyzing Go endgames. 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 torturously difficult unless the game is very simple.

CGT中的一个重要概念是求解博弈。例如，井字棋被认为是一个已解决的游戏，因为它可以证明如果两个玩家都发挥最佳状态，那么任何游戏都将导致平局。对于具有丰富组合结构的游戏，获得相似的结果是困难的。例如，在2007年，有人宣布跳棋已被弱解---- 双方的最佳玩法也会导致平局---- ’’’ 但这个结果是计算机辅助证明 ’’’。尽管该理论最近在分析围棋终局游戏方面取得了一些成功，但其他现实世界的游戏大多过于复杂，以至于今天无法进行全面分析。将 CGT 应用到一个位置，试图确定两个玩家的最佳移动顺序，直到游戏结束，并以此发现在任何位置的最佳移动。在实践中，除非游戏非常简单，否则这个过程非常折磨人。

It can be helpful to distinguish between combinatorial "mathgames" of interest primarily to mathematicians and scientists to ponder and solve, and combinatorial "playgames" of interest to the general population as a form of entertainment and competition.[5] However, a number of games fall into both categories. Nim, for instance, is a playgame instrumental in the foundation of CGT, and one of the first computerized games.[6] Tic-tac-toe is still used to teach basic principles of game AI design to computer science students.

It can be helpful to distinguish between combinatorial "mathgames" of interest primarily to mathematicians and scientists to ponder and solve, and combinatorial "playgames" of interest to the general population as a form of entertainment and competition. However, a number of games fall into both categories. Nim, for instance, is a playgame instrumental in the foundation of CGT, and one of the first computerized games. Tic-tac-toe is still used to teach basic principles of game AI design to computer science students.

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

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

CGT的产生与公正博弈理论有关，在这个理论中，一个玩家可用的任何比赛必须对另一个玩家也可用。尼姆就是这样一种游戏，它可以完全解决。尼姆是一款适用于两名玩家的公正游戏，受到正常游戏条件的限制，这意味着不能移动的玩家就是输家。在20世纪30年代，Sprague-Grundy 定理表明，所有公正的游戏都等价于尼姆游戏，这表明在组合层次上考虑的游戏可能具有重大的统一性，在这种情况下，详细的策略很重要，而不仅仅是收益。

In the 1960s, Elwyn R. Berlekamp, John H. Conway and Richard K. Guy jointly introduced the theory of a partisan game, 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 work published on the subject was Conway's 1976 book 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.

In the 1960s, Elwyn R. Berlekamp, John H. Conway and Richard K. Guy jointly introduced the theory of a partisan game, 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 work published on the subject was Conway's 1976 book 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.

Combinatorial games are generally, by convention, put into a form where one player wins when the other has no moves remaining. It is easy to convert any finite game with only two possible results into an equivalent one where this convention applies. One of the most important concepts in the theory of combinatorial games is that of the sum of two games, which is a game where each player may choose to move either in one game or the other at any point in the game, and a player wins when his opponent has no move in either game. This way of combining games leads to a rich and powerful mathematical structure.

Combinatorial games are generally, by convention, put into a form where one player wins when the other has no moves remaining. It is easy to convert any finite game with only two possible results into an equivalent one where this convention applies. One of the most important concepts in the theory of combinatorial games is that of the sum of two games, which is a game where each player may choose to move either in one game or the other at any point in the game, and a player wins when his opponent has no move in either game. This way of combining games leads to a rich and powerful mathematical structure.

John Conway states in ONAG that the inspiration for the theory of partisan games was based on his observation of the play in go endgames, which can often be decomposed into sums of simpler endgames isolated from each other in different parts of the board.

John Conway states in ONAG that the inspiration for the theory of partisan games was based on his observation of the play in go endgames, which can often be decomposed into sums of simpler endgames isolated from each other in different parts of the board.

==Examples==

The introductory text Winning Ways introduced a large number of games, but the following were used as motivating examples for the introductory theory:

The introductory text Winning Ways introduced a large number of games, but the following were used as motivating examples for the introductory theory:

《赢家之道》介绍了大量的游戏，但以下是作为引导性理论的激励例子:

• 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 that 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.
• 蓝-红-绿 哈肯布什-允许附加的游戏值不是传统意义上的数字，例如星（博弈论）。
• Toads and Frogs - Allows various game values. Unlike most other games, a position is easily represented by a short string of characters.
• [蟾蜍和青蛙]- 允许各种游戏值。与大多数其他游戏不同，一个位置很容易用一串短字符来表示。
• Domineering - Various interesting games, such as hot games, appear as positions in Domineering, because 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.

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.

Another game studied in the context of combinatorial game theory is chess. In 1953 Alan Turing wrote of the game, "If one can explain quite unambiguously in English, with the aid of mathematical symbols if required, how a calculation is to be done, then it is always possible to programme any digital computer to do that calculation, provided the storage capacity is adequate."引用错误：没有找到与</ref>对应的<ref>标签 In a 1950 paper, Claude Shannon estimated the lower bound of the game-tree complexity of chess to be 10120, and today this is referred to as the Shannon number.[7] Chess remains unsolved, although extensive study, including work involving the use of supercomputers has created chess end-game tablebases, which shows the result of perfect play for all end-games with seven pieces or less. Infinite chess has an even greater combinatorial complexity than chess (unless only limited end-games, or composed positions with a small number of pieces are being studied).

}}</ref> In a 1950 paper, Claude Shannon estimated the lower bound of the game-tree complexity of chess to be 10120, and today this is referred to as the Shannon number. Chess remains unsolved, although extensive study, including work involving the use of supercomputers has created chess end-game tablebases, which shows the result of perfect play for all end-games with seven pieces or less. Infinite chess has an even greater combinatorial complexity than chess (unless only limited end-games, or composed positions with a small number of pieces are being studied).

} / ref 在1950年的一篇论文中，Claude Shannon 估计国际象棋博弈树复杂度的下限为10 sup 120 / sup，今天这被称为 Shannon 数。国际象棋仍然是无解的，尽管广泛的研究，包括涉及使用超级计算机的工作已经创建了国际象棋终局表库，它显示了所有七个或更少棋子的终局的完美结果。与国际象棋相比，无限棋比国际象棋有更大的组合复杂性(除非只研究有限的终局，或者只研究有少量棋子的组成局面)。

## Overview

A game, in its simplest terms, is a list of possible "moves" that two players, called left and right, can make. The game position resulting from any move can be considered to be another game. This idea of viewing games in terms of their possible moves to other games leads to a recursive mathematical definition of games that is standard in combinatorial game theory. In this definition, each game has the notation {L|R}. L is the set of game positions that the left player can move to, and R is the set of game positions that the right player can move to; each position in L and R is defined as a game using the same notation.

A game, in its simplest terms, is a list of possible "moves" that two players, called left and right, can make. The game position resulting from any move can be considered to be another game. This idea of viewing games in terms of their possible moves to other games leads to a recursive mathematical definition of games that is standard in combinatorial game theory. In this definition, each game has the notation {L|R}. L is the set of game positions that the left player can move to, and R is the set of game positions that the right player can move to; each position in L and R is defined as a game using the same notation.

Using Domineering as an example, label each of the sixteen boxes of the four-by-four board by A1 for the upper leftmost square, C2 for the third box from the left on the second row from the top, and so on. We use e.g. (D3, D4) to stand for the game position in which a vertical domino has been placed in the bottom right corner. Then, the initial position can be described in combinatorial game theory notation as

Using Domineering as an example, label each of the sixteen boxes of the four-by-four board by A1 for the upper leftmost square, C2 for the third box from the left on the second row from the top, and so on. We use e.g. (D3, D4) to stand for the game position in which a vertical domino has been placed in the bottom right corner. Then, the initial position can be described in combinatorial game theory notation as

$\displaystyle{ \{(\mathrm{A}1,\mathrm{A}2),(\mathrm{B}1,\mathrm{B}2),\dots|(\mathrm{A}1,\mathrm{B}1), (\mathrm{A}2,\mathrm{B}2),\dots\}. }$

$\displaystyle{ \{(\mathrm{A}1,\mathrm{A}2),(\mathrm{B}1,\mathrm{B}2),\dots|(\mathrm{A}1,\mathrm{B}1), (\mathrm{A}2,\mathrm{B}2),\dots\}. }$

In standard Cross-Cram play, the players alternate turns, but this alternation is handled implicitly by the definitions of combinatorial game theory rather than being encoded within the game states.

In standard Cross-Cram play, the players alternate turns, but this alternation is handled implicitly by the definitions of combinatorial game theory rather than being encoded within the game states.

Image:20x20square.pngImage:20x20square.png

Image:20x20square.png

$\displaystyle{ \{(\mathrm{A}1,\mathrm{A}2) | (\mathrm{A}1,\mathrm{B}1)\} = \{ \{|\} | \{|\} \}. }$

$\displaystyle{ \{(\mathrm{A}1,\mathrm{A}2) | (\mathrm{A}1,\mathrm{B}1)\} = \{ \{|\} | \{|\} \}. }$

Math (mathrum { a }1，mathrum { a }2) | (mathrum { a }1，mathrum { b }1) | | math

The above game describes a scenario in which there is only one move left for either player, and if either player makes that move, that player wins. (An irrelevant open square at C3 has been omitted from the diagram.) The {|} in each player's move list (corresponding to the single leftover square after the move) is called the zero game, and can actually be abbreviated 0. In the zero game, neither player has any valid moves; thus, the player whose turn it is when the zero game comes up automatically loses.

The above game describes a scenario in which there is only one move left for either player, and if either player makes that move, that player wins. (An irrelevant open square at C3 has been omitted from the diagram.) The {|} in each player's move list (corresponding to the single leftover square after the move) is called the zero game, and can actually be abbreviated 0. In the zero game, neither player has any valid moves; thus, the player whose turn it is when the zero game comes up automatically loses.

The type of game in the diagram above also has a simple name; it 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.

The type of game in the diagram above also has a simple name; it 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.

An additional type of game, not found in Domineering, is a loopy game, in which a valid move of either left or right is a game that can then lead back to the first game. Checkers, for example, becomes loopy when one of the pieces promotes, as then it can cycle endlessly between two or more squares. A game that does not possess such moves is called loopfree.

An additional type of game, not found in Domineering, is a loopy game, in which a valid move of either left or right is a game that can then lead back to the first game. Checkers, for example, becomes loopy when one of the pieces promotes, as then it can cycle endlessly between two or more squares. A game that does not possess such moves is called loopfree.

## Game abbreviations

### Numbers

Numbers represent the number of free moves, or the move advantage of a particular player. By convention positive numbers represent an advantage for Left, while negative numbers represent an advantage for Right. They are defined recursively with 0 being the base case.

Numbers represent the number of free moves, or the move advantage of a particular player. By convention positive numbers represent an advantage for Left, while negative numbers represent an advantage for Right. They are defined recursively with 0 being the base case.

0 = {|}
0 = {|}

0 = {|}

1 = {0|}, 2 = {1|}, 3 = {2|}
1 = {0|}, 2 = {1|}, 3 = {2|}

1 = {0|}, 2 = {1|}, 3 = {2|}

−1 = {|0}, −2 = {|−1}, −3 = {|−2}
−1 = {|0}, −2 = {|−1}, −3 = {|−2}

−1 = {|0}, −2 = {|−1}, −3 = {|−2}


The zero game is a loss for the first player.

The zero game is a loss for the first player.

0局，则是先发制人的失利。

 —- 意译


The sum of number games behaves like the integers, for example 3 + −2 = 1.

The sum of number games behaves like the integers, for example 3 + −2 = 1.

### Star

Star, written as ∗ or {0|0}, is a first-player win since either player must (if first to move in the game) move to a zero game, and therefore win.

Star, written as ∗ or {0|0}, is a first-player win since either player must (if first to move in the game) move to a zero game, and therefore win.

∗ + ∗ = 0, because the first player must turn one copy of ∗ to a 0, and then the other player will have to turn the other copy of ∗ to a 0 as well; at this point, the first player would lose, since 0 + 0 admits no moves.
∗ + ∗ = 0, because the first player must turn one copy of ∗ to a 0, and then the other player will have to turn the other copy of ∗ to a 0 as well; at this point, the first player would lose, since 0 + 0 admits no moves.


∗ + ∗ = 0，因为第一个玩家必须把一个 ∗ 的一个棋子变成0，然后另一个玩家也必须把∗的另一个棋子变成0; 这时，第一个玩家会输，因为0 + 0不允许移动。

The game ∗ is neither positive nor negative; it and all other games in which the first player wins (regardless of which side the player is on) are said to be fuzzy with or confused with 0; symbolically, we write ∗ || 0.

The game ∗ is neither positive nor negative; it and all other games in which the first player wins (regardless of which side the player is on) are said to be fuzzy with or confused with 0; symbolically, we write ∗ || 0.

### Up

Up, written as ↑, is a position in combinatorial game theory.[8] In standard notation, ↑ = {0|∗}.

Up, written as ↑, is a position in combinatorial game theory. In standard notation, ↑ = {0|∗}.

−↑ = ↓ (down)
−↑ = ↓ (down)

−↑ = ↓ (down)


Up is strictly positive (↑ > 0), but is infinitesimal. Up is defined in Winning Ways for your Mathematical Plays.

Up is strictly positive (↑ > 0), but is infinitesimal. Up is defined in Winning Ways for your Mathematical Plays.

### Down

Down, written as ↓, is a position in combinatorial game theory.[8] In standard notation, ↓ = {∗|0}.

Down, written as ↓, is a position in combinatorial game theory. In standard notation, ↓ = {∗|0}.

−↓ = ↑ (up)
−↓ = ↑ (up)

−↓ = ↑ (up)


Down is strictly negative (↓ < 0), but is infinitesimal. Down is defined in Winning Ways for your Mathematical Plays.

Down is strictly negative (↓ < 0), but is infinitesimal. Down is defined in Winning Ways for your Mathematical Plays.

Down是严格意义上的负数（↓<0），但却是无穷小的。Down的定义见《数学游戏的赢家》。

### "Hot" games

Consider the game {1|−1}. Both moves in this game are an advantage for the player who makes them; so the game is said to be "hot;" it is greater than any number less than −1, less than any number greater than 1, and fuzzy with any number in between. It is written as ±1. It can be added to numbers, or multiplied by positive ones, in the expected fashion; for example, 4 ± 1 = {5|3}.

Consider the game {1|−1}. Both moves in this game are an advantage for the player who makes them; so the game is said to be "hot;" it is greater than any number less than −1, less than any number greater than 1, and fuzzy with any number in between. It is written as ±1. It can be added to numbers, or multiplied by positive ones, in the expected fashion; for example, 4 ± 1 = {5|3}.

## 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, domineering is not impartial, because one player places horizontal dominoes and the other places vertical ones. Likewise Checkers is not impartial, since the players own different colored pieces. 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.

The "smallest" nimbers – the simplest and least under the usual ordering of the ordinals – are 0 and ∗.

The "smallest" nimbers – the simplest and least under the usual ordering of the ordinals – are 0 and ∗.

“最小”的尼姆数是0和 * ，即按照通常的顺序排列最简单和最小的尼姆数。

Alpha-beta剪枝算法，一种用于搜索博弈树的优化算法

• Connection game, a type of game where players attempt to establish connections

Expectiminimax树，最小化博弈树的改编，以适应有偶然因素的博弈。

• Game complexity, an article describing ways of measuring the complexity of games

• Grundy's game, a mathematical game in which heaps of objects are split

• Sylver coinage, a mathematical game of choosing positive integers that are not the sum of non-negative multiples of previously chosen integers

Sylver coinage，一种选择正整数的数学游戏，该整数不是先前选择的整数的非负倍数的总和

• Wythoff's game, a mathematical game of taking objects from one or two piles

Wythoff的游戏，一种从一堆或两堆中取出物体的数学游戏

• Zugzwang, being obliged to play when this is disadvantageous

## Notes

1. Lessons in Play, p. 3
2. Thomas S. Fergusson's analysis of poker is an example of CGT expanding into games that include elements of chance. Research into Three Player NIM is an example of study expanding beyond two player games. Conway, Guy and Berlekamp's analysis of partisan games is perhaps the most famous expansion of the scope of CGT, taking the field beyond the study of impartial games.
3. http://erikdemaine.org/papers/AlgGameTheory_GONC3/paper.pdf
4. Schaeffer, J.; Burch, N.; Bjornsson, Y.; Kishimoto, A.; Muller, M.; Lake, R.; Lu, P.; Sutphen, S. (2007). "Checkers is solved". Science. 317 (5844): 1518–1522. Bibcode:2007Sci...317.1518S. CiteSeerX 10.1.1.95.5393. doi:10.1126/science.1144079. PMID 17641166.
5. Fraenkel, Aviezri (2009). "Combinatorial Games: selected bibliography with a succinct gourmet introduction". Games of No Chance 3. 56: 492.
6. Grant, Eugene F.; Lardner, Rex (2 August 1952). "The Talk of the Town - It". The New Yorker.
7. Claude Shannon (1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. 41 (314): 4. Archived from the original (PDF) on 2010-07-06.
8. E. Berlekamp; J. H. Conway; R. Guy (1982). Winning Ways for your Mathematical Plays. I. Academic Press. ISBN 0-12-091101-9.
E. Berlekamp; J. H. Conway; R. Guy (1982). Winning Ways for your Mathematical Plays. II. Academic Press. ISBN 0-12-091102-7.

## References

• [[Michael H. Albert

2; Wolfe, David

3 David (2007). Lessons in Play: An Introduction to Combinatorial Game Theory

[国际标准图书馆编号978-1-56881-277-9]|978-1-56881-277-9

[国际标准图书馆编号978-1-56881-277-9]]].

| year = 2007}}


2007年开始

[国际标准图书编号978-0-521-46100-9]|978-0-521-46100-9

[国际标准图书编号978-0-521-46100-9]]].

| year = 2008}}


2008年开始

• [[Elwyn Berlekamp

1 |Berlekamp, E.]]; [[John Horton Conway

2 Conway |Conway, J. H.]]; [[Richard K. Guy

,

| year = 1982}} 2nd ed., A K Peters Ltd (2001–2004),  ,


| 1982年}}第二版，a k Peters Ltd (2001-2004) ，,

• Berlekamp, E.

1; Conway, J. H.

2 Conway; [[Richard K. Guy

,

.

| url = https://archive.org/details/winningwaysforyo02berl | url-access = registration | year = 1982}} 2nd ed., A K Peters Ltd (2001–2004), , .


Https://archive.org/details/winningwaysforyo02berl : a k Peters Ltd (2001-2004) ，1982年。

• [[Elwyn Berlekamp

1 Elwyn |Berlekamp, Elwyn]]; [[David Wolfe (mathematician)

1-56881-032-6|1-56881-032-6

1-56881-032-6]].

| url = https://archive.org/details/mathematicalgoch0000berl | url-access = registration | year = 1997}}


| https://archive.org/details/mathematicalgoch0000berl | url-access registration | year 1997}

1-56881-210-8|1-56881-210-8

1-56881-210-8]].  See especially sections 21–26.

| year = 2004}} See especially sections 21–26.


• [[John Horton Conway

.

| year = 1976}} 2nd ed., A K Peters Ltd (2001), .


| 1976年}}第二版，a k Peters Ltd (2001) ，。

• Robert A. Hearn; Erik D. Demaine (2009). Games, Puzzles, and Computation. A K Peters, Ltd.. ISBN 978-1-56881-322-6.