组合博弈-获胜位置

当分析有限的<一个href="//www.parkandroid.com/wiki/combinatorial-games-definition/" class="wiki_link" title="组合游戏" target="_blank">组合游戏，其中两个关键问题是:

1） 如果两名球员都发挥最佳，谁会赢？
2） 什么样的游戏策略是“最优的”？

也就是说，考虑到游戏的当前状态（或“位置”），问题是轮到移动的玩家是否可以强制获胜，如果是，必须采取什么样的移动才能做到这一点。一些著名的组合对策已经被广泛研究，包括<一个href="//www.parkandroid.com/wiki/chess-puzzles/" class="wiki_link" title="国际象棋" target="_blank">国际象棋，<一个href="//www.parkandroid.com/wiki/nim/" class="wiki_link" title="尼姆" target="_blank">尼姆，及<一个href="//www.parkandroid.com/wiki/tic-tac-toe/" class="wiki_link" title="井字游戏" target="_blank">井字游戏．

在这种情况下，解决问题的技巧通常是<一个href="//www.parkandroid.com/wiki/induction/" class="wiki_link" title="归纳推理" target="_blank">归纳推理．换句话说，从分析游戏的简单版本开始，了解谁在哪个位置获胜，然后将结果扩展到整个游戏中。这里有一个基本的例子。

在双人游戏中，从一堆 $n$石头，玩家轮流选择移除 $1、2、3,$或 $4$从那堆石头中取出来。从那堆石头中取出最后一块的玩家就是赢家。的 $n$第二个玩家能保证他或她会赢吗？

---

解决方案:从小案例开始。如果桩中包含 $4 \勒$石头，然后第一个玩家立即赢得全部。但如果这堆包含 $5$石头，第二名玩家可以赢，因为在第一名玩家移走一些石头后，第二名玩家可以移走其余的石头。

但是如果有的话 $6、7、8日$或 $9$石头，第一个玩家可以通过离开而获胜 $5$,因为 $5$对于移动的玩家来说是一个失败的位置。在这里，我们以我们对早期职位的了解为基础进行归纳总结。同样地， $10$是第二名选手的胜利。

通常在这一点上，最简单的方法是对一般情况作出有根据的猜测，然后解释为什么猜测是正确的(因为推理是归纳的，证明也经常使用归纳)。在这里，正确的说法似乎是 $5$都是第2个玩家的胜利，其他的都是第1个玩家的胜利。这可以用归纳法来证明。基本情况已经完成了。现在假设这个结论是正确的 $n\le 5k$. 对于 $n=5k+1,5k+2,5k+3,5k+4$第一个玩家赢了 $1、2、3、4$分别为 $n = 5 k + 5$第一个玩家不得不离开 $5 k + 1, 5 k + 2, 5 k + 3,$或 $5 k + 4$，轮到谁的玩家获胜。所以这个结论是正确的 $n\le 5（k+1）$，它建立了归纳步骤。 $\方格$

为了进一步检查你的理解，考虑下面这个例子，它是介绍中的例子的扩展:

记住上面的例子，我们可以使用以下3条规则来将所有的职位分类为赢得或失去，这取决于移动的玩家最终是赢还是输，双方都有完美的玩法。

1. 空位游戏（没有移动的游戏）是一个失败的位置。
2. 一个职位就是一份工作赢如果单次移动可从此位置获得的至少一个位置为丢失位置。
3. 一个职位就是一份工作失利如果每一个可以从这个位置通过单步移动获得的位置都是一个获胜的位置。

由于游戏的确定性，我们可以通过反向归纳法证明，每个位置都可以唯一地表示为赢或输的位置。规则2也告诉我们，一般来说，当我们处于一个胜利的位置时，如何以最佳方式移动：我们移动到一个失败的位置。因此，这为我们提供了一个非常简单的算法来理解这些游戏是如何玩的：

