博弈
博弈的两种的分类：
动态博弈是指在博弈中，两个参与人有行动的先后顺序，且后行动者能够观察到先行动者所选择的行动。
静态博弈是指在博弈中，两个参与人同时选择或不同时选择时，后行动者并不知道先行动者采取什么样的具体行动。
1. 极大极小博弈树
由于动态博弈参与者的行动有先后顺序，因此参与者的行动构成的为树状结构。
博弈通常是双方对抗，甚至是零和的博弈。也就是说，对对方最有利的决策，反过来就是对我方最不利的局面。在轮到我们做出决策的时候，我们通常希望最大化我们的收益，叫做极大层，此时树的节点叫做极大层节点；在对手做决策的时候，对手希望最小化我们的收益，叫做极小层，此时树的节点叫做极小层节点。由于双方是交替做出决策，因此极大层、极小层通常是交替出现，这样的数据结构就叫做极大极小树（Min-Max Tree）。
「必胜态」和「必败态」的概念：
- 一个状态为「必胜态」，当且仅当其相邻状态中至少有一个「必败态」。这里相邻的状态的定义为：在当前状态中进行决策的玩家可以到达的所有状态。也就是说，玩家可以选择移动到一个「必败态」，使得对手必败，因此当前状态是必胜的。
- 一个状态为「必败态」，当且仅当其相邻的所有状态都是「必胜态」。这里的道理是类似的，如果所有相邻状态都是「必胜态」，那么对手必胜，当前玩家必败。
2.从已知状态进行搜索
从已知的最终状态进行倒推之前状态的可能性，考虑已有的可能的几种状态
leetcode 913 猫和老鼠
- 此步老鼠胜利，上一步为老鼠行动，则上一步老鼠为必胜态
- 此步老鼠胜利，上一步为猫行动，则上一步猫行动状态的出度减一，(因为猫走该步后不肯能胜利)，只有当猫行动后所有的子状态均为老鼠的必胜态时，即出度为0时，此时猫所处的状态为必败态。
- 此步猫胜利，上一步为猫行动，则上一步猫的状态为必胜态。
- 此步猫胜利，上一步为老鼠行动，同上。
状态定义 f[i][j][0]为老鼠处于i，猫处于j，此时为老鼠行动，上一步为猫行动。 老鼠胜利：1， 猫胜利： 2， 平局： 0，最终返回初始状态的值。