什么是组合博弈论 | 集智百科

“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！

本文是对集智百科中“组合博弈论”词条的摘录，参考资料及相关词条请参阅百科词条原文。

本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！

一、历史

二、例子

三、总揽

四、游戏缩写

五、尼姆数

六、编者推荐

七、百科项目志愿者招募

组合博弈论 Combinatorial game theory是数学和理论计算机科学的一个分支，主要研究具有完全信息的序贯博弈。研究很大程度上局限于双人游戏，在这种游戏中，玩家以规定的方式或招数轮流变化，以达到规定的制胜条件。CGT传统上并不研究机会博弈，也不研究那些使用不完全或不完整信息的博弈，而是倾向于那些提供完全信息的博弈，在这种博弈中，双方都知道博弈的状态和可用的招数。然而，随着数学技术的进步，可以用数学方法分析的博弈类型不断扩展，因此该领域的边界也在不断变化。学者们通常会在论文的开头定义他们所说的 “博弈 “，这些定义经常随着他们所分析的特定博弈而变化，并不代表该领域的全部范围。

组合游戏包括众所周知的游戏，如国际象棋、跳棋、围棋等，这些游戏被认为是非琐碎的，而井字棋则被认为是 “容易解决 “的琐碎游戏。一些组合游戏也可能有一个无限制的游戏区域，如无限棋。在CGT中，这些游戏和其他游戏中的棋步被表示为博弈树。

组合游戏还包括单人组合谜题，如数独游戏，以及无人自动机，如康威的生命游戏(虽然在最严格的定义中，“游戏”可以说需要一个以上参与者，因此命名为“拼图”和“自动机”。)

博弈论通常包括机会博弈、不完全知识博弈和参与者可以同时移动的博弈，它们往往代表现实生活中的决策情况。

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

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

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

数学家们在组合博弈论研讨会上玩Konane

历史

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

在20世纪60年代，Elwyn R. Berlekamp，John h. Conway和Richard k. Guy 共同提出了一个党派博弈理论，在这个理论中，放宽了一个游戏可供两个玩家使用的要求。他们的研究结果发表在1982年的《数学游戏的获胜方法》一书中。但是，关于这一主题的第一部著作是Conway于1976年出版的《数与游戏 On Numbers and Games》（也称为ONAG），该书引入了超现实数的概念以及对游戏。《数字与游戏》也是Berlekamp，Conway和Guy之间合作的成果。

按照惯例，组合游戏通常是一种形式，即一个玩家在另一方没有剩余移动时获胜。将只有两个可能结果的任何有限博弈转换为适用此约定的等效博弈是很容易的。组合博弈理论中最重要的概念之一是两个博弈之和，即每个玩家可以选择在一个博弈中或另一个博弈中的任何一个时刻移动，当对手在其中任何一个博弈中没有移动时，玩家获胜。这种组合游戏的方式导致了丰富而强大的数学结构。

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

例子

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

Blue-Red Hackenbush – 在有限层面上，这种党派组合游戏允许构造其值是二元有理数的游戏。在无限水平上，它允许构造所有实值，以及许多属于超现实数类的无限值。
Blue-Red-Green Hackenbush – 允许附加的游戏值不是传统意义上的数字，例如星（博弈论）。
Toads and Frogs – 允许各种游戏值。与大多数其他游戏不同，一个位置很容易用一串短字符来表示。
Domineering – 各种有趣的棋局，比如热棋，都会出现在主宰局面中，因为有时有下棋的动机，有时没有。这允许讨论一盘棋的温度（博弈论）。
Nim – 一个公正的游戏。这使得nimber的构建成为可能。(它也可被视为Blue-Red-Green Hackenbush中仅有绿色的特例)。

经典的围棋游戏 Go对早期的组合博弈论影响很大，Berlekamp 和 Wolfe 随后为其发展出了一套终局和温度理论(见参考文献)。有了这些，他们就能够构建出合理的围棋终局局面，从中可以给围棋高手一个选择阵营的机会，然后以任何一种方式击败他们。

在组合博弈论的背景下研究的另一个游戏是国际象棋。1953年，艾伦·图灵写道：“如果可以用英语非常明确地解释，并在需要时借助数学符号来解释如何进行计算，那么始终可以编写任何数字计算机来进行计算，前提是存储容量足够。”在1950年的一篇论文中，Claude Shannon 估计国际象棋博弈树复杂度的下限为10120，今天这被称为香农数 Shannon number。国际象棋仍然是无解的，尽管广泛的研究，包括涉及使用超级计算机的工作已经创建了国际象棋终局表库，它显示了所有七个或更少棋子的终局的完美结果。与国际象棋相比，无限棋比国际象棋有更大的组合复杂性(除非只研究有限的终局，或者只研究有少量棋子的组成局面)。

