Nim游戏

给定 (n) 堆石子，第 (i) 堆石子有 (A_i) 个石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿),最后无法进行操作的人视为失败。

若两人均为巨佬，采用最优策略，先手是否必胜。

这种游戏被称作Nim博弈。游戏过程中面临的状态叫做局面。若在某一局面下无论采取任何行动，都会失败，则称该局面必败。若在某一局面下，能通过采取某一行动使得对手陷入必败局面，则优先采取该行动，这种局面就被称作必胜。在讨论博弈问题时，都只考虑双方都是巨佬的情况，都会采取对于自身的最优策略。Nim博弈不存在平局，只有先手必胜和先手必败两种情况。

定理：Nim博弈先手必胜,当且仅当(A_1 oplus A_2 oplus ldots oplus A_n ne 0) 。（注：$oplus $为异或符号）

证明如下：

首先，对于最终必败局面，即所有物品都被取完，而此时轮到自己行动时。这时(A_1, A_2, ldots, A_n = 0), 显然有 (A_1 oplus A_2 oplus ldots oplus A_n = 0)。

在博弈过程中，任何局面显然都有两种情况：$A_1 oplus A_2 oplus ldots oplus A_n ne 0 $ 或 (A_1 oplus A_2 oplus ldots oplus A_n = 0).

1. 当(A_1 oplus A_2 oplus ldots oplus A_n ne 0) 时, 设此时(A_1 oplus A_2 oplus ldots oplus A_n = x(x > 0))。

该情况一定能够通过某种操作况变为情况二。

设将 (x) 的二进制表示下最高位的 (1) 在第 (k) 位。显然， (A_1, A_2, ldots, A_n) 中必然至少有一个数 (A_i) 的二进制表示下第 (k) 位也为 (1)。 显然有(A_i oplus x < A_i), 于是 (A_i - (A_i oplus x) > 0) ,因此，我们在该局面下将第 (i) 堆石子取走 (A_i - (A_i oplus x))个石子，第 (i) 堆石子的个数就为 (A_i - (A_i - (A_i oplus x)) = A_i oplus x) ，将其记为(A_i') 。此时，所有的石子的异或值为：

[begin{aligned} A_1 oplus A_2 oplus ldots oplus A_i' oplus ldots oplus A_n &= A_1 oplus A_2 oplus ldots oplus (A_i oplus x)oplus A_n \ &=A_1 oplus A_2 oplus ldots oplus A_i oplus ldots oplus A_n oplus x \ &= x oplus x \ &= 0 end{aligned} ]

这样，我们就成功证明了第一种情况一定能变成第二种情况。

2. 当(A_1 oplus A_2 oplus ldots oplus A_n = 0) 时

在该情况下，无论进行任何操作，之后都会有(A_1 oplus A_2 oplus ldots oplus A_n ne 0) ,该情况在玩家操作后必然会变成情况一。 可以使用反证法来证明：

设该玩家在第 (i) 堆取走石子，(A_i) 被取成 (A_i') ， 且 (A_1 oplus A_2 oplus ldots oplus A_i' ldots oplus A_n = 0) 。将该等式与 (A_1 oplus A_2 oplus ldots oplus A_n = 0) 异或得：

[begin{aligned} A_1 oplus A_2 oplus ldots oplus A_i' ldots oplus A_n oplus (A_1 oplus A_2 oplus ldots oplus A_n) = 0 \ end{aligned} ]

[A_i' oplus A_i = 0 ]

这就反映出， (A_i'= A_i)，表明一个石子都没取，与“不能不拿”的题意矛盾。

因此，当先手(A_1 oplus A_2 oplus ldots oplus A_n ne 0)时，为情况一，该玩家一定能将该情况变为情况二，而后手无论如何操作，都会将情况二又变回情况一，于是先手又继续将情况一变为情况二......就这样，先手面临的一定会是情况一，后手永远面临情况二，而石子的总数不断减少，所以最后后手一定会面临最终必败局面。因此，Nim博弈先手必胜,当且仅当(A_1 oplus A_2 oplus ldots oplus A_n ne 0)

公平组合游戏ICG

若一个游戏满足：

  1. 由2名玩家交替行动；
  2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
  3. 不能行动的玩家判负。

则称该游戏为公平组合游戏。

NIM博弈也属于公平组合游戏。常见的棋类游戏例如围棋都不属于公平组合游戏，比如围棋，因为玩家只能落黑子或白子，不符合条件2和3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称作有向图游戏。

任何一个公平组合游戏都可以化为有向图游戏。把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设 (S) 表示一个自然数集合。定义 (text{mex}(S))为求出不属于集合 (S) 的最小自然数的运算，即：

[text{mex}(S) = underset{x in mathbb{N}, x notin S}{min} left{ x right} ]

SG函数

在有向图游戏中，对于每个节点 (x) 。 设从 (x) 出发共有 (k) 条有向边，分别到达节点 (y_1, y_2, ldots, y_k) , 定义 (text{SG}(x)) 为 (x) 的后继节点 (y_1, y_2, ldots, y_k) 的 (text{SG}) 函数值构成的集合再执行 (text{mex}) 运算的结果，即：

[text{SG}(x) = text{mex}( left{text{SG}(y_1), text{SG}(y_2), ldots, text{SG}(y_k) right}) ]

特别地，整个有向图游戏 (G) 的 (text{SG}) 函数值被定义为有向图游戏的起点 (s) 的 (text{SG}) 函数值， 即(text{SG}(G) = text{SG}(s)) 。

有向图游戏的和

设 (G_1, G_2, ldots, G_m) 是 (m) 个有向图游戏。定义有向图游戏 (G) ， 它的行动规则是任选某个有向图游戏 (G_i) , 并在 (G_i)上行动一步。 (G) 被称为有向图游戏 (G_1, G_2, ldots, G_m)的和。

有向图游戏的和的 (text{SG}) 函数值等于它包含的各个子游戏 (text{SG}) 函数值的异或和，即：

[text{SG}(G) = text{SG}(G_1) oplus text{SG}(G_2) oplus ldots oplus text{SG}(G_m) ]

定理：

有向图游戏的某个局面必胜，当且仅当该局面对应节点的 (text{SG}) 函数值大于 (0) 。

有向图游戏的某个局面必输，当且仅当该局面对应节点的 (text{SG}) 函数值等于 (0) 。

可以这样理解：

  1. 对于一个没有出边的节点，即最终必败局面，它的 (text{SG}) 函数值为 (0) 。

  2. 对于一个 (text{SG}) 函数值大于 (0) 的节点，对应必胜局面，表明它的所有后继节点中必然有一个节点 (text{SG}) 函数值为 (0) 。

  3. 对于一个 (text{SG}) 函数值等于 (0) 且有出边的节点，该节点对应必败局面，它的所有后继节点的 (text{SG}) 函数值都大于 (0) ，对应必胜节点。

因此，这里的2、3种节点，就类似于上面Nim游戏的1、2种情况，用类似的思路即可证明上述定理。

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/yduck/p/17607467.html

标签： 算法 数据结构
你还没有登录，请先登录或注册！
  • 还没有人评论，欢迎说说您的想法！

相关课程

人工智能入门
5328 9.8元 98元 1折
英特尔 OpenCV 初级认证课程
8879 0元 限免