博弈论
1.是二人或多人在平等的对局中各自利用对方策略变换自己的对抗策略,达到取胜目标的理论。
2.博弈论是研究互动决策的理论。博弈可以分析自己与对手的利弊关系,从而确定自己在博弈中
3.的优势,因此有不少博弈理论,可以帮助对弈者分析局势,从而采取相应策略,最终达到取胜
开胃菜-抢糖果
1.桌子上放着5块糖,Alice和Bob轮流拿,Alice先手
2.没人最少可以拿1块最多拿3块
3.拿最后一块糖的人获胜
我们推导一下:
1.假如说桌子上只有1~3块糖果时候,拿糖果得人可以一次拿走这就是先手必胜态先手必胜态先手必胜态;
2.当桌子上有4块的时候呢,那么无论怎么拿先手都是必败得,这就是先手必败态先手必败态先手必败态
3.同样如果桌子上是6/7/块得时候先手都可以变4块就是必胜态
4.但是如果是8块Alice只能变成5/6/7,那么先手必败
5.我们要明白非4倍的状态可以变成4倍或者非4倍的状态而4倍只能变成非4倍
6.由于4是必败态那么每个人取完都极可能的留下4的倍数给对方那么就是4x+z就是先手必胜
必胜态和必败态
1.如果先手以这种状态开局必胜/必败就是必胜/必败态
2.这里我们定义了一个转移,对于A状态,若通过一个回合的操作可以变成B状态,那么我们称A状态可以转移到B状态
3.作为必胜态,该状态一定可以转移到任意必败必败态
4做为必败态,该状态的任意转移都会转到必胜态。
棋盘问题
我们可以逆序倒推,就是从终点看终点是必败态,那么就可以逆向递推出所有的状态