首页关于

计算机中的博弈论

2025-02-06

相较于经济学中的博弈论问题，计算机中的博弈论，更多讲述的是两人对弈的优胜策略。
本文将重点讨论一下博弈论在计算机领域的一些理论基础和简单应用。
为了简化问题讨论，文章中没有明确说明的博弈问题都代指两人博弈。

填格子游戏

在聊到计算机中的博弈论问题之前，我们先来玩一个[小游戏:填格子]。

这个填格子游戏看起来很简单, 但是似乎又隐藏着什么规律。

是的，这个游戏其实是存在必胜策略的。

假设我们最终需要报数的数值为N, 每次可以填1至M个格子, 后手必胜的条件是(|表示整除, %表示取余数)：

1 + M ｜ N

否则, 先手总可以在游戏的第一轮, 先选取一个数K = N % (1 + M), 在填完K个格子之后的每一轮，先手总可以在后手填完格子之后，想办法和后手上一轮填的格子数量凑成1 + M个格子数量即可。

Nim取石子游戏

接下来，我们再来一起玩另一个[小游戏:Nim取石子]。

这个游戏的规则相较于上一个游戏来说，会稍微复杂一些，但是也是存在必胜的游戏策略。

我们先说结论，后面将通过反证法来证明结论的正确性。

在说明具体的必胜策略之前，我们先引入游戏中存在的2个状态的定义：

必败态: 当前游戏者进行任意的一步操作之后，都将导致对手进入必胜态，则当前游戏的局面对于当前进行操作的玩家为必败态。
必胜态: 当前游戏者进行某一步操作之后，将导致对手进行入必败态，则当前游戏的局面对于当前进行操作的玩家为必胜态。

举个例子，在上面的填格子游戏中，需要填的格子数量为N，每一轮可以填的格子数量为1到M，如果N刚好是1+M的整数倍，那么，对于先手来说，初始的局面就是必败态，因为无论先手填了1到M中的任意一个整数K的格子数之后，后手都有办法取走1+M-K个格子，使得剩余空闲的格子数量仍然为1+M的倍数，也就是后手总会在先手操作后，变为必胜态。

现在，我们再来说明一下这个游戏的必胜策略：

  1. 将每一堆石子的数量进行逐个异或(运算符号为^)计算，得到它们的异或和。
  2. 当前的局面, 如果异或和为0，则当前的操作者进入了必败态, 否则，为必胜态。
  3. 进入必胜态的操作者，需要将剩余石子的数量的异或和变为0, 即可获胜。

这个结论看着有一点复杂，下面我们来进行具体举例讨论说明，假设我们有3堆石子，每一堆的石子数量分别为4个(第1堆)、5个（第2堆）、6个(第7堆), 这几个数字的异或和为7(7 = 4 ^ 5 ^ 6), 为了取胜，先手可以通过取走第1堆1个石子之后(必胜方案不唯一)，将剩余石子的数量的异或和变为0(0 = 3 ^ 5 ^ 6)，后续无论后手如何操作, 先手只需要保证在每一轮的操作之后，剩余石子的数量的异或和变为0， 即可取得胜利。

为了证明上面必胜策略的正确性，我们只需要证明下述2个猜想为真即可：

[猜想1] 异或和为0是必败态: 任意一种异或和为0的场景，一定无法通过一步操作重新变为异或和为0的场景。
[猜想2] 异或和为非0是必胜态: 任意一种异或和为非0的场景，一定至少有一种操作方案变为异或和为0的场景。

对于[猜想1]，我们可以简单的通过反证法说明：

假设我们从一堆石子总数为X的石子堆中取了K个石子，最终使得所有堆的石子数的异或之和为0，由于，在取石子之前，所有堆的石子数的异或和为0，则说明除了当前堆的石子，其他堆石子的异或之和为X，又因为取了K个石子后，当前堆剩余的石子数量为Y(Y=X-K), 由于总体的石子数在本轮操作后的异或和为0，也就是X ^ Y = 0，那么，Y = X, 反推出K = 0, 与游戏的要求，每次需要至少取走某堆至少1枚石子的要求不符, 因此，可证明[猜想1]的正确性。

对于[猜想2], 假设全部堆石子的异或和为K, 我们需要证明 ：

