博弈论讲解-拓冰建站

简单图上博弈

博弈树

其实就是记录你每一步决策的状态。

比如：

5 个石子，Alice 和 Bob 轮流取，每次取 1 到 2 颗，取到最后一颗的入人胜，Alice 先手问她的必胜决策。

5 Start | \ 4 3 Alice | \ \ \ 3 2-+ 2-+ 1 Bob | \ \ \ \ \ \ 2 1 1 0 1 0 0 Alice |\ \ \ \ 1 0 0 0 0 Bob | 0 A

其中旁边的字母代表现在轮到了谁，数字表示当前还剩几颗，这就差不多是博弈树。

然后求答案就从出边为 0 的开始计算，有点类似 Topo 排序。

题目

P4096

P7135

这里我认为第二道题不那么像模板题，第一道题就是模板题，因此我讲第二道：

P7135

这是我做的第一道交互题，只不过它也不是很难。

如果你发现的仔细的话，你就可以填出一个幻方（这里不展示），包含这几个数字，每一行、每一列、每一条对角线都是 15，因此我们发现这不就是井字棋吗？

于是直接建出博弈树就做完了。

如果你玩过井字棋的的话，你也可以直接写程序暴力和交互库下棋。

code：

不好意思的是我是直接和他下棋并没有建博弈树。

提示：先手下角（网上有说为什么），后手堵桥（就把交互库第一步下的位置直接提前每个出一套对策直接干）。

有向图博弈

这玩意很好做，博弈方式直接建出树，只不过有可能有两个父节点同时拥有同一个子节点~~（继父？？？）~~，只不过这问题也不大~~（父母离异问题还不大？孩子心理会有问题）~~。

划掉的部分是我同学说的，但我想回一句：

~~你是不知道红黑树是吧？孙子的孙子秒变爷爷的爷爷！！！~~

这是数据结构和家谱没有问题。

但是，DAG只存在于有向无环图，有环怎么办？？？~~（啥？孙子结婚生了爷爷？？？（见过基环树吗？也有环））~~

没关系，我们可以发现，只要这种情况出现了，肯定平局，不然跳出这个环外的人就输了！！！

题目

CF786A

P6560

P9169

都是模板题，没必要讲。

公平组合游戏（Nim 游戏）

博弈论部分由于以思维为主，很少作为一个知识点用来考察。但以nim 游戏为代表的公平组合游戏，是一个很容易考场的知识点。

公平博弈（impartial game）指满足如下条件的组合博弈：
在任意确定状态下，所有参与者可选择的行动完全相同，仅取决于当前状态，与身份无关；
博弈中的同一个状态不可能多次抵达，博弈以参与者无法行动为结束，且博弈一定会在有限步后以
非平局结束。
nim 游戏：有堆石子，第堆石子有颗石头，先后手轮流操作，每次可以选择一堆石子，然后从中选大于 0 个石头扔掉。谁在操作后场上所有石头清空，谁获胜。
所有的公平组合游戏，都可以转化为nim 游戏。

我们直接给出结论：一个状态为先手必败，当且仅当所有石子的异或和为 0。
证明是这样的：不妨把上述状态称为必败。显然，当时，这就是一个必败态。
现在对于任意一个非必败态，可以证明一定存在一种操作方案，使得一次操作之后转化为必败态，
且对于一个必败态，操作一次必然成为一个非必败态，因此证明完毕。
于是我们可以线性复杂度判断一局 nim 游戏的状态了。

这个理论可以把所有的公平组合游戏转化为nim 游戏。
首先公平组合游戏有很多不同的“局”，比如nim 游戏中，就有局游戏，每一局游戏都是一堆石子，
虽然单堆石子很简单，但是它也可以看做一张有向无环图博弈：连边为必败点。
而所有的“局”都是一张有向无环图。
我们定义图上一个点的函数值为所有它可以到达的点的值的 mex。且必败态的值为 0。
把所有游戏起点的异或起来，不为 0 则为必胜态。

knim 游戏，与 nim 游戏的区别在于每次可以至多拿堆石子。
阶梯nim，每次可以在一堆里面选出大于 0 个石子，然后放到下一堆，特殊的，对于第一堆选出来
的石子会直接扔掉。
树上nim，选出来的石子放到父节点上，根上的直接扔掉。
树上博弈，给你若干个有根森林，每次删掉一颗子树（根不能删），谁不能操作谁输。