首页 > 其他分享 >先手的微弱优势——两道博弈论题的解析

先手的微弱优势——两道博弈论题的解析

时间:2022-08-22 18:15:26浏览次数:89  
标签:游戏 sum 博弈论 个数 Alice 先手 棋子 Bob 解析

博弈论的题往往可以通过直接计算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

相关文章