取子游戏_博弈简单分析

《取子游戏_博弈简单分析》由会员分享，可在线阅读，更多相关《取子游戏_博弈简单分析（7页珍藏版）》请在金锄头文库上搜索。

1、一局游戏在两个游戏人之间如下交替进行：游戏从一空堆开始。当轮到一个游戏人时，他可以往堆中加进 1，2，3 或 4 枚硬币。往堆中加进第 100 枚硬币的游戏人为得胜者。确定在这局游戏中是游戏人 A 还是游戏人 B 能够确保取胜。取胜的策略是什么？在学术论坛有博士家园，组合图论论坛确保取足 5 个硬币即可例题：两个人玩移火柴的游戏，桌子上有 1000 根火柴，每个人每次可以拿走 1-7 根火柴，拿走桌子上最后那根火柴的算输，问第一个人第一次要拿多少根火柴才能保证赢7 根。以后对方拿几根，你都要拿够凑足 8 根的数。1000 根和 8 根性质是一样的。从抢 30 到 NIM 游戏的取胜策略（一）倒

2、推法抢 30 是我国民间的一个两人游戏，具有很强的对抗性和娱乐性。抢 30 游戏通常有两种玩法。（1）两人从 1 开始轮流报数，每人每次可报一个数或两个连续的数，谁先报到 30，谁就为胜方。（2）两人从 1 开始轮流报数，每人每次可报一个数或两个连续的数，同时把两个人报出的所有数累加，谁先使这个累加数最先达到 30，谁就为胜方。解决最个问题的一般策略是用倒推法。以（1）为例，要抢到 30，必须抢到 27；要抢到 27，必须抢到 24。如此倒推回去，可得到一系列关键数 30、27、24、21、18、9、6、3。根据以上分析，抢 30 游戏本身并不是一个公平的游戏，初始数和先后顺序已经决定了最后的

3、结果，因为只有后报数者才能抢到 3 的倍数，后报数者有必胜策略。（二）关键因子所有这些关键数都是 3 的倍数。3 是两个报数者年内能够报出的最大数与最小数的和。在类似游戏中，我们把游戏者所能用到的最大数和最小数之和称之为关键因子 k，关键数就是 k 的倍数.。在抢 30 的游戏中，关键因子 k 等于 3。又例如，抢 100 报数游戏中，如果每人可报数为 1 至 9 个连续的自然数，谁先报到 100 谁就是胜利者。这里的关键因子 k 就是可报最大数 9 和可报最小数 1 的和，即 k=10。报数获胜的策略就是：（1）让对方先报数；（2）每次报数为关键因子减去对方所报数。这样自己每次所报数都是关键

4、数。如果对方一定要先报，你只能期待对方不懂策略或者大意出错了。（三）不平衡因子在上述的抢 30 或者抢 100 的游戏中，最后数 30 是关键因子 3 的整数倍，最后数 100 是关键因子 10 的整数倍。我们可以把这样的游戏称为平衡游戏，也就是最后报数与关键因子相除余数为 0。如果最后报数与关键因子相除有余数，这个游戏就可以称为不平衡游戏，其余数就是不平衡因子。抢数不平衡游戏也是不公平的游戏，先报数者有必胜策略。先报数者的获胜策略就是先消除不平衡因子，使其变成一个平衡游戏，先报数者随后就成为平衡游戏的后报数者。例如，在抢 30 游戏中，两人从 1 开始轮流报数，每人每次可报 1 到 3 个连

5、续的数，谁先报到 30，谁就为胜方。在这里，关键因子是 4，不平衡因子是2。又例如，抢 100 报数游戏中，如果每人可报数为 1 至 10 个连续的自然数，谁先报到 100 谁就是胜利者。在这里，关键因子是 11，不平衡因子是 1。在不平衡游戏中，如果先报数者不懂得游戏策略，懂得这个策略的后报数者需要不断计算不平衡因子，以便最后获胜。（四）更多例子报数游戏里的最后数都是些比较小的数，因此用倒推法比较容易得到策略。当我们把数变得大一些的时候，就变成了小学奥赛题。如果掌握上述讨论中的关键因子和不平衡因子的计算，奥数题也变得迎刃而解了。下面就是两个奥数例题。（1）2008 个空格子排成一排，第一格放

