博弈

Tags：数学

作业部落

评论地址

前言

本博文分三部分，第一部分简单介绍SG函数，第二部分简单介绍博主所理解的一些博弈模型，第三部分推荐题目以及分享做题心得，本文基本不适合初学者食用，初学者请移步下方链接

论文：2009贾志豪（百度文库可搜）
自为风月马前卒的总结
自为风月马前卒的题目

Part1 SG函数

优势：可以实现对多个游戏进行加和

计算方式：\(SG(x)=mex(SG(y))\)，其中\(mex\)指集合中最小没有出现过的自然数，\(y\)为\(x\)的后继状态

游戏加和：\(SG=SG(x_1) \bigoplus SG(x_2) \bigoplus ...\bigoplus SG(x_n)\)

意义：\(SG=0\)表示先手必败，为P状态，否则为N状态，先手必胜

理解：化为\(Nim\)游戏，对于每个\(SG\)不为\(0\)的状态总有一种方案使得\(SG\)成为\(0\)

Part2 平等博弈模型

1.巴什博弈（Bash Game）

问题：只有一堆\(n\)个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取\(m\)个。最后取光者得胜
结论：\(n\%(m+1)\)为\(0\)先手必败否则必胜

2.威佐夫博弈（Wythoff Game）

问题：有两堆各若干个物品，两个人轮流同时从一到两堆中取同样多的物品，规定每次至少取一个，最后取光者得胜
结论：
先手必败态的两堆石子之差依次递增，且每个自然数仅出现一次，先手必败态为\((0,0),(1,2),(3,5),(4,7),(6,10),(8,13)...\)
如果必败态为\((a,b)\)，\(k=(a-b)\)，则\(a=\frac{1+\sqrt{5}}{2}*k\)

3.尼姆博弈（Nim Game）

问题：\(n\)堆石子两人轮流在任意一堆中取任意石子，不能不取，最多取完，取到最后一颗石子者胜
结论：\(n\)堆石子数量异或和为\(0\)则先手必败否则必胜
Nim游戏代表了所有平等博弈问题！！

4.Nim 游戏扩展

问题：每次最多丢\(k\)个石子，其余规则同\(Nim\)
结论：每堆石子数量\(\%(k+1)\)后再求异或和

5.Nim k 博弈

问题：一次最多在\(k\)堆中取，其余规则同\(Nim\)
结论：把石子数二进制拆开，每位求和后\(\%(k+1)\)，若最后每位都为\(0\)则先手必败，否则先手必胜

6.阶梯博弈

问题：有\(n\)堆石子放在\(n\)层阶梯上，两人轮流选择一层的若干石子，放入下一层（特别地，选择\(1\)层的石子就被扔掉），无法操作者输
结论：奇数层石子的数量异或和为\(0\)则先手必败否则必胜

7.Anti-SG（反Nim游戏）

问题：取走最后一颗石子者败，其余规则同\(Nim\)
结论：
当且仅当以下情况先手必胜
1.整个游戏\(SG=0\)并且没有单一游戏\(SG>1\)
2.整个游戏\(SG>0\)并且至少一个单一游戏\(SG>1\)
通过下图来理解（QAQ之前画错了，更严谨证明请见贾志豪的论文）

8.Multi-SG

问题：
结论：

9.Every-SG

问题：
结论：

10.翻硬币游戏

问题：
结论：

11.树上删边游戏

问题：
结论：

12.无向图删边游戏

问题：
结论：

13.动态减法问题

问题：
结论：

14.匹配的应用

问题：
结论：

博弈学习笔记（未完成）

原文：https://www.cnblogs.com/xzyxzy/p/9397756.html