[学习笔记] 博弈论

UKError · 2024-04-02 22:39:55 · 算法·理论

博弈论 game-theory

基本概念

• 在一个游戏中，进行游戏的多位玩家的最优策略

  公平组合游戏

  1. 定义

• 游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；

• 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；

• 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

人话：骰子点数固定，限时且禁疗的图书馆。

2. 类型

一般的，如取数游戏， Nim 游戏，有向图游戏都属于公平组合游戏。特别的，大部分棋类游戏并不是公平组合游戏，因为他们不能动对方棋子。

3. 博弈图与状态

在题目中，我们通常需要预测谁必胜。博弈论便是为此诞生的。

我们拿 Nim 游戏举例：

我们把每一种状态设置成点，如果一种状态可以到达另一种状态，则建一条单向边。如此我们便可以绘制出博弈图状态图。

如图，是当初始值为 1,2,3 时，博弈图的绘制。

我们提取一部分来看：

经过推理，我们可以发现：

• 当 n 堆的值都为零，失败，游戏结束。

• 如果一个人发现自己可以走到一个地方绝杀对面，那么他一定会走到那个地方并赢得胜利。

• 如果一个人发现自己不管怎么走对面都能使他失败，那么他一定失败。

我们把必胜状态定义为先手必胜的状态，必败状态定义为先手必败的状态，一个人取了之后可能的状态定义为后继状态。

那么我们便可以总结为：

• 当一个人没有后继状态，那么他便是必败状态。

• 当一个人发现自己可以走到必败状态，那么他便可以走到那里，使对手处于必败状态，赢得比赛。

• 当一个人发现他的后继状态没有一个必败状态，那么他就只能走到必胜状态，输掉比赛。

例题：Nim 和

当且仅当 $Nim$ 和为 $0$ 时，该状态为必败状态；否则该状态为必胜状态。

证明这个只需要三个定理：

• 定理 1：没有后继状态的状态是必败状态。

• 定理 2：对于 a_1 \oplus a_2 \oplus \ldots \oplus a_n \neq 0 的局面，一定存在某种移动使得 a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0。

• 定理 3：对于 a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0 的局面，一定不存在某种移动使得 a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0。

为什么证明这三个定理便可以证明 Nim 和呢？

详见上文“博弈图与状态”，它与上文的区别只是将必胜状态改为 a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0 。

• 证明定理 1 ：

因为没有后继状态时， a_1 到 a_n 的值都为零，此时 a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0。

• 证明定理 2 ：