更改

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

组合游戏包括著名的游戏，如国际象棋、西洋跳棋和围棋，这些游戏被认为是非常重要的，还有井字游戏，这些游戏被认为是微不足道的，因为它们“很容易解决”。一些组合游戏也可能有一个无限的游戏区域，如无限的国际象棋。在 CGT 中，这些和其他游戏中的步骤被表示为一个博弈树。

组合游戏包括著名的游戏，如国际象棋、西洋跳棋和围棋，这些游戏被认为是非常重要的，还有井字棋，这些游戏被认为是微不足道的，因为它们“很容易解决”。一些组合游戏也可能有一个无限的游戏区域，如无限国际象棋。在 CGT 中，这些和其他游戏中的步骤被表示为一个博弈树。

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

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. 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 修剪启发式) ，而更多强调描述性的理论结果(例如对策复杂性的度量或最优解存在性的证明，而不一定指定算法，例如策略窃取论点)。

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. 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 应用到一个位置，试图确定两个玩家的最佳移动顺序，直到游戏结束，并通过这样做，发现在任何位置的最佳移动。在实践中，除非游戏非常简单，否则这个过程非常困难。

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

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.   

它有助于区分主要是供数学家和科学家思考和解决的组合型”数学游戏”和作为一种娱乐和竞争形式的广大民众感兴趣的组合型”游戏”。然而，许多游戏都属于这两种类型。以尼姆为例，它是 CGT 基础上的一个游戏，也是最早的电脑游戏之一。井字游戏仍然是用来教游戏 AI 设计的基本原则，计算机科学的学生。

它有助于区分主要是供数学家和科学家思考和解决的组合型”数学游戏”和作为一种娱乐和竞争形式的广大民众感兴趣的组合型”游戏”。然而，许多游戏都属于这两种类型。以尼姆为例，它是在 CGT 基础上的一种游戏，也是最早的电脑游戏之一。井字棋仍然用于向计算机科学专业的学生教授游戏AI设计的基本原理。

==History==

==History==

CGT arose in relation to the theory of [[impartial game]]s, 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 game]]s, 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 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.

法官总工会的产生与公正博弈理论有关，在这个理论中，一个球员可用的任何比赛必须对另一个球员也可用。尼姆就是这样一种博弈，它可以被完全解决。尼姆是一个对两个玩家不偏不倚的游戏，受到正常游戏条件的限制，这意味着不能移动的玩家就是输家。在20世纪30年代，Sprague-Grundy 定理表明，所有公正的游戏都等价于 nim 中的大堆，因此表明，在被认为是组合级别的游戏中，主要的统一是可能的，在这些游戏中，详细的策略很重要，而不仅仅是收益。

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.

在20世纪60年代，埃尔温·伯利坎普，John h. Conway 和 Richard k. Guy 联合提出了一个党派游戏的理论，在这个理论中，一个球员可以使用的游戏对双方都是放松的。他们的研究结果发表在1982年出版的《数学游戏的制胜之道》一书中。然而，康威1976年出版的第一本关于数字和游戏的书，也被称为 ONAG，介绍了超现实数字的概念和对游戏的概括。《数字与游戏》也是 Berlekamp、康威和盖伊合作的成果。

在20世纪60年代，埃尔温·伯利坎普Elwyn R. Berlekamp，约翰·h·康威。 John h. Conway 和 理查德·盖伊 Richard k. Guy 共同提出了一个党派博弈理论，在这个理论中，放宽了一个游戏可供两个玩家使用的要求。他们的研究结果发表在1982年的《数学游戏的获胜方法》一书中。但是，关于这一主题的第一部著作是Conway于1976年出版的《数与游戏》（也称为ONAG），该书引入了超现实数的概念以及对游戏。《数字与游戏》也是Berlekamp，Conway和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.

约翰 · 康威在 ONAG 中指出，党派游戏理论的灵感来源于他对围棋终局游戏的观察。

约翰 · 康威在 ONAG 中指出，党派博弈理论的灵感来源于他对围棋终局游戏的观察。