1,569
个编辑
更改
跳到导航
跳到搜索
Moved page from wikipedia:en:Combinatorial game theory (history)
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
{{about|the theory of combinatorial games|the theory that includes games of chance and games of imperfect knowledge|Game theory}}
[[Image:Mathematicians playing Konane.jpg|thumb|Mathematicians playing [[Konane]] at a combinatorial game theory workshop]]
Mathematicians playing [[Konane at a combinatorial game theory workshop]]
数学家们在玩[ Konane 在组合博弈论研讨会上]
'''Combinatorial game theory''' ('''CGT''') is a branch of [[mathematics]] and [[theoretical computer science]] that typically studies [[sequential game]]s with [[perfect information]]. Study has been largely confined to two-player [[game]]s 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.<ref>Lessons in Play, p. 3</ref> However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing.<ref>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.</ref> 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]], [[Draughts|checkers]], and [[Go (board game)|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 [[Bounded set|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 中，这些和其他游戏中的步骤被表示为一个博弈树。
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".<ref name=AlgGameTheory>http://erikdemaine.org/papers/AlgGameTheory_GONC3/paper.pdf</ref>)
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.<ref name=AlgGameTheory/> 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 algorithm]]s (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 [[Solved game#overview|weakly solved]]—optimal play by both sides also leads to a draw—but this result was a [[computer-assisted proof]].<ref>{{Cite journal| last1 = Schaeffer | first1 = J.| last2 = Burch | first2 = N.| last3 = Bjornsson | first3 = Y.| last4 = Kishimoto | first4 = A.| last5 = Muller | first5 = M.| last6 = Lake | first6 = R.| last7 = Lu | first7 = P.| last8 = Sutphen | first8 = S.| title = Checkers is solved| journal = [[Science (journal)|Science]]| volume = 317| issue = 5844| pages = 1518–1522| year = 2007| pmid = 17641166| doi = 10.1126/science.1144079| citeseerx = 10.1.1.95.5393| bibcode = 2007Sci...317.1518S}}</ref> 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.<ref>{{Cite journal| last1 = Fraenkel | first1 = Aviezri| title = Combinatorial Games: selected bibliography with a succinct gourmet introduction| journal = Games of No Chance 3| volume = 56| pages = 492| year = 2009}}</ref> 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.<ref>{{Cite news |url=http://www.newyorker.com/archive/1952/08/02/1952_08_02_018_TNY_CARDS_000236053 |title=The Talk of the Town - It |first1=Eugene F. |last1=Grant |first2=Rex |last2=Lardner |date=2 August 1952 |newspaper=[[The New Yorker]]}}</ref> 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 设计的基本原则，计算机科学的学生。
==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 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 中的大堆，因此表明，在被认为是组合级别的游戏中，主要的统一是可能的，在这些游戏中，详细的策略很重要，而不仅仅是收益。
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 number]]s 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、康威和盖伊合作的成果。
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 (board game)|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 中指出，党派游戏理论的灵感来源于他对围棋终局游戏的观察。
==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|dyadic rational number]]s. 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 (game theory)|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 game]]s, appear as positions in Domineering, because there is sometimes an incentive to move, and sometimes not. This allows discussion of a game's [[temperature (game theory)|temperature]].
* [[Nim]] - An [[impartial game]]. This allows for the construction of the [[nimber]]s. (It can also be seen as a green-only special case of Blue-Red-Green Hackenbush.)
The classic game [[Go (board 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.
经典的围棋游戏对早期的组合博弈论产生了影响，Berlekamp 和 Wolfe 随后为围棋发展出了一套终局和温度理论(见参考文献)。有了这些武器，他们就能够构建出合理的围棋终局位置，从中他们可以给围棋高手一个选择阵营的机会，然后以任何一种方式击败他们。
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>{{cite web
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>{{cite web
另一个在组合博弈论中研究的游戏是国际象棋。1953年，阿兰 · 图灵写道: “如果一个人能够用英语清楚地解释，如果需要的话，可以借助数学符号来解释如何进行计算，那么，只要存储容量足够，任何数字计算机都有可能进行计算。1.1.1.1.1.1.1.2.1.2.1.2.2.2.1.2.2.2.2.2.2.2.2.2.2.1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2
| url=http://www.turingarchive.org/browse.php/B/7
| url=http://www.turingarchive.org/browse.php/B/7
Http://www.turingarchive.org/browse.php/b/7
| title=Digital computers applied to games
| title=Digital computers applied to games
应用于游戏的数字计算机
| author=Alan Turing
| author=Alan Turing
作者: 阿兰 · 图灵
| publisher=University of Southampton and King's College Cambridge
| publisher=University of Southampton and King's College Cambridge
剑桥大学国王学院南安普敦大学
| page=2
| page=2
第二页
}}</ref> In a 1950 paper, [[Claude Shannon]] estimated the lower bound of the [[game complexity|game-tree complexity]] of chess to be 10<sup>120</sup>, and today this is referred to as the [[Shannon number]].<ref>{{cite journal | author = [[Claude Shannon]] | title = Programming a Computer for Playing Chess | journal = Philosophical Magazine | volume = 41 | issue = 314 | year = 1950 | page = 4 | url = http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | url-status = dead | archiveurl = https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | archivedate = 2010-07-06 }}</ref> Chess remains unsolved, although extensive study, including work involving the use of supercomputers has created chess end-game [[Endgame tablebase|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 10<sup>120</sup>, 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 [[recursion|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 (mathematics)|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.
一个博弈，用最简单的术语来说，就是两个参与者(左边和右边)可以完成的一系列可能的“动作”。游戏的位置产生的任何移动可以被认为是另一个游戏。这种根据游戏可能转移到其他游戏的观点导致了游戏的递归数学定义，这是21组合博弈论的标准。在这个定义中，每个游戏都有一个符号{ l | r }。是左边玩家可以移动到的游戏位置的集合，r 是右边玩家可以移动到的游戏位置的集合; l 和 r 中的每个位置都被定义为使用相同符号的游戏。
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
以霸气为例，用 A1表示最左边的方格，用 C2表示第二排左边的第三个方格，以此类推。我们使用例如。(D3，D4)代表游戏位置，即一块垂直的多米诺骨牌被放置在游戏的右下角。然后，初始位置可以用组合博弈论表示法描述为
:<math>\{(\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\}.</math>
<math>\{(\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\}.</math>
数学[ a ]1，[ a ]2) ，(数学[ b ]1，[ b ]2) ，[点] | (数学[ a ]1，[ b ]1) ，[ a ]2，[ b ]2] ，[点] . / 数学
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.png]][[Image:20x20square.png]]<br/>
Image:20x20square.pngImage:20x20square.png<br/>
图片: 20x20square. pngImage: 20x20square.png br /
:::[[Image:20x20square.png]]
Image:20x20square.png
图片: 20x20square. png
:<math>\{(\mathrm{A}1,\mathrm{A}2) | (\mathrm{A}1,\mathrm{B}1)\} = \{ \{|\} | \{|\} \}.</math>
<math>\{(\mathrm{A}1,\mathrm{A}2) | (\mathrm{A}1,\mathrm{B}1)\} = \{ \{|\} | \{|\} \}.</math>
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 <nowiki>{|}</nowiki> 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 <nowiki>{|}</nowiki> 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.
上面的游戏描述了一个场景，在这个场景中，任何一个玩家只剩下一步棋，如果任何一个玩家走了那一步棋，那个玩家就赢了。(图中省略了 C3处一个不相关的开平方)每个玩家的移动列表中的 nowiki { | } / nowiki (对应于移动后剩下的单个方块)称为零游戏，实际上可以缩写为0。在零游戏中，两个玩家都没有任何有效的移动，因此，当零游戏出现时，轮到的玩家自动失败。
The type of game in the diagram above also has a simple name; it is called the [[star (game theory)|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 = {|}
0 = {|}
: 1 = {0|}, 2 = {1|}, 3 = {2|}
1 = {0|}, 2 = {1|}, 3 = {2|}
1 = {0|}, 2 = {1|}, 3 = {2|}
: <nowiki>−1 = {|0}, −2 = {|−1}, −3 = {|−2}</nowiki>
<nowiki>−1 = {|0}, −2 = {|−1}, −3 = {|−2}</nowiki>
<nowiki>−1 = {|0}, −2 = {|−1}, −3 = {|−2}</nowiki>
The [[zero game]] is a loss for the first player.
The zero game is a loss for the first player.
零游戏对于第一个玩家来说是一种损失。
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.
数字游戏之和的行为类似于整数，例如3 +-21。
===Star===
''[[star (game theory)|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.
星，写作 x 或{0 | 0} ，是第一个玩家的胜利，因为任何一个玩家必须(如果第一个在游戏中移动)移动到零游戏，因此赢。
: ∗ + ∗ = 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.
衰 x + 0，因为第一个参与者必须把一个 x 分数的副本变成0，然后另一个参与者也必须把另一个 x 分数的副本变成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 game|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.
第一个参与者胜出的所有其他游戏(不管参与者站在哪一边)都被称为 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x。
===Up===
''Up'', written as ↑, is a position in combinatorial game theory.<ref name=winningways>{{cite book |author1=E. Berlekamp |author2=J. H. Conway |author3=R. Guy | title=[[Winning Ways for your Mathematical Plays]] | volume=I | publisher=Academic Press | year=1982 | isbn=0-12-091101-9}}<br/>{{cite book |author1=E. Berlekamp |author2=J. H. Conway |author3=R. Guy | title=Winning Ways for your Mathematical Plays | volume=II | publisher=Academic Press | year=1982 | isbn=0-12-091102-7}}</ref> In standard notation, ↑ = {0|∗}.
Up, written as ↑, is a position in combinatorial game theory. In standard notation, ↑ = {0|∗}.
上面，注明↑ ，是组合博弈论中的一个位置。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.
Up 是严格正的(↑0) ，但是是无穷小的。向上是定义在你的数学游戏的胜利方式。
===Down===
''Down'', written as ↓, is a position in combinatorial game theory.<ref name=winningways /> In standard notation, ↓ = {∗|0}.
Down, written as ↓, is a position in combinatorial game theory. In standard notation, ↓ = {∗|0}.
是组合博弈论的一个职位↓。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.
是严格的负数(↓0) ，但是是无穷小的。在你的数学游戏的胜利方式中定义了向下。
==="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}.
Consider the game {1|−1}.在这个游戏中，两个动作都是制造它们的玩家的优势; 所以这个游戏被称为“热” ; 它比任何小于 -1的数字都要大，小于大于1的数字都要小，而且在两者之间的任何数字都是模糊的。它被写成了1。它可以以预期的方式加到数字上，或者乘以正数; 例如，41{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 [[nimber]]s. The [[Sprague–Grundy theorem]] states that every impartial game is equivalent to a nimber.
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.
一个公正的游戏是这样的，在游戏的每个位置，两个玩家都可以使用相同的动作。例如，尼姆是公正的，因为任何一组可以被一个玩家移除的物体都可以被另一个玩家移除。然而，霸道并不公平，因为一个玩家放置水平的多米诺骨牌，另一个放置垂直的。同样，西洋跳棋也是不公平的，因为玩家拥有不同颜色的棋子。对于任何序数，我们都可以定义一个公正的游戏来概括 Nim，在这个游戏中，任何一个玩家在每次移动时都可以用任何较小的序数来替换这个数字; 这样定义的游戏被称为 nimbers。斯普拉格-格兰迪定理指出，每一个公正的博弈都等价于一个智者。
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和 * ，即按照通常的顺序排列最简单和最小的邻位数。
==See also==
* [[Alpha–beta pruning]], an optimised algorithm for searching the game tree
* [[Backward induction]], reasoning backwards from a final situation
* [[Cooling and heating (combinatorial game theory)]], various transformations of games making them more amenable to the theory
* [[Connection game]], a type of game where players attempt to establish connections
* [[Endgame tablebase]], a database saying how to play endgames
* [[Expectiminimax tree]], an adaptation of a minimax game tree to games with an element of chance
* [[Extensive-form game]], a game tree enriched with payoffs and information available to players
* [[Game classification]], an article discussing ways of classifying games
* [[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
* [[Multi-agent system]], a type of computer system for tackling complex problems
* [[Solving chess]]
* [[Sylver coinage]], a mathematical game of choosing positive integers that are not the sum of non-negative multiples of previously chosen integers
* [[Wythoff's game]], a mathematical game of taking objects from one or two piles
* [[Topological game]], a type of mathematical game played in a topological space
* [[Zugzwang]], being obliged to play when this is disadvantageous
==Notes==
{{Reflist}}
==References==
*{{cite book
| last1 = Albert | first1 = Michael H. | author1-link = Michael H. Albert
| last1 = Albert | first1 = Michael H. | author1-link = Michael H. Albert
作者: 迈克尔 · h · 艾伯特
| last2 = Nowakowski | first2 = Richard J.
| last2 = Nowakowski | first2 = Richard J.
2 | nowaykowski | first2 Richard j.
| last3 = Wolfe | first3 = David
| last3 = Wolfe | first3 = David
3 David
| isbn = 978-1-56881-277-9
| isbn = 978-1-56881-277-9
[国际标准图书馆编号978-1-56881-277-9]
| publisher = A K Peters Ltd
| publisher = A K Peters Ltd
| 出版商 a k Peters Ltd
| title = Lessons in Play: An Introduction to Combinatorial Game Theory
| title = Lessons in Play: An Introduction to Combinatorial Game Theory
游戏中的课程: 组合博弈论入门
| year = 2007}}
| year = 2007}}
2007年开始
*{{cite book
| last = Beck | first = József | author-link = József Beck
| last = Beck | first = József | author-link = József Beck
| last = Beck | first = József | author-link = József Beck
| isbn = 978-0-521-46100-9
| isbn = 978-0-521-46100-9
[国际标准图书编号978-0-521-46100-9]
| publisher = Cambridge University Press
| publisher = Cambridge University Press
出版商剑桥大学出版社
| title = Combinatorial games: tic-tac-toe theory
| title = Combinatorial games: tic-tac-toe theory
组合游戏: 井字游戏理论
| title-link = Combinatorial Games: Tic-Tac-Toe Theory
| title-link = Combinatorial Games: Tic-Tac-Toe Theory
| 题目链接组合游戏: 井字游戏理论
| year = 2008}}
| year = 2008}}
2008年开始
*{{cite book
| last1 = Berlekamp | first1 = E. | author1-link = Elwyn Berlekamp
| last1 = Berlekamp | first1 = E. | author1-link = Elwyn Berlekamp
1 | last1 Berlekamp | first1 e | author1-link Elwyn Berlekamp
| last2 = Conway | first2 = J. H. | author2-link = John Horton Conway
| last2 = Conway | first2 = J. H. | author2-link = John Horton Conway
2 Conway | first2 j. h. | author2-link 约翰·何顿·康威
| last3 = Guy | first3 = R. | author3-link = Richard K. Guy
| last3 = Guy | first3 = R. | author3-link = Richard K. Guy
作者: 理查德 · 盖伊
| isbn = 0-12-091101-9
| isbn = 0-12-091101-9
| isbn 0-12-091101-9
| publisher = Academic Press
| publisher = Academic Press
出版商: 学术出版社
| title = [[Winning Ways for your Mathematical Plays]]: Games in general
| title = Winning Ways for your Mathematical Plays: Games in general
| 题目你的数学游戏的成功之道: 一般的游戏
| year = 1982}} 2nd ed., A K Peters Ltd (2001–2004), {{ISBN|1-56881-130-6}}, {{ISBN|1-56881-142-X}}
| year = 1982}} 2nd ed., A K Peters Ltd (2001–2004), ,
| 1982年}}第二版，a k Peters Ltd (2001-2004) ，,
* {{cite book
| last1 = Berlekamp | first1 = E.
| last1 = Berlekamp | first1 = E.
1 | last1 Berlekamp | first1.
| last2 = Conway | first2 = J. H.
| last2 = Conway | first2 = J. H.
2 Conway | first2 j. h.
| last3 = Guy | first3 = R. | author3-link = Richard K. Guy
| last3 = Guy | first3 = R. | author3-link = Richard K. Guy
作者: 理查德 · 盖伊
| isbn = 0-12-091102-7
| isbn = 0-12-091102-7
| isbn 0-12-091102-7
| publisher = Academic Press
| publisher = Academic Press
出版商: 学术出版社
| title = Winning Ways for your Mathematical Plays: Games in particular
| title = Winning Ways for your Mathematical Plays: Games in particular
| 题目: 数学游戏的制胜之道: 特别是游戏
| url = https://archive.org/details/winningwaysforyo02berl | url-access = registration | year = 1982}} 2nd ed., A K Peters Ltd (2001–2004), {{ISBN|1-56881-143-8}}, {{ISBN|1-56881-144-6}}.
| 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年。
*{{cite book
| last1 = Berlekamp | first1 = Elwyn | author1-link = Elwyn Berlekamp
| last1 = Berlekamp | first1 = Elwyn | author1-link = Elwyn Berlekamp
1 Elwyn | author1-link Elwyn Berlekamp
| last2 = Wolfe | first2 = David | author2-link = David Wolfe (mathematician)
| last2 = Wolfe | first2 = David | author2-link = David Wolfe (mathematician)
大卫 · 沃尔夫(数学家)
| isbn = 1-56881-032-6
| isbn = 1-56881-032-6
1-56881-032-6
| publisher = A K Peters Ltd
| publisher = A K Peters Ltd
| 出版商 a k Peters Ltd
| title = Mathematical Go: Chilling Gets the Last Point
| title = Mathematical Go: Chilling Gets the Last Point
数学行动: 冷却得到最后一分
| url = https://archive.org/details/mathematicalgoch0000berl | url-access = registration | year = 1997}}
| url = https://archive.org/details/mathematicalgoch0000berl | url-access = registration | year = 1997}}
| https://archive.org/details/mathematicalgoch0000berl | url-access registration | year 1997}
*{{cite book
| last = Bewersdorff | first = Jörg | author1-link = Jörg Bewersdorff
| last = Bewersdorff | first = Jörg | author1-link = Jörg Bewersdorff
| last = Bewersdorff | first = Jörg | author1-link = Jörg Bewersdorff
| isbn = 1-56881-210-8
| isbn = 1-56881-210-8
1-56881-210-8
| publisher = A K Peters Ltd
| publisher = A K Peters Ltd
| 出版商 a k Peters Ltd
| title = Luck, Logic and White Lies: The Mathematics of Games
| title = Luck, Logic and White Lies: The Mathematics of Games
运气，逻辑和善意的谎言: 游戏的数学
| year = 2004}} See especially sections 21–26.
| year = 2004}} See especially sections 21–26.
特别是21-26节。
*{{cite book
| last = Conway | first = John Horton | author-link = John Horton Conway
| last = Conway | first = John Horton | author-link = John Horton Conway
最后一个康威 | 第一个 John Horton | 作者链接约翰·何顿·康威
| isbn = 0-12-186350-6
| isbn = 0-12-186350-6
| isbn 0-12-186350-6
| publisher = Academic Press
| publisher = Academic Press
出版商: 学术出版社
| title = [[On Numbers and Games]]
| title = On Numbers and Games
关于数字和游戏
| year = 1976}} 2nd ed., A K Peters Ltd (2001), {{ISBN|1-56881-127-6}}.
| year = 1976}} 2nd ed., A K Peters Ltd (2001), .
| 1976年}}第二版，a k Peters Ltd (2001) ，。
* {{cite book|author1=Robert A. Hearn|author2=Erik D. Demaine|title=Games, Puzzles, and Computation|year=2009|publisher=A K Peters, Ltd.|isbn=978-1-56881-322-6}}
==External links==
*[http://www.ics.uci.edu/~eppstein/cgt/ List of combinatorial game theory links] at the homepage of [[David Eppstein]]
*[https://arxiv.org/pdf/math/0410026 An Introduction to Conway's games and numbers] by Dierk Schleicher and Michael Stoll
*[http://senseis.xmp.net/?CGTPath#toc1 Combinational Game Theory terms summary] by Bill Spight
*[http://www.pims.math.ca/birs/birspages.php?task=displayevent&event_id=05w5048 Combinatorial Game Theory Workshop, Banff International Research Station, June 2005]
{{Game theory}}
{{Authority control}}
[[Category:Combinatorial game theory|*]]
*
*
<noinclude>
<small>This page was moved from [[wikipedia:en:Combinatorial game theory]]. Its edit history can be viewed at [[组合博弈论/edithistory]]</small></noinclude>
[[Category:待整理页面]]
{{about|the theory of combinatorial games|the theory that includes games of chance and games of imperfect knowledge|Game theory}}
[[Image:Mathematicians playing Konane.jpg|thumb|Mathematicians playing [[Konane]] at a combinatorial game theory workshop]]
Mathematicians playing [[Konane at a combinatorial game theory workshop]]
数学家们在玩[ Konane 在组合博弈论研讨会上]
'''Combinatorial game theory''' ('''CGT''') is a branch of [[mathematics]] and [[theoretical computer science]] that typically studies [[sequential game]]s with [[perfect information]]. Study has been largely confined to two-player [[game]]s 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.<ref>Lessons in Play, p. 3</ref> However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing.<ref>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.</ref> 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]], [[Draughts|checkers]], and [[Go (board game)|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 [[Bounded set|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 中，这些和其他游戏中的步骤被表示为一个博弈树。
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".<ref name=AlgGameTheory>http://erikdemaine.org/papers/AlgGameTheory_GONC3/paper.pdf</ref>)
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.<ref name=AlgGameTheory/> 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 algorithm]]s (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 [[Solved game#overview|weakly solved]]—optimal play by both sides also leads to a draw—but this result was a [[computer-assisted proof]].<ref>{{Cite journal| last1 = Schaeffer | first1 = J.| last2 = Burch | first2 = N.| last3 = Bjornsson | first3 = Y.| last4 = Kishimoto | first4 = A.| last5 = Muller | first5 = M.| last6 = Lake | first6 = R.| last7 = Lu | first7 = P.| last8 = Sutphen | first8 = S.| title = Checkers is solved| journal = [[Science (journal)|Science]]| volume = 317| issue = 5844| pages = 1518–1522| year = 2007| pmid = 17641166| doi = 10.1126/science.1144079| citeseerx = 10.1.1.95.5393| bibcode = 2007Sci...317.1518S}}</ref> 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.<ref>{{Cite journal| last1 = Fraenkel | first1 = Aviezri| title = Combinatorial Games: selected bibliography with a succinct gourmet introduction| journal = Games of No Chance 3| volume = 56| pages = 492| year = 2009}}</ref> 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.<ref>{{Cite news |url=http://www.newyorker.com/archive/1952/08/02/1952_08_02_018_TNY_CARDS_000236053 |title=The Talk of the Town - It |first1=Eugene F. |last1=Grant |first2=Rex |last2=Lardner |date=2 August 1952 |newspaper=[[The New Yorker]]}}</ref> 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 设计的基本原则，计算机科学的学生。
==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 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 中的大堆，因此表明，在被认为是组合级别的游戏中，主要的统一是可能的，在这些游戏中，详细的策略很重要，而不仅仅是收益。
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 number]]s 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、康威和盖伊合作的成果。
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 (board game)|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 中指出，党派游戏理论的灵感来源于他对围棋终局游戏的观察。
==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|dyadic rational number]]s. 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 (game theory)|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 game]]s, appear as positions in Domineering, because there is sometimes an incentive to move, and sometimes not. This allows discussion of a game's [[temperature (game theory)|temperature]].
* [[Nim]] - An [[impartial game]]. This allows for the construction of the [[nimber]]s. (It can also be seen as a green-only special case of Blue-Red-Green Hackenbush.)
The classic game [[Go (board 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.
经典的围棋游戏对早期的组合博弈论产生了影响，Berlekamp 和 Wolfe 随后为围棋发展出了一套终局和温度理论(见参考文献)。有了这些武器，他们就能够构建出合理的围棋终局位置，从中他们可以给围棋高手一个选择阵营的机会，然后以任何一种方式击败他们。
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>{{cite web
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>{{cite web
另一个在组合博弈论中研究的游戏是国际象棋。1953年，阿兰 · 图灵写道: “如果一个人能够用英语清楚地解释，如果需要的话，可以借助数学符号来解释如何进行计算，那么，只要存储容量足够，任何数字计算机都有可能进行计算。1.1.1.1.1.1.1.2.1.2.1.2.2.2.1.2.2.2.2.2.2.2.2.2.2.1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2
| url=http://www.turingarchive.org/browse.php/B/7
| url=http://www.turingarchive.org/browse.php/B/7
Http://www.turingarchive.org/browse.php/b/7
| title=Digital computers applied to games
| title=Digital computers applied to games
应用于游戏的数字计算机
| author=Alan Turing
| author=Alan Turing
作者: 阿兰 · 图灵
| publisher=University of Southampton and King's College Cambridge
| publisher=University of Southampton and King's College Cambridge
剑桥大学国王学院南安普敦大学
| page=2
| page=2
第二页
}}</ref> In a 1950 paper, [[Claude Shannon]] estimated the lower bound of the [[game complexity|game-tree complexity]] of chess to be 10<sup>120</sup>, and today this is referred to as the [[Shannon number]].<ref>{{cite journal | author = [[Claude Shannon]] | title = Programming a Computer for Playing Chess | journal = Philosophical Magazine | volume = 41 | issue = 314 | year = 1950 | page = 4 | url = http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | url-status = dead | archiveurl = https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | archivedate = 2010-07-06 }}</ref> Chess remains unsolved, although extensive study, including work involving the use of supercomputers has created chess end-game [[Endgame tablebase|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 10<sup>120</sup>, 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 [[recursion|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 (mathematics)|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.
一个博弈，用最简单的术语来说，就是两个参与者(左边和右边)可以完成的一系列可能的“动作”。游戏的位置产生的任何移动可以被认为是另一个游戏。这种根据游戏可能转移到其他游戏的观点导致了游戏的递归数学定义，这是21组合博弈论的标准。在这个定义中，每个游戏都有一个符号{ l | r }。是左边玩家可以移动到的游戏位置的集合，r 是右边玩家可以移动到的游戏位置的集合; l 和 r 中的每个位置都被定义为使用相同符号的游戏。
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
以霸气为例，用 A1表示最左边的方格，用 C2表示第二排左边的第三个方格，以此类推。我们使用例如。(D3，D4)代表游戏位置，即一块垂直的多米诺骨牌被放置在游戏的右下角。然后，初始位置可以用组合博弈论表示法描述为
:<math>\{(\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\}.</math>
<math>\{(\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\}.</math>
数学[ a ]1，[ a ]2) ，(数学[ b ]1，[ b ]2) ，[点] | (数学[ a ]1，[ b ]1) ，[ a ]2，[ b ]2] ，[点] . / 数学
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.png]][[Image:20x20square.png]]<br/>
Image:20x20square.pngImage:20x20square.png<br/>
图片: 20x20square. pngImage: 20x20square.png br /
:::[[Image:20x20square.png]]
Image:20x20square.png
图片: 20x20square. png
:<math>\{(\mathrm{A}1,\mathrm{A}2) | (\mathrm{A}1,\mathrm{B}1)\} = \{ \{|\} | \{|\} \}.</math>
<math>\{(\mathrm{A}1,\mathrm{A}2) | (\mathrm{A}1,\mathrm{B}1)\} = \{ \{|\} | \{|\} \}.</math>
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 <nowiki>{|}</nowiki> 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 <nowiki>{|}</nowiki> 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.
上面的游戏描述了一个场景，在这个场景中，任何一个玩家只剩下一步棋，如果任何一个玩家走了那一步棋，那个玩家就赢了。(图中省略了 C3处一个不相关的开平方)每个玩家的移动列表中的 nowiki { | } / nowiki (对应于移动后剩下的单个方块)称为零游戏，实际上可以缩写为0。在零游戏中，两个玩家都没有任何有效的移动，因此，当零游戏出现时，轮到的玩家自动失败。
The type of game in the diagram above also has a simple name; it is called the [[star (game theory)|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 = {|}
0 = {|}
: 1 = {0|}, 2 = {1|}, 3 = {2|}
1 = {0|}, 2 = {1|}, 3 = {2|}
1 = {0|}, 2 = {1|}, 3 = {2|}
: <nowiki>−1 = {|0}, −2 = {|−1}, −3 = {|−2}</nowiki>
<nowiki>−1 = {|0}, −2 = {|−1}, −3 = {|−2}</nowiki>
<nowiki>−1 = {|0}, −2 = {|−1}, −3 = {|−2}</nowiki>
The [[zero game]] is a loss for the first player.
The zero game is a loss for the first player.
零游戏对于第一个玩家来说是一种损失。
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.
数字游戏之和的行为类似于整数，例如3 +-21。
===Star===
''[[star (game theory)|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.
星，写作 x 或{0 | 0} ，是第一个玩家的胜利，因为任何一个玩家必须(如果第一个在游戏中移动)移动到零游戏，因此赢。
: ∗ + ∗ = 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.
衰 x + 0，因为第一个参与者必须把一个 x 分数的副本变成0，然后另一个参与者也必须把另一个 x 分数的副本变成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 game|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.
第一个参与者胜出的所有其他游戏(不管参与者站在哪一边)都被称为 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x。
===Up===
''Up'', written as ↑, is a position in combinatorial game theory.<ref name=winningways>{{cite book |author1=E. Berlekamp |author2=J. H. Conway |author3=R. Guy | title=[[Winning Ways for your Mathematical Plays]] | volume=I | publisher=Academic Press | year=1982 | isbn=0-12-091101-9}}<br/>{{cite book |author1=E. Berlekamp |author2=J. H. Conway |author3=R. Guy | title=Winning Ways for your Mathematical Plays | volume=II | publisher=Academic Press | year=1982 | isbn=0-12-091102-7}}</ref> In standard notation, ↑ = {0|∗}.
Up, written as ↑, is a position in combinatorial game theory. In standard notation, ↑ = {0|∗}.
上面，注明↑ ，是组合博弈论中的一个位置。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.
Up 是严格正的(↑0) ，但是是无穷小的。向上是定义在你的数学游戏的胜利方式。
===Down===
''Down'', written as ↓, is a position in combinatorial game theory.<ref name=winningways /> In standard notation, ↓ = {∗|0}.
Down, written as ↓, is a position in combinatorial game theory. In standard notation, ↓ = {∗|0}.
是组合博弈论的一个职位↓。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.
是严格的负数(↓0) ，但是是无穷小的。在你的数学游戏的胜利方式中定义了向下。
==="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}.
Consider the game {1|−1}.在这个游戏中，两个动作都是制造它们的玩家的优势; 所以这个游戏被称为“热” ; 它比任何小于 -1的数字都要大，小于大于1的数字都要小，而且在两者之间的任何数字都是模糊的。它被写成了1。它可以以预期的方式加到数字上，或者乘以正数; 例如，41{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 [[nimber]]s. The [[Sprague–Grundy theorem]] states that every impartial game is equivalent to a nimber.
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.
一个公正的游戏是这样的，在游戏的每个位置，两个玩家都可以使用相同的动作。例如，尼姆是公正的，因为任何一组可以被一个玩家移除的物体都可以被另一个玩家移除。然而，霸道并不公平，因为一个玩家放置水平的多米诺骨牌，另一个放置垂直的。同样，西洋跳棋也是不公平的，因为玩家拥有不同颜色的棋子。对于任何序数，我们都可以定义一个公正的游戏来概括 Nim，在这个游戏中，任何一个玩家在每次移动时都可以用任何较小的序数来替换这个数字; 这样定义的游戏被称为 nimbers。斯普拉格-格兰迪定理指出，每一个公正的博弈都等价于一个智者。
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和 * ，即按照通常的顺序排列最简单和最小的邻位数。
==See also==
* [[Alpha–beta pruning]], an optimised algorithm for searching the game tree
* [[Backward induction]], reasoning backwards from a final situation
* [[Cooling and heating (combinatorial game theory)]], various transformations of games making them more amenable to the theory
* [[Connection game]], a type of game where players attempt to establish connections
* [[Endgame tablebase]], a database saying how to play endgames
* [[Expectiminimax tree]], an adaptation of a minimax game tree to games with an element of chance
* [[Extensive-form game]], a game tree enriched with payoffs and information available to players
* [[Game classification]], an article discussing ways of classifying games
* [[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
* [[Multi-agent system]], a type of computer system for tackling complex problems
* [[Solving chess]]
* [[Sylver coinage]], a mathematical game of choosing positive integers that are not the sum of non-negative multiples of previously chosen integers
* [[Wythoff's game]], a mathematical game of taking objects from one or two piles
* [[Topological game]], a type of mathematical game played in a topological space
* [[Zugzwang]], being obliged to play when this is disadvantageous
==Notes==
{{Reflist}}
==References==
*{{cite book
| last1 = Albert | first1 = Michael H. | author1-link = Michael H. Albert
| last1 = Albert | first1 = Michael H. | author1-link = Michael H. Albert
作者: 迈克尔 · h · 艾伯特
| last2 = Nowakowski | first2 = Richard J.
| last2 = Nowakowski | first2 = Richard J.
2 | nowaykowski | first2 Richard j.
| last3 = Wolfe | first3 = David
| last3 = Wolfe | first3 = David
3 David
| isbn = 978-1-56881-277-9
| isbn = 978-1-56881-277-9
[国际标准图书馆编号978-1-56881-277-9]
| publisher = A K Peters Ltd
| publisher = A K Peters Ltd
| 出版商 a k Peters Ltd
| title = Lessons in Play: An Introduction to Combinatorial Game Theory
| title = Lessons in Play: An Introduction to Combinatorial Game Theory
游戏中的课程: 组合博弈论入门
| year = 2007}}
| year = 2007}}
2007年开始
*{{cite book
| last = Beck | first = József | author-link = József Beck
| last = Beck | first = József | author-link = József Beck
| last = Beck | first = József | author-link = József Beck
| isbn = 978-0-521-46100-9
| isbn = 978-0-521-46100-9
[国际标准图书编号978-0-521-46100-9]
| publisher = Cambridge University Press
| publisher = Cambridge University Press
出版商剑桥大学出版社
| title = Combinatorial games: tic-tac-toe theory
| title = Combinatorial games: tic-tac-toe theory
组合游戏: 井字游戏理论
| title-link = Combinatorial Games: Tic-Tac-Toe Theory
| title-link = Combinatorial Games: Tic-Tac-Toe Theory
| 题目链接组合游戏: 井字游戏理论
| year = 2008}}
| year = 2008}}
2008年开始
*{{cite book
| last1 = Berlekamp | first1 = E. | author1-link = Elwyn Berlekamp
| last1 = Berlekamp | first1 = E. | author1-link = Elwyn Berlekamp
1 | last1 Berlekamp | first1 e | author1-link Elwyn Berlekamp
| last2 = Conway | first2 = J. H. | author2-link = John Horton Conway
| last2 = Conway | first2 = J. H. | author2-link = John Horton Conway
2 Conway | first2 j. h. | author2-link 约翰·何顿·康威
| last3 = Guy | first3 = R. | author3-link = Richard K. Guy
| last3 = Guy | first3 = R. | author3-link = Richard K. Guy
作者: 理查德 · 盖伊
| isbn = 0-12-091101-9
| isbn = 0-12-091101-9
| isbn 0-12-091101-9
| publisher = Academic Press
| publisher = Academic Press
出版商: 学术出版社
| title = [[Winning Ways for your Mathematical Plays]]: Games in general
| title = Winning Ways for your Mathematical Plays: Games in general
| 题目你的数学游戏的成功之道: 一般的游戏
| year = 1982}} 2nd ed., A K Peters Ltd (2001–2004), {{ISBN|1-56881-130-6}}, {{ISBN|1-56881-142-X}}
| year = 1982}} 2nd ed., A K Peters Ltd (2001–2004), ,
| 1982年}}第二版，a k Peters Ltd (2001-2004) ，,
* {{cite book
| last1 = Berlekamp | first1 = E.
| last1 = Berlekamp | first1 = E.
1 | last1 Berlekamp | first1.
| last2 = Conway | first2 = J. H.
| last2 = Conway | first2 = J. H.
2 Conway | first2 j. h.
| last3 = Guy | first3 = R. | author3-link = Richard K. Guy
| last3 = Guy | first3 = R. | author3-link = Richard K. Guy
作者: 理查德 · 盖伊
| isbn = 0-12-091102-7
| isbn = 0-12-091102-7
| isbn 0-12-091102-7
| publisher = Academic Press
| publisher = Academic Press
出版商: 学术出版社
| title = Winning Ways for your Mathematical Plays: Games in particular
| title = Winning Ways for your Mathematical Plays: Games in particular
| 题目: 数学游戏的制胜之道: 特别是游戏
| url = https://archive.org/details/winningwaysforyo02berl | url-access = registration | year = 1982}} 2nd ed., A K Peters Ltd (2001–2004), {{ISBN|1-56881-143-8}}, {{ISBN|1-56881-144-6}}.
| 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年。
*{{cite book
| last1 = Berlekamp | first1 = Elwyn | author1-link = Elwyn Berlekamp
| last1 = Berlekamp | first1 = Elwyn | author1-link = Elwyn Berlekamp
1 Elwyn | author1-link Elwyn Berlekamp
| last2 = Wolfe | first2 = David | author2-link = David Wolfe (mathematician)
| last2 = Wolfe | first2 = David | author2-link = David Wolfe (mathematician)
大卫 · 沃尔夫(数学家)
| isbn = 1-56881-032-6
| isbn = 1-56881-032-6
1-56881-032-6
| publisher = A K Peters Ltd
| publisher = A K Peters Ltd
| 出版商 a k Peters Ltd
| title = Mathematical Go: Chilling Gets the Last Point
| title = Mathematical Go: Chilling Gets the Last Point
数学行动: 冷却得到最后一分
| url = https://archive.org/details/mathematicalgoch0000berl | url-access = registration | year = 1997}}
| url = https://archive.org/details/mathematicalgoch0000berl | url-access = registration | year = 1997}}
| https://archive.org/details/mathematicalgoch0000berl | url-access registration | year 1997}
*{{cite book
| last = Bewersdorff | first = Jörg | author1-link = Jörg Bewersdorff
| last = Bewersdorff | first = Jörg | author1-link = Jörg Bewersdorff
| last = Bewersdorff | first = Jörg | author1-link = Jörg Bewersdorff
| isbn = 1-56881-210-8
| isbn = 1-56881-210-8
1-56881-210-8
| publisher = A K Peters Ltd
| publisher = A K Peters Ltd
| 出版商 a k Peters Ltd
| title = Luck, Logic and White Lies: The Mathematics of Games
| title = Luck, Logic and White Lies: The Mathematics of Games
运气，逻辑和善意的谎言: 游戏的数学
| year = 2004}} See especially sections 21–26.
| year = 2004}} See especially sections 21–26.
特别是21-26节。
*{{cite book
| last = Conway | first = John Horton | author-link = John Horton Conway
| last = Conway | first = John Horton | author-link = John Horton Conway
最后一个康威 | 第一个 John Horton | 作者链接约翰·何顿·康威
| isbn = 0-12-186350-6
| isbn = 0-12-186350-6
| isbn 0-12-186350-6
| publisher = Academic Press
| publisher = Academic Press
出版商: 学术出版社
| title = [[On Numbers and Games]]
| title = On Numbers and Games
关于数字和游戏
| year = 1976}} 2nd ed., A K Peters Ltd (2001), {{ISBN|1-56881-127-6}}.
| year = 1976}} 2nd ed., A K Peters Ltd (2001), .
| 1976年}}第二版，a k Peters Ltd (2001) ，。
* {{cite book|author1=Robert A. Hearn|author2=Erik D. Demaine|title=Games, Puzzles, and Computation|year=2009|publisher=A K Peters, Ltd.|isbn=978-1-56881-322-6}}
==External links==
*[http://www.ics.uci.edu/~eppstein/cgt/ List of combinatorial game theory links] at the homepage of [[David Eppstein]]
*[https://arxiv.org/pdf/math/0410026 An Introduction to Conway's games and numbers] by Dierk Schleicher and Michael Stoll
*[http://senseis.xmp.net/?CGTPath#toc1 Combinational Game Theory terms summary] by Bill Spight
*[http://www.pims.math.ca/birs/birspages.php?task=displayevent&event_id=05w5048 Combinatorial Game Theory Workshop, Banff International Research Station, June 2005]
{{Game theory}}
{{Authority control}}
[[Category:Combinatorial game theory|*]]
*
*
<noinclude>
<small>This page was moved from [[wikipedia:en:Combinatorial game theory]]. Its edit history can be viewed at [[组合博弈论/edithistory]]</small></noinclude>
[[Category:待整理页面]]