6、有一个棋子。两人做游戏，轮流移动这枚棋子。每个人每次可前移 1 到 5 个格子，谁先把棋子移到最后一格，谁就是获胜者。问怎样的策略才能保证获胜。（2）桌上放着一堆火柴，共有 5000 根。两个人轮流从中取火柴，每人每次取的火柴根数为 1 到 8 根，谁取了最后一根谁就输。问怎样的策略才能保证获胜。（五）进一步扩展到 NIM 游戏抢 30 的游戏是中国 NIM 游戏（也叫筹码游戏）的一种特例。NIM 游戏的一种经典表述为：有 n 堆火柴，每堆各有若干根。两人轮流取出火柴，每次取出的根数不限但至少取 1 根，每次也只能从 1 堆里取火柴。谁最后把火柴取完，谁就是获胜者。问如何才能保证获胜。获胜策略

7、已由美国数学家 C.L.Bouton 分析完成，用到的是二进制和平衡状态概念。其结论是：如果一开始火柴的总根数转化成二进制后各位数上的数字和都是偶数时，则是平衡状态，后取者必胜。最简单的平衡态是（1，1），即 2 堆火柴，每堆各 1 根。如果开始时火柴的状态处于不平衡状态，先取者必胜，其策略是取完后使火柴根数保持为平衡状态。最简单的不平衡态是（1），即 1 根火柴。例如，2 堆火柴数都为 2 根，二进制记为（10，10），各位数之和为 20，这是一个平衡态，则后取者必胜。3 堆火柴数分别为 1 根、2 根、1 根，二进制记为（1，10，1），各位数之和为 12，这不是一个平衡态。先取者先取掉中

8、间一堆 2 根火柴，变成平衡状态（1，1），则先取者必胜。下面的一道例题，可以用来练习 NIM 游戏的上述策略：有 3 堆火柴，根数分别为 12、9、6.。甲乙两人轮番从其中一堆中取出 1 根或几根火柴，取到最后一根者获胜。先取者还是后取者有必胜策略，如何取胜？Nim 游戏Nim 游 戏 是 博 弈 论 中 最 经 典 的 模 型 （ 之 一 ？ ） ， 它 又 有 着 十 分 简 单 的 规 则 和 无 比 优美 的 结 论Nim 游 戏 是 组 合 游 戏 (Combinatorial Games)的 一 种 ， 准 确 来 说 ， 属 于 “Impartial Combinatorial

9、 Games”（ 以 下 简 称 ICG） 。 满 足 以 下 条 件 的 游 戏 是 ICG（ 可 能 不 太严 谨 ） ： 1、 有 两 名 选 手 ； 2、 两 名 选 手 交 替 对 游 戏 进 行 移 动 (move)， 每 次 一 步 ， 选手 可 以 在 （ 一 般 而 言 ） 有 限 的 合 法 移 动 集 合 中 任 选 一 种 进 行 移 动 ； 3、 对 于 游 戏 的 任何 一 种 可 能 的 局 面 ， 合 法 的 移 动 集 合 只 取 决 于 这 个 局 面 本 身 ， 不 取 决 于 轮 到 哪 名 选 手 操作 、 以 前 的 任 何 操 作 、 骰 子 的

10、点 数 或 者 其 它 什 么 因 素 ； 4、 如 果 轮 到 某 名 选 手 移 动 ，且 这 个 局 面 的 合 法 的 移 动 集 合 为 空 （ 也 就 是 说 此 时 无 法 进 行 移 动 ） ， 则 这 名 选 手 负 。 根据 这 个 定 义 ， 很 多 日 常 的 游 戏 并 非 ICG。 例 如 象 棋 就 不 满 足 条 件 3， 因 为 红 方 只 能 移动 红 子 ， 黑 方 只 能 移 动 黑 子 ， 合 法 的 移 动 集 合 取 决 于 轮 到 哪 名 选 手 操 作 。 通 常 的 Nim 游 戏 的 定 义 是 这 样 的 ： 有 若 干 堆 石 子 ，