至少存在某堆石子，这堆石子的数量为X, 使得X > X ^ K 成立, 此时, 我们可以将这一堆石的数量变为X ^ K个石子即可使得全部堆石子的异或和为0。

具体的证明方式比较有意思，由于篇幅有限，留给感兴趣的读者自行推导。

SG函数

我们继续玩一个[小游戏:Nim取石子2.0]。

这个游戏是我们对Nim取石子游戏的一个改版，在每次取石子的过程中，对于可以进行取石子的数量做了一定的限制。

一定有聪明的朋友在思考，这个改版的2.0版本Nim取石子游戏，是否有必胜策略，以及是否可以借鉴Nim取石子游戏的一些方法论呢？

答案是肯定的。在讲述具体的必胜策略之前，我们先引入一个概念:

SG函数： 通过将某个游戏局面转化为一个具体数值来表示该局面价值的函数，具体数值的取值范围为非负整数，其中, SG数值为0的局面为必败态，SG数值为非0的局面为必胜态。另外，SG数值较大的局面，一定可以通过某种操作，转换为任意SG数值较小的局面。

某个游戏盘面P的SG数值的计算方式可以简化为如下公式：

SG(P) = SG(P1) ^ ... ^ SG(Pn)

其中，P1、P2、...、Pn为当前游戏盘面P下的1到n个规则完全相同的子盘面。

就比如Nim取石子游戏，某个盘面具体的SG函数的数值即为每堆石子的SG函数的异或和。

那么，具体某个子盘面的SG函数的数值该如何计算呢？下面我们先给出具体公式：

SG(Pi) = mex{SG(Pi1), SG(Pi2), ..., SG(Pim)}

其中mex函数表示一个集合中最小未出现的非负整数，而 SG(Pij)集合表示Pi盘面在完成一步操作之后，得到所有下一个盘面的SG数值的集合。

在上面的填格子游戏中，假设剩余盘面中，未填的空余格子数为K，此时:

SG(K) = mex{SG(K - 1), SG(K - 2), ..., SG(K - M)} = SG(K - (M + 1)) = K % (M + 1)

而Nim取石子游戏里，某堆包含K个石子的盘面的SG数值即为K。计算方式参考如下：

SG(K) = mex{SG(0), SG(1), ..., SG(K-2), SG(K-1)} = mex{0,1,...,K-2,K-1} = K

结合上述的2个游戏结论，读者们可以思考一下，在多重填格子游戏中（有多堆数量各不相同的格子，每次可以填写其中某一堆格子至少1个，至多M个格子的数量），某个盘面的具体SG函数的数值是多少，有什么样的必胜策略。

仔细思考上述问题的朋友会发现，这个神奇的SG函数，好像可以解决上述这一大类的两人对称博弈的问题。

现在，我们回到Nim取石子游戏2.0这个游戏，我们通过上面的结论也大致知道了这个游戏可以通过计算每个子盘面的SG函数数值，再通过异或和的方式判断某个盘面是否为必胜态，下面我们也给出7以内这个游戏子盘面的SG数值：

SG(0) = 0
SG(1) = mex{SG(0)} = 1
SG(2) = mex{SG(0), SG(1)} = mex{0, 1} = 2
SG(3) = mex{SG(1), SG(2)} = mex{1, 2} = 0
SG(4) = mex{SG(0), SG(2), SG(3)} = mex{0, 2, 0} = 1
SG(5) = mex{SG(1), SG(3), SG(4)} = mex{1, 0, 1} = 2
SG(6) = mex{SG(0), SG(2), SG(4), SG(5)} = mex{0, 2, 1, 2} = 3
SG(7) = mex{SG(1), SG(3), SG(5), SG(6)} = mex{1, 0, 2, 3} = 4
...

相信你根据上面问题的详细分析，已经知道如何在这个游戏中取胜了， 祝你好运！

极大极小搜索

这个算法使用的是计算机算法中的深度优先搜索、贪心、剪枝来实现解决计算机棋牌等对弈游类戏的博弈计算，由于具体的实现方式的专业性质较强，篇幅有限，感兴趣的可以自行搜索阅读相关资料或者和笔者私下交流。