组合博弈论|集1（导论）

组合博弈是两人博弈 完美信息 而且没有机会移动（没有像掷硬币这样的随机化影响游戏）。这些游戏有胜负或平局的结果，由一组位置决定，包括初始位置，以及轮到谁移动。游戏从一个位置移动到另一个位置，玩家通常交替移动，直到到达终点位置。终端位置是不可能移动的位置。然后其中一名选手被宣布为赢家，另一名选手被宣布为输家。或者有一个平局（取决于组合游戏的规则，游戏可能会以平局结束。关于组合游戏，唯一可以说明的是，游戏应该在某个点结束，不应该陷入循环。为了防止像国际象棋这样的游戏中出现这种循环情况（考虑两个玩家只是将他们的皇后从一个地方来回移动到另一个地方的情况），实际上有一个“50步规则”，根据该规则，如果每个玩家的最后50步都完成了，没有任何棋子移动，也没有任何抓捕，则游戏被视为平局。资料来源： Stackexchange ]

另一方面，博弈论一般包括机会博弈、不完全知识博弈和玩家可以同时移动的博弈。

组合博弈论（CGT）的特点是编码部分相对较小且简单。博弈论问题的关键在于隐藏的观察，有时很难找到。

国际象棋、尼姆游戏、井字游戏都属于组合博弈论的范畴。

我们可以将这些游戏分为两类，如下所示：

它们之间的区别在于 公正的游戏 任何位置的所有可能动作都是相同的 相同的 对于球员，而在 党派游戏 所有球员的动作都是 不一样 .

考虑下面的游戏： 给定若干堆，其中每一堆包含一定数量的石头/硬币。在每一回合中，玩家选择一堆，并从该堆中移除任意数量的石头（至少一块）。不能移动的玩家将被视为输掉比赛（即，拿走最后一块石头的玩家为赢家）。 从上述游戏规则中可以清楚地看出，两位玩家的动作是相同的。一名球员不受另一名球员的限制。这种游戏被认为是公正的。 上述游戏因其名字而闻名- 尼姆的游戏 这将在下一节中讨论。

与上述游戏相比，让我们举一个 国际象棋 .在这个游戏中，一个玩家只能移动黑色棋子，另一个玩家只能移动白色棋子。因此，这两名球员都受到限制。他们的一套动作是不同的，因此这样的游戏被归类为 党派游戏 .

党派博弈比公正博弈更难分析 斯普拉格-格伦迪定理 失败。

在接下来的部分中，我们将主要看到关于公平博弈的内容，比如——尼姆博弈及其变体、斯普拉格-格伦迪定理等等。

练习： 读者可以尝试解决以下简单的组合博弈论问题。 自行车赛 巧克力游戏

资料来源： http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf https://en.wikipedia.org/wiki/Combinatorial_game_theory https://en.wikipedia.org/wiki/Impartial_game https://en.wikipedia.org/wiki/Partisan_game

本文由 拉希特·贝尔瓦里亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论