组合游戏的问题解决策略：
1.分析简单的起始位置，建立基本的赢和输的位置库。
2.根据这些例子，推测输赢位置的一般描述。
3.证明这个猜想（通常通过归纳法）：证明一个赢的位置总是可以移动到一个输的位置，而一个输的位置只能移动到一个赢的位置。

下面是另一个使用这个术语和策略的例子。

一个双人游戏是在一个 $5 \ * 5$网格。一个标记从网格的左下角开始。在每个回合中，玩家可以将代币向右移动1或2个单位，或移动到上述一行中最左边的方格。最后一个能移动的玩家获胜。确定令牌的哪些位置是赢的位置，哪些是输的位置。

---

解决方案:很容易确定顶部行的赢和输位置，因为唯一的选择是向右移动1或2个位置。这就给出了第一行的W L W W L，因为这一行中的第一个位置是一个胜利的位置，所以从前一行移动到这里是没有好处的。这意味着下一行的最后一个位置也输了，整行的格局将与这一行相同。该模式将继续适用于所有5行，因此，如果令牌位于 $1 ^ \文本圣}{3 ^ {rd} \文本,$或 $4^\text{th}$列，这是一个获胜的位置，如果它是在 $2^\text{nd}$或 $5^\text{th}$列，它输了。 $_ \广场$

奖金:将这个问题推广到更大的网格。一张桌子上有多少个获胜的位置 $k次n$网格?

Chomp是一种公正的组合博弈，其规则如下 $m \ n$巧克力棒( $mn\ge 2$)被切割成 $1 \ * 1$方格。爱丽丝和鲍勃轮流从右上角吃巧克力棒:他们选一个方块，连同上面和右边的所有方块一起吃(包括正上方和正右侧的方块)。每个玩家必须在每个回合吃至少一个方块。吃左下角方块的人输了。

Chomp（未使用最佳策略）

案例1:用一排咀嚼。

Alice(第一个玩家)吃掉了所有的方块，只剩下左下角的方块。

案例2：两排咀嚼。

表示Chomp游戏中间的一个两行棒子 $（a、b）$在哪里 $一个$是顶行中的方块数，并且 $b$下面一行的方块数。所以 $一个\ b$. 这种说法是，损失的头寸正是如此 $(+ 1)$．

看到这一点 $(+ 1)$如果失败了，我们继续归纳。很容易看出这一点 $(1、2)$(或 $(0,1)$)是失去。假设爱丽丝从 $(+ 1)$．她有两个选择。如果她咬的只是最上面的一排，要减少到 $(c + 1)$， Bob可以简化为 $（c，c+1）$而Alice在归纳法上输了。如果她把两排都咬了，就会缩小成一个长方形 $(c, c)$， Bob可以简化为 $（c-1，c）$，这对Alice来说是失败的。

很明显，这些是唯一输掉的位置:如果爱丽丝从其他位置移动，她可以咬咬杆来减少 $(+ 1)$所以爱丽丝赢了。特别是，从两行矩形开始，Alice只吃右上角的正方形就赢了。

案例3：有三行(或更多)的Chomp。

即使是三排嘴也是一个复杂的问题，是当代研究的主题。Alice的最佳第一步（作为列数的函数）并不明显，但事实证明，对于任何非平凡的矩形起始形状，Alice必须始终获胜。

这是可以证明的<圣rong>第一个玩家总是赢的在最优策略下，即使一般的游戏策略是未知的。

为了说明这一点，假设一个特定的矩形条是第二个玩家Bob的胜利。如果Alice开始只吃右上角，Bob一定有一个毁灭性的举动，让Alice处于失败的位置。但爱丽丝本可以这么做的这样一来，鲍勃也会处于同样的劣势。这是一个矛盾。

这是一个教科书上的非建设性证明的例子：很明显，第一个玩家必须获胜，但该证明几乎没有给出正确的获胜招式。

• 组合对策-定义
• 棋局
• 尼姆
• 井字过三关
• 递归回溯
• K级思维