博弈论详解 1（基本理论定义 和 Nim 游戏）

本文主要是介绍博弈论详解 1（基本理论定义 和 Nim 游戏），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

公平博弈游戏

1. 一般是两个玩家，轮流操作。
2. 是否能够必胜只和当前局面相关，不与现在是轮到哪个玩家相关（说白了就是不分黑白棋子，格点也不分黑白，都一样）。
3. 固定了开始状态后，可能的局面数是有限的。
4. 游戏一定会在有限步内结束

怎么才能赢？

必胜局面与必败局面

我们定义当前的局面对于先手（指的是要对当前局面进行操作的人，下面对先手的定义也相同）是必胜的为 $N$ 局面，必败为 $P$ 局面。根据必胜与必败的定义，可知：

1. 如果当前是 $N$ 局面，那么操作者一定能够通过做某一种操作使得局面变成 $P$ 局面，使对方（要对 $P$ 局面操作的人）必败，自己也就必胜。简单说就是从 $N$ 能走到 $P$。
2. 如果当前是 $P$ 局面，那么操作者无论如何操作，总是会输，也就是说只能到达 $N$ 局面，使对方必胜，自己必败（如果 $P$ 能到 $P$，那么意味着操作者可以反败为胜，此局面是 $N$ 局面，矛盾）。简单来说就是从 $P$ 只能走到 $N$。

什么样的局面是必胜的？

假设满足条件 $C$，局面就必胜，否则必败。根据上面的分析，容易发现：

1. 满足 $C$ 的局面一定能走到不满足 $C$ 的局面。
2. 不满足 $C$ 的局面只能走到满足 $C$ 的局面。

由于游戏结束时的局面是必败的（已经输了），所以再加上一条： 最终局面不满足 $C$。
那么该怎么找到条件 $C$ 呢？这很困难，一般都是引用先辈的结论。我们举一个简单的例子：Nim 游戏。

Nim游戏

游戏规则

有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个，每次操作可以取走一堆石子中的任意数量的石子。如果轮到一方取石子的时候没有石子了，Ta 就输了。

必胜条件 C

$C:a_1\oplus a_2\oplus a_3\oplus ...\oplus a_n\ne 0$（$a_1\oplus a_2\oplus a_3\oplus ...\oplus a_n$ 也称为 Nim 和）
$But$ $Why?$
首先，当 $a_1=a_2=a_3=...=a_n=0$ 的时候，是最终局面，上述等式不成立，所以 $C$ 要满足的第三个条件已经得证。
对异或的性质不是很了解的可以看一下本人之前写的一篇文章，主要结论：交换律，结合律和 $x\oplus y=z$ 则 $x\oplus z=y$。

第一个条件：假设操作之后的石子数量变成 $a_1^{\prime },a_2,a_3...a_n$，是 P 局面，则需满足$a_1^{\prime }\oplus a_2\oplus a_3\oplus ...\oplus a_n=0$，要证明 $a_1>a_1^{\prime }$。
令 $A=a_2\oplus a_3\oplus ...\oplus a_n$，$B=a_1\oplus a_2\oplus a_3\oplus ...\oplus a_n$。因为 $a_1^{\prime }\oplus A=0$，所以 $a_1^{\prime }=A$；因为 $a_1\oplus A=B$，所以 $a_1^{\prime }=A=B\oplus a_1$。
$B$ 的二进制中最高的为 $1$ 的位置是第 $k$ 位（从低位到高位，最低位是第 $0$ 位），不妨设 $a_1$ 的二进制中包含 $2^k$（这$n$ 个数里必然有一个数包含 $2^k$，否则 $B$ 的第 $k$ 位是 $0$）。因为两者的第 $k$ 位都是 $1$，所以 $B\oplus a_1$ 的第 $k$ 位是 $0$。但是 $B$ 的更高位上没有 $1$ 了，所以 $B\oplus a_1<a_1$，即 $a_1^{\prime }<a_1$，可以通过从 $a_1$ 中拿走一些石子实现转移。
你竟然看懂了第一个条件的证明！太厉害了，第二个条件会简单很多！

第二个条件：由于此时 Nim 和等于 $0$，假设你从第 $i$ 堆拿走了 $j$ 个石子，此时 Nim 和变为$(a_1\oplus a_2\oplus ...\oplus a_n)\oplus a_i\oplus (a_i-j)$（就是先把原本的 $a_i$ 从 Nim 和中去掉，再异或上新的 $a_i$）。由于 $j>0$，所以 $a_i-j\ne a_i$，$a_i\oplus (a_i-j)\ne 0$，新的 Nim 和不等于 $0$，转移到 N 局面。

必胜操作

必胜操作也已经在第一个条件的证明中提到了，如果你必胜，那么就在 $a_1$ 中拿走 $a_1-(a_1\oplus \text{Nim和})$ 个石子（$a_1$ 是一堆石子，满足 $a_1$ 包含 Nim 和最高位的 $1$ 所代表的值 $2^k$）。

想继续学习请看后续：博弈论详解 2（SG函数——对于一切公平博弈游戏通用的必胜条件）

题外话

此结论和证明都过于神奇且抽象，如果没看懂可以多研究一下，本人写文章的时候也差点绕进去了。

这篇关于博弈论详解 1（基本理论定义 和 Nim 游戏）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---