最新要闻

广告

手机

顺络电子：董事长部分股权办理股票质押业务

顺络电子：董事长部分股权办理股票质押业务

 深圳7月二手住宅成交2259套，中介称近期咨询客户开始增加

深圳7月二手住宅成交2259套，中介称近期咨询客户开始增加

家电

  1. 首页
  2. 移动通信
  3. 内容

博弈论学习笔记

来源：博客园

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种情况，用类似的思路即可证明上述定理。

关键词：