关于如何思考有向图游戏上的不对称博弈问题
讲个笑话，这篇文章本来是想用来辅助证明 Moscow-International-Workshops-2017-Day-4-赛后小结中 I 的结论的，但是最后没有用到。
首先关于能建出 DAG 的不对称博弈，我们需要先确定一个事情，DAG dp 得到的 $ans$ 的就是答案。
原因是如果我是后手，只要给我 DAG 的 dp 转移过程，无论你是什么决策，我就一定能让你 $\ge ans$ ，而后手绝顶聪明，故答案 $\ge ans$ 。
同理，我是先手，可以证明 $\le ans$ ，所以是答案。
所以直接在 DAG 上 dp 是对的，问题是很多问题并不能在 DAG 上 dp ，所以就涉及了脱离 DAG 怎么思考不对称博弈的问题了。
不妨声称，我们只需要思考下面形式的决策：认为对手什么操作都做的出来，在任意一个状态，对手做出任何一个可行的操作后，我们会做出一个怎样的决策（即状态和对手操作唯一决定我的策略，没有任何别的因素）。这种决策很符合理性直觉。至于证明也非常简单，只要我们能构造一个答案相等的问题就行了。
为此，我们需要先思考一个问题，怎么知道一种决策对应的答案呢？即后手遵循怎样的策略呢？
- 后手目的是为了使你的答案最劣，根据你的决策。（即在 DAG 上根据这个决策进行 dp ，得到使先手最劣的决策；也可以认为是后手根据先手的决策穷举所有的决策，最终得到使先手决策答案最劣的决策；或者认为是根据先手决策改造 DAG ，然后在这 DAG 上跑最长路）
- 后手目的是为了使你的答案最劣，根据你的最优决策。（这一句话指，忽略前面的操作，在当前状态下，后手会认为你绝顶聪明的情况下进行操作，使你的答案最劣。换句话说：其的决策是 DAG dp 上的其中一个最优转移）
（如果你看过我后面写的内容，这里可以说一下为什么这里的方案 1 不会出现我预判你的预判的情况，因为这里先手指定策略完全不会受后手的具体决策影响，所以不会有这个问题）
显然，从 DAG dp 的角度可以证明，采用上面任意一种方案给每个决策赋予其答案，最终的最优答案都等于原问题的答案。甚至混合使用也是，但是显然正常人不会这么干
但是采用方案 $2$ 有一个问题，就是可能会使不是最优决策的决策拥有最优答案，这在某些找最优决策的题可能会出问题。
总之，这个思考方法的核心就是，不要管别的乱七八糟的可能的决策，我们就划分出一块可以思考而且答案在里头的决策用于思考。
类似的，也可以用 DAG dp 证明一些别的思考方法，反正只要证明这个思考方法的答案不变就行了。
这里举个例子：一种可能的思考方式是认为后手在每个状态的决策是固定的，是 DAG dp 最优决策的其中一个（是哪一个在一开始就固定了，不会中途改变，虽然可以改变也是对的，但是思考起来可能会比较麻烦），在此基础上，先手要最优化答案，根据 DAG dp ，这显然也是对的。两个思考方法各有优劣，如果你能够思考出后者的最优策略，那么你就能直接当成一个非博弈题来做，但是如果你思考不出最优策略，那么一个存在但是你不知道的后手的固定策略反而会让你的思考僵化。
当然，除了直接思考不对称博弈的策略，还有许多种方法可以绕过这个过程，直接得到答案是啥：
- 证明先手存在策略使得答案 $\le ans$ ，无论后手策略是啥；证明后手存在策略使得答案 $\ge ans$ ，无论先手策略是啥。所以答案就是 $ans$ 。
下面的可以不用看了，想知道这篇博客背景的可以看看，上面已经总结完我最终得到的思考方法了。
说起来，我在写小结的时候突然发现，我在思考不对称博弈的时候思维总是是混乱的，所以这里写一篇博客来理一理怎么思考不对称博弈。
这里放一个不对称博弈的例子：
https://qoj.ac/contest/1213/problem/6370
在思考这一类问题的时候，我总是会陷入一个误区，为什么不会出现我预判了你的预判的这种情况，就总是会想，虽然我可以证明这个世界线这样变方案不会更劣，但是说不定对手不如我的愿，改变了策略，反而使这种改变更劣了呢？
虽然直觉上，我改变了一条世界线，肯定不应该改变另外一条世界线，两者的决策应该是根据当前状态，而不会根据对手的策略，但是真要严谨证明上述过程，不借助具体模型，纯口胡总是很难表达清楚，总会陷入循环证明的情况；要么就十分的复杂，最后把自己都绕晕了；要么就涉及一点感性，怎么想都感觉别扭，什么一定最优，不会改变之类的（当然也有可能我是先天笨蛋圣体）。
以上面的例子为例，显然的，可以建出一个 DAG ，表示转移，显然最小值可以通过 DAG 转移出来，这样得出最小值的方法简单明了，清晰易懂，不会有任何争议。但是直接让我在原问题上想怎么通过优化决策的方式得到最小值，我就不知道为什么，总会觉得哪里很不对劲，哪里想错了，而且事实是在比赛时也确实想错了几次。
update ：后面发现有些疑惑的产生是因为题目让对手在大局上绝顶聪明，目标是阻止我，而细化到局部，“阻止我”这句话太过感性，没有具体的模型思考的话，我就总会感觉感性，会感觉怪怪的，所以解决方法就是找个模型就行了，具体见上面。
所以这里提供几个方法。
直接证明这是答案的下界，然后取得到。
这种方法相当于直接规避掉了决策方案的讨论，类似投机取巧的方法，上面的那个问题就比较难用，但是方便直观。
仔细思考一下，上面我们为什么会陷入疑惑，即为什么两者的决策会跟对手有关，我思考了一下，感觉可能是潜意识中对下述两个问题的混淆：
如何在知道对手决策的情况下使得其答案更劣？（指裁判方的决策，下个问题同）
如何在知道对手决策的情况下使得其在最优情况下答案更劣，或者换句话说，如果这个时候，对手换成绝顶聪明的人，我们什么操作能使对方得到最劣的答案？
说到底我会疑惑主要是很多时候陷入到了前者，但实际我们应该考虑后者。注意到后半句话其实和题目要求很像：认为对手绝顶聪明。这两个问题的本质区别在于，实际想问题的时候，我们在追求最优方案，即我们在尝试模拟绝顶聪明的人是怎么想的。但绝顶聪明是怎么定义的呢？怎样算绝顶聪明的呢？
如果在类似 LOL 这种游戏，必须要考虑对手决策的情况下，这种问题是难以回答的，但是在 DAG 上时，这种绝顶聪明是可以定义的，就是只要决策符合 DAG 上 dp 的最优转移，这个操作就是绝顶聪明的人能干出来的。
而我们在尝试找到己方最优方案的同时，我们在模拟对方的方案的时候，其实潜意识中认为了对方知道我们不是绝顶聪明的这个信息，从而对方会尝试通过我们的决策找到最劣的答案（问题 1）。但实际的问题一定是我们就是绝顶聪明，对手也知道（问题 2）。因此在 DAG 问题上，对手的操作可以认为是基本固定的。
因此，我们可以在疑惑的时候，多想想我们是不是把问题 2 搞错成了问题 1 。
所以一个好的解决方法就是，既然对手在问题 2 的情况下，操作是基本固定的，那么我们不妨就直接固定下来，具体来说，将问题转化为：
当对手碰到某个状态，一定会进行 DAG dp 上所指示的其的最优策略，有多个进行其中任意一个即可。显然这样不会改变答案（证明就 dp 一下就行了，发现转移是不变的），这样就将对手操作固定，从活物变成规则集，这样会好思考很多。
在这个新的问题上，为啥改变其中一条时间线不会影响到其他时间线的原因就显然了，只要我其他时间线的决策不变，而对手的决策是固定的，所以显然就不会变。
就认为对手并不是绝顶聪明的，是一个会给出任意策略的神经，因此你在思考最优策略的时候，必须在所有状态，都决定好其打出任意可行操作后的策略，这个思考方法可以认为就是在有向图游戏上 dp 过程的具象化，有向图游戏上的 dp 过程在得到我方某个状态的最优解的时候，实际上就是穷举了对手下一步的所有操作并转移的。