总揽

一个游戏，用最简单的说法，就是两个参与者(左边和右边)可以完成的一系列可能的“动作”。游戏的位置产生的任何移动可以被认为是另一个游戏。这种根据游戏可能转移到其他游戏的观点导致了组合博弈论中标准的递归数学定义。在这个定义中，每个游戏都有{L|R}的符号。L是左边玩家可以移动到的游戏位置的集合，R 是右边玩家可以移动到的游戏位置的集合; L和 R 中的每个位置都用同样的记号定义为一个游戏。

以Domineering为例，在四乘四棋盘的十六个棋格中，分别用A1代表最左上角的棋格，C2代表第二行从上到下左边的第三个棋格，以此类推。我们用如(D3，D4)代表在右下角放置了一张竖直的多米诺骨牌的游戏位置。那么，初始位置可以用组合博弈论的符号描述为

在标准的Cross-Cram游戏中，玩家交替轮换，但这种交替是由组合博弈论的定义隐性处理的，而不是被编码在游戏状态中。

上面的游戏描述了这样一种情形：任何一方只剩下一步棋，如果任何一方下了这一步棋，该一方就获胜。(图中省略了C3处无关的空位。)每个棋手棋谱中的 {|} (对应于下棋后剩余的单个方格)称为零棋局，实际上可以缩写为0。在零棋局中，双方都没有任何有效棋步；因此，当零棋局出现时，轮到自己的玩家自动输掉。

上图中的游戏类型也有一个简单的名字，它叫做星棋 star game，也可以缩写为∗。在星型棋局中，唯一有效的棋步是导致零棋，也就是说，在星型棋局中，谁的回合出现，谁就自动获胜。

另一种类型的游戏，不存在于霸气中，是一种循环游戏，在这种游戏中，左或右的有效举动都是一种游戏，然后可以导致回到第一个游戏。例如，跳棋，当其中一个棋子晋升时，就会变得很循环，因为它可以在两个或更多的格子之间无休止地循环。不具备这种棋步的棋局称为无环棋。

游戏缩写

数字

数字代表自由移动的次数，或者某个特定玩家的移动优势。按照惯例，正数代表左边的优势，而负数代表右边的优势。它们是递归定义的，0是基本情况。

0 = {|}

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

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

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

数字游戏之和的行为类似于整数，例如3 + −2 = 1。

星

星，写作∗或{0|0} ，是第一个玩家的胜利，因为任何一个玩家必须(如果第一个在游戏中移动)移动到零局，因此先手赢。

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

游戏 ∗ 既不是正数，也不是负数；它和所有其他最先获胜的游戏（无论玩家在哪一方）都被称为与0模糊或混淆的游戏；象征性地，我们写成∗ || 0。

上

上，写成↑，是组合博弈论中的一个位置。在标准符号中，↑={0|∗}。

−↑ = ↓ (下)

上是严格的正数（↑ > 0），但却是无穷小的。上的定义见《数学游戏的赢家 Winning Ways for your Mathematical Plays》。

下

下，写成↓，是组合博弈论中的一个位置。在标准符号中，↓={∗|0}。

−↓ = ↑ (上)

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

热门游戏

考虑游戏{1|−1}.在这盘棋中，两步棋都对下棋者有利，所以说这盘棋是 “热棋”；它大于小于-1的任何数字，小于大于1的任何数字，而模糊的是中间的任何数字。它的写法是±1.它可以与数字相加，也可以与正数相乘，按预期的方式进行；例如，4 ± 1 = {5|3}。

尼姆数 Nimbers

公正的游戏是指在游戏中的每个位置上，双方都可以走同样的移动路线。例如，Nim是公正的，因为一个玩家可以移走的任何一组物体都可以被另一个玩家移走。然而，霸气不是公正的，因为一个玩家放置水平的骨牌，而另一个玩家放置垂直的骨牌。同样跳棋也不是公正的，因为玩家拥有不同颜色的棋子。对于任何序数，我们可以定义一个公平的广义Nim游戏。在这个游戏中，每一个玩家都可以用任何更小的序数来代替这个数字；以这种方式定义的游戏被称为尼姆数 nimber。Sprague-Grundy定理指出，每一个公正的游戏都等同于Nim游戏。

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