博弈论的题往往可以通过直接计算Sprague-Grundy函数来解决。本文将介绍两道较为相似的例题,在他们的设定下,大多数情况输赢仅由双方的优势程度所决定,而先手的优势则被限定在很小的范围内——即势均力敌的情况。
例题1
CodeForces 1704F. Colouring Game
Alice和Bob在一个仅由0和1所构成的字符串上进行轮流博弈。Alice先行。
- Alice每次可以选择连续的两个字符,且至少有一个是0,然后将这两个字符均变为2。
- Bob每次可以选择连续的两个字符,且至少有一个是1,然后将这两个字符均变为2。
无法操作者游戏失败。
解法:
双方的优势成都可由0和1的个数来描述:
- 如果0的个数比1的个数多,那么Alice赢;如果1的个数比0的个数多,那么Bob赢。
这是显然的,因为个数多的那一方永远选择把01或者10变为22,不会减小0和1的个数之差。
接下来,只需要考虑0与1一样多的情况。此时,将01交替出现的一段看作一个部分。对每个部分的博弈可化为:
- 每人每次可以选择连续的两个未被占据的位置,将其占据。
- 无法操作者失败。
这是因为,剩余的未被占据的单个位置必然拥有相同个数的0和1,不会影响双方胜负的情况。
于是,令$g(n)$表示长度为$n$的部分的SG值,那么
$$ g(n) = \operatorname{mex} \{ g(i) \oplus g(n-i-2) : 0 \leq i \leq n-2 \}, $$
其中$g(0) = g(1) = 0$。整个游戏的SG值即为每个部分的SG值之异或。
从而,Alice必胜,当且仅当以下条件之一成立:
- 0的个数比1多。
- 0与1一样多,并且整个游戏的SG值不为0。
最后,$g(n)$在计算前若干项后,是一个周期为34的序列(参见OEIS A002187),可以$O(n)$预处理。
代码:code
例题2
在$n$行$m$列的格子上,每行选择两个不同的格子放置分别仅能由Alice和Bob操控的棋子(每行总共有$m(m-1)$种放置方式)。Alice先行。
- Alice所能操控的棋子仅能向左移动(至少一格),且不能跨越Bob所能操控的棋子,并且不能移动到格子以外。
- Bob所能操控的棋子仅能向右移动(至少一格),且不能跨越Alice所能操控的棋子,并且不能移动到格子以外。
无法操作者失败。
求Alice能获胜的所有局面的数量。
解法:
每行的放置方式有两种:
- Alice的棋子在Bob的棋子左侧。此时双方的最佳策略均是向对应方向移动一格。
- Alice的棋子在Bob的棋子右侧。此时双方共享所有可移动的格子,这些格子即可看作取石子游戏(nim game)中的石子。
于是,游戏划分成了两个部分,一个部分的最佳策略是仅移动一格;二另一部分则是取石子游戏。
继而,如果仅考虑【Alice的棋子在Bob的棋子左侧】的所有行,统计Alice能移动的次数$A$和Bob能移动的次数$B$。那么,
- 如果$A>B$,则Alice胜。
- 如果$A<B$,则Bob胜。
这是因为,获胜的一方的必胜策略是先去按最佳策略进行取石子游戏。取石子游戏的特殊之处在于,必输的一方至多只会比对方差一步。因此,即便是取石子游戏的部分输了,也能通过另一部分游戏的优势锁定胜局。
因此,Alice获胜,当且仅当以下条件之一成立:
- $A>B$。
- $A=B$且取石子游戏部分的SG值不为0。
接下来,考虑每种放置方式$(i, j)$,其中$i$表示Alice的棋子位置,$j$表示Bob的棋子位置。
- 如果$1\leq i<j \leq m$,Alice的优势(即对$A-B$的贡献)为$i+j-m-1$,对取石子游戏的SG值的贡献为$0$。
- 如果$1\leq j<i \leq m$,Alice的优势(即对$A-B$的贡献)为$0$,对取石子游戏的SG值的贡献为$i-j-1$。
考虑生成函数
$$ f(x, y) = \sum_{i} \sum_{j} a_{i,j} x^i y^j, $$
其中$a_{i,j}$表示Alice的优势为$i$且对取石子游戏的SG值的贡献为$j$的放置方案数(单行)。
定义,
$$ f(x, y) \otimes g(x, y) = \sum_{i} \sum_{j} \sum_{i'} \sum_{j'} a_{i,j} a_{i', j'} x^{i+i'} y^{j \oplus j'}. $$
那么
$$ f^{\otimes n}(x, y) = \sum_{i} \sum_{j} b_{i,j} x^i y^j $$
即为$n$行游戏的生成函数。根据定义,Alice必胜的局面数为
$$ \sum_{i > 0} \sum_{j} b_{i, j} + \sum_{j \neq 0} b_{0, j}. $$
代码:code 复杂度$O(nm^2(\log n + \log m))$。
标签:游戏,sum,博弈论,个数,Alice,先手,棋子,Bob,解析 From: https://www.cnblogs.com/TinyWong/p/16613458.html