111 lines
5.1 KiB
Markdown
111 lines
5.1 KiB
Markdown
## 博弈论入门
|
||
[原文地址](https://www.cnblogs.com/RioTian/p/13032919.html)
|
||
|
||
> 古语有云，“笑人情似纸，世事如棋”。生活中每个人如同棋手，其每一个行为如同在一张看不见的棋盘上布子，精明慎重的棋手们相互揣摩、牵制、争赢，下出诸多精彩纷呈、变化多端的棋局。而什么是博弈论？就是研究棋手们的“出棋” 过程，从中抽象出可逻辑化的部分，并将其系统化的一门科学，也是运筹学的一个重要学科。
|
||
|
||
### 博弈论的题目有如下特点:
|
||
1. 博弈模型为两人轮流决策的博弈。并且两人都使用最优策略来取得胜利。
|
||
* 两个玩家，都会采取最优的决策，那么如果存在一个局面为必胜局面，某玩家位于此局面。只要自己无失误，则必胜。那么同样又一个局面为必败局面，某玩家位于此局面。只要对手无失误，则必败。
|
||
* 那也就是说，针对这样的游戏，我们关注点应该在局面上。
|
||
2. 博弈是有限的。即无论两人如何决策，都会在有限步决出胜负。
|
||
3. 博弈是公平的。即两人进行决策的规则相同。
|
||
|
||
相关概念：
|
||
* 先手必胜状态：先手可以从这个状态走到某一个必败状态。
|
||
* 先手必败状态：先手走不到任何一个必败状态。
|
||
* 也就是说先手必胜状态，那么先手一定能采取某些操作，让后手面对必败态。如果是先手必败态，无论先手怎么操作，都无法让后手面对必败态。
|
||
|
||
### 简单博弈的基本题型
|
||
#### 1、$bash$博弈 (巴什博奕)
|
||
假设一堆石子有$n$个，每次最多取$m$个，甲乙两个玩家轮流取石子，**最后把石子取完的人获胜**，保证甲乙每一步的决策都是最优的，请问给定$n$和$m$，问甲胜还是乙胜。
|
||
|
||
**解答**：
|
||
不妨假设刚刚开始 $\large \displaystyle n = m + 1$，那么不管先手取几个，后手必胜，有如下推论：
|
||
|
||
令 $n = (m + 1)*r+s$ 其中$(r > 1，0 <= s < m + 1)$
|
||
|
||
* 如果$s=0$的话，先手每次取$k$个，后手只要取$(m+1-k)$个即可，**后手必赢**。
|
||
* 如果$s>0$的话，先手者第一次取$s$个，后手第一次取$k$个，接下来先手只要取$(m + 1 - k)$个即可，**先手必赢**。
|
||
|
||
<font size=5 color='red'><b>结论：
|
||
$$n \ mod (m+1)
|
||
\large \left\{\begin{matrix}
|
||
=0 & 先手必败 \\
|
||
≠0 & 先手必胜
|
||
\end{matrix}\right. $$
|
||
</b></font>
|
||
**练习题**
|
||
|
||
[$HDU2188$](https://www.cnblogs.com/littlehb/p/16403946.html)
|
||
|
||
|
||
[$HDU1846$](https://www.cnblogs.com/littlehb/p/16403951.html)
|
||
|
||
[$HDU1847$](https://www.cnblogs.com/littlehb/p/16403954.html)
|
||
|
||
---
|
||
|
||
#### 2、$nim$游戏
|
||
假设有$n$堆石子，每堆石子分别有$a_1,a_2,…,a_n$个,每次可以选择任意一堆且至少取$1$枚石子, 甲乙两个玩家轮流取石子, 最后把石子取完的人获胜, 保证甲乙每一步的决策都是最优的, 甲为先手操作, 问甲胜还是乙胜。
|
||
|
||
<font color='red' size=5><b>结论:
|
||
$$a_1∧a_2∧…∧a_n = \left\{\begin{matrix}
|
||
=0 & 先手必败 \\
|
||
\neq 0 & 先手必胜
|
||
\end{matrix}\right.
|
||
$$
|
||
</b></font>
|
||
|
||
证明：
|
||
* 当$a$不全为$0$时, 任意一个$res!=0$的局面, 先手可以通过一定的操作让后手面对$res=0$的局面。
|
||
|
||
* 对于任意一个$res=0$的局面, 先手无法通过任何操作让后手面对$res=0$的局面。
|
||
|
||
得出结论, 当$res=0$时先手必败, 反之必胜。
|
||
|
||
[详细证明](https://i.cnblogs.com/posts/edit-done;postId=15391869)
|
||
|
||
|
||
练习题
|
||
[$AcWing$ $891$. $Nim$游戏](https://www.cnblogs.com/littlehb/p/15391869.html)
|
||
|
||
[$HDU1850$](https://www.cnblogs.com/littlehb/p/16403971.html)
|
||
|
||
[$HDU2176$](https://www.cnblogs.com/littlehb/p/16403990.html)
|
||
|
||
[$HDU1730$](https://www.cnblogs.com/littlehb/p/16403933.html)
|
||
|
||
---
|
||
|
||
#### 3、$Nim$博弈拓展-台阶$Nim$
|
||
**问题描述**: 有一个$n$级台阶的楼梯, 每级台阶上有若干个石子, 其中第$i$级台阶上有$a_i$个石子($i≥1$)。两位玩家路轮流操作, 每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶上(不能不拿)。
|
||
已经拿到地面的石子不能再拿, 最后无法进行操作的人视为失败。问如果两人都采取最优策略, 先手是否必胜。
|
||
|
||
<font color='red' size=5><b>结论
|
||
$$res=a_1∧a_3∧a_5∧,…,∧a_n
|
||
\large \left\{\begin{matrix}
|
||
=0 & 先手必败 \\
|
||
\neq 0 & 先手必胜
|
||
\end{matrix}\right.
|
||
$$ (这里的$n$是奇数)
|
||
</b></font>
|
||
|
||
练习题:
|
||
[$AcWing$ $892$ 台阶-$Nim$游戏](https://www.cnblogs.com/littlehb/p/15391920.html)
|
||
|
||
[$POJ1704$(台阶Nim)](https://www.cnblogs.com/littlehb/p/16404976.html)
|
||
|
||
[$HDU4315$(台阶Nim)](https://acm.hdu.edu.cn/showproblem.php?pid=4315)
|
||
此题太难理解了，暂时没整上,明天继续
|
||
|
||
#### 4、$Wythoff$博弈(威佐夫博弈)
|
||
#### 5、$Fibonacci$博弈
|
||
#### 6、$sg$函数
|
||
|
||
https://www.cnblogs.com/RioTian/p/13032919.html
|
||
https://blog.csdn.net/qq_42505741/article/details/84330302
|
||
https://blog.csdn.net/bbhhtt/category_7312898.html
|
||
https://www.cnblogs.com/zzz-hhh/p/13625295.html
|
||
|
||
|
||
[HDU4764 Stone] |