博弈论

NIM游戏 —— 模板题 AcWing 891. Nim游戏

给定N堆物品,第i堆物品有Ai个。两名玩家轮流行动,每次可以任选一堆,取走任意多个物品,可把一堆取光,但不能不取。取走最后一件物品者获胜。两人都采取最优策略,问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手,第二个行动的称为后手。若在某一局面下无论采取何种行动,都会输掉游戏,则称该局面必败。
所谓采取最优策略是指,若在某一局面下存在某种行动,使得行动后对面面临必败局面,则优先采取该行动。同时,这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况,即两人均无失误,都采取最优策略行动时游戏的结果。
NIM博弈不存在平局,只有先手必胜和先手必败两种情况。

定理: NIM博弈先手必胜,当且仅当 A1 ^ A2 ^ … ^ An != 0

Nim游戏

20220131215546

公平组合游戏ICG

若一个游戏满足:

  1. 由两名玩家交替行动;
  2. 在游戏进程的任意时刻,可以执行的合法行动与轮到哪名玩家无关;
  3. 不能行动的玩家判负;
    则称该游戏为一个公平组合游戏。
    NIM博弈属于公平组合游戏,但城建的棋类游戏,比如围棋,就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子,胜负判定也比较复杂,不满足条件2和条件3。

有向图游戏

给定一个有向无环图,图中有一个唯一的起点,在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动,每次可以移动一步,无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是,把每个局面看成图中的一个节点,并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算,即:
mex(S) = min{x}, x属于自然数,且x不属于S

SG函数

在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1, y2, …, yk,定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果,即:
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即SG(G) = SG(s)。

有向图游戏的和 —— 模板题 AcWing 893. 集合-Nim游戏

设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G,它的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和,即:
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)

定理

有向图游戏的某个局面必胜,当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败,当且仅当该局面对应节点的SG函数值等于0。