【学习笔记】博弈论

前言

开大坑~估计一万年都填不完的那种233

再次搬用前段时间苦啃动态规划时鼓励我的那句话(感谢小陶!

怕什么学海无涯,进一寸有进一寸的欢喜

(\)


(\)

来自巨佬们的一些经验

先研究一些比较显然的必胜/必败策略,比如说,我们要得到00这个数,那么当你取完时还剩0个,你就显然是胜的。
然后再通过最后的这个显然的必胜状态,往前递推找出其余的必胜状态。
显然博弈论是必然会出现循环节的,因为它是一种不断递归求解的过程,每次都可以取到当前这个循环节上的必胜状态,并且让你的对手能达到的下个状态全部都是必败状态,那样你就可以稳了。
——Flash_plus

必胜是对于当前这个状态是必胜的,与是谁无关,赢的人只是处于一个胜的状态而已。——Flash_plus

同样的,先手必胜或先手必败也是对于当前的局面来说的

(\)


(\)

例题以及简单题解记录

题目(P2197)【模板】nim游戏

题解:若当前异或和为 (0) 则后手胜,反之先手胜

思考:最开始看结论怎么样也想不通,这怎么就和异或扯上关系了??取任意石头,随意挑一堆,怎样都和异或没半毛钱关系啊??

接着我看了这篇题解。了解了一些其他类型的取石子游戏后,我有了一点初步的看法

事实上我们希望把局面控制在一个稳定的,操作数为偶数的循环节里

稳定的意思是指,不论对方怎样操作,我方都可以在固定的操作树中还原到目前局面

例如只可以取 (1) 个或 (2) 个石头的时候,只要剩余石头是 (3) 的倍数,那么先手取任意 (x) 个,后手只要取 (3 - x) 个就可以,操作数为 (2)

对于这道题,我们也希望找到这样一个循环节,而异或正好满足,因为若当前异或和为 (0) ,那么先手无论怎样操作都不可能使得取完后仍为 (0) ,而后手绝对可以将任意一个异或和不为 (0) 的局面操作成为 (0) 的,所以这也是一个操作数为 (2) 的循环节

原文地址:https://www.cnblogs.com/Bn_ff/p/13280944.html