博弈论总结（20260201）

ICG 游戏若满足以下条件游戏由两个人参与两人轮流做出决策且必定对自己最有利当有一人无法做出决策时游戏结束无法做出决策的人输且无论两人如何决策游戏都一定会结束不会出现平局游戏中的同一个状态不可多次抵达任意游戏者在某一确定状态下做出的决策只与当前状态有关而与游戏者无关DAG 中的博弈根节点有一个棋子两个游戏者轮流移动这颗棋子若当前点没有后继点则当前点为必败点若当前点的后继点存在必败点则当前点为必胜点否则为必败点SG 函数Sprague-Grundy定义 为 最小的不属于集合 的非负整数定义SG函数性质若SG函数值为0则当前点必败否则必胜满足DAG上博弈的性质SG 定理游戏的和的SG函数值等于游戏的SG函数值的异或和Nim游戏各类变形Nim堆物品每堆 个两个玩家轮流取走任意一堆的任意个物品不能不取取到最后一个物品的人获胜若 则先手必败否则先手必胜k-Nim堆物品每堆 个两个玩家轮流取走最多 堆中的任意个物品不能不取取到最后一个物品的人获胜令 在二进制下第 位的值为若 则先手必败否则先手必胜阶梯 Nim堆物品每堆 个两个玩家轮流将任意一堆 中的任意个物品放入 中 不能不操作无法操作的人输若 且为奇数 则先手必败Anti-Nim堆物品每堆 个两个玩家轮流取走任意一堆的任意个物品不能不取取到最后一个物品的人失败若 且 , 则先手必胜若 且 , 则先手必胜否则先手必败博弈论题目常用做题技巧规约为经典模型如 Nim 游戏或经典模型变形分类讨论SG函数胜败态DP寻找必胜策略然后从简单情况开始手玩博弈思想若当前状态对自己有利必定会尽量维持当前局面否则尽力改变