11、每 堆 石 子 的 数 量 都 是 有 限 的 ，合 法 的 移 动 是 “选 择 一 堆 石 子 并 拿 走 若 干 颗 （ 不 能 不 拿 ） ”， 如 果 轮 到 某 个 人 时 所 有 的石 子 堆 都 已 经 被 拿 空 了 ， 则 判 负 （ 因 为 他 此 刻 没 有 任 何 合 法 的 移 动 ） 。这 游 戏 看 上 去 有 点 复 杂 ， 先 从 简 单 情 况 开 始 研 究 吧 。 如 果 轮 到 你 的 时 候 ， 只 剩 下 一堆 石 子 ， 那 么 此 时 的 必 胜 策 略 肯 定 是 把 这 堆 石 子 全 部 拿 完 一 颗 也 不 给 对 手 剩 ， 然

12、后 对 手就 输 了 。 如 果 剩 下 两 堆 不 相 等 的 石 子 ， 必 胜 策 略 是 通 过 取 多 的 一 堆 的 石 子 将 两 堆 石 子 变得 相 等 ， 以 后 如 果 对 手 在 某 一 堆 里 拿 若 干 颗 ， 你 就 可 以 在 另 一 堆 中 拿 同 样 多 的 颗 数 ， 直至 胜 利 。 如 果 你 面 对 的 是 两 堆 相 等 的 石 子 ， 那 么 此 时 你 是 没 有 任 何 必 胜 策 略 的 ， 反 而 对手 可 以 遵 循 上 面 的 策 略 保 证 必 胜 。 如 果 是 三 堆 石 子 好 像 已 经 很 难 分 析 了 ， 看 来 我们

13、 必 须 要 借 助 一 些 其 它 好 用 的 （ 最 好 是 程 式 化 的 ） 分 析 方 法 了 ， 或 者 说 ， 我 们 最 好 能 够设 计 出 一 种 在 有 必 胜 策 略 时 就 能 找 到 必 胜 策 略 的 算 法 。定 义 P-position 和 N-position， 其 中 P 代 表 Previous， N 代 表 Next。 直 观 的说 ， 上 一 次 move 的 人 有 必 胜 策 略 的 局 面 是 P-position， 也 就 是 “后 手 可 保 证 必 胜 ”或者 “先 手 必 败 ”， 现 在 轮 到 move 的 人 有 必 胜 策 略

14、的 局 面 是 N-position， 也 就 是 “先 手 可保 证 必 胜 ”。 更 严 谨 的 定 义 是 ： 1.无 法 进 行 任 何 移 动 的 局 面 （ 也 就 是 terminal position） 是 P-position； 2.可 以 移 动 到 P-position 的 局 面 是 N-position； 3.所 有移 动 都 导 致 N-position 的 局 面 是 P-position。按 照 这 个 定 义 ， 如 果 局 面 不 可 能 重 现 ， 或 者 说 positions 的 集 合 可 以 进 行 拓 扑 排序 ， 那 么 每 个 positio

15、n 或 者 是 P-position 或 者 是 N-position， 而 且 可 以 通 过 定 义 计 算出 来 。以 Nim 游 戏 为 例 来 进 行 一 下 计 算 。 比 如 说 我 刚 才 说 当 只 有 两 堆 石 子 且 两 堆 石 子 数量 相 等 时 后 手 有 必 胜 策 略 ， 也 就 是 这 是 一 个 P-position， 下 面 我 们 依 靠 定 义 证 明 一 下(3,3)是 一 个 P 是 一 个 P 是 一 个 P-position。 首 先 (3,3)的 子 局 面 （ 也 就 是 通 过 合 法 移 动可 以 导 致 的 局 面 ） 有 (0,3

16、)(1,3)(2,3)（ 显 然 交 换 石 子 堆 的 位 置 不 影 响 其 性 质 ， 所 以 把(x,y)和 (y,x)看 成 同 一 种 局 面 ） ， 只 需 要 计 算 出 这 三 种 局 面 的 性 质 就 可 以 了 。 (0,3)的子 局 面 有 (0,0)、 (0,1)、 (0,2)， 其 中 (0,0)显 然 是 P-position， 所 以 (0,3)是 N-position（ 只 要 找 到 一 个 是 P-position 的 子 局 面 就 能 说 明 是 N-position） 。 (1,3)的 后继 中 (1,1)是 P-position（ 因 为 (1,1)的 唯 一 子 局 面 (0,1)是 N-position） ， 所 以 (1,3)也是 N-position。 同 样 可 以 证 明 (2,3)是 N-position。 所 以 (3,3)的 所 有 子 局 面 都 是 N-position， 它 就 是 P-position。 通 过 一 点 简 单 的 数 学 归 纳 ， 可 以 严 格