Chlience

【算法】基本博弈与SG函数
组合博弈论 三大基本博弈在组合博弈中,一切信息都是透明的,也就是说,存在着一种确定的必胜策略,若参赛双方都按照最优...
扫描右侧二维码阅读全文
31
2019/01

【算法】基本博弈与SG函数

组合博弈论 三大基本博弈

在组合博弈中,一切信息都是透明的,也就是说,存在着一种确定的必胜策略,若参赛双方都按照最优操作进行,那么其局面对应的胜者是确定的

定义两个状态:

先手必胜 $N-position$
后手必胜 $P-position$

若一个状态的后续中存在后手必胜状态,则该状态为先手必胜
若一个状态的全部后续均为先手必胜,则该状态为后手必胜

巴什博奕(Bash's Game)

给定 $n$ 个筹码,两人轮流取筹码,每次取不超过 $m$ 个,取完所有筹码的一方获胜

这是最为经典和常见的博弈问题,在小学奥数题中便有提及

考虑简单的情况:当 $n\leq m$ 时,为先手必胜

$n=m+1$ 时,无论先取者拿多少个,后取者都能一次取完,为后手必胜

那么如果将 $n$ 表示为 $(m+1)*k+c$,$0< c<m+1$ 的形式,只要先手将 $c$ 取完,无论后手每次取多少个,先手只需要将其补到 $m+1$ 个,那么这是先手必胜的

同样,如果 $n$ 表示为 $(m+1)*k$ 的形式,先手不管取多少个,后手只要将其补到 $m+1$ 个,那么这是后手必胜的

威佐夫博弈(Wythoff's Game)

两人轮流取两堆筹码,其中取法有两种:取走一堆中任意个筹码,或从两堆中取走相同数目的筹码。取完所有筹码的一方获胜(考虑一开始就没有筹码的情况或者说无法行动者失败?)

可以用两个正整数 $(n,m)$ 来刻画当前局面

显然 $(0,0)$ 是后手必胜的

将所有后手必胜的状态写出来,大概是:$(0,0),(1,2),(3,5),(4,7),(6.10),(8,13),(9,15)...$

图中红色点即为后手必胜状态

在这里给出这个序列的构造方法:设状态 $(a,b)$ ,其中 $a\leq b$ ,对于第 $i$ 个先手必胜状态 $(a[i],b[i])$,有 $a[0]=b[0]=0,a[i]$ 为第一个前面没有出现的正整数, $b[i]=a[i]+i$

对于这些状态,显然有这样的性质:

  1. 每个 正整数 出现且仅在一个状态中出现一次
  2. 任何操作都能将后手必胜转化为先手必胜
  3. 存在一个操作使得先手必胜变为后手必胜

首先证明性质1

显然, $a[i]$ 不可能等于 $b[j],j<i$ ,这是由定义决定的
其次, $a[i]$ 不可能等于 $b[j],j\ge i$ ,因为 $b[i]=a[i]+i>a[i]$

接着证明性质2

如果当前为后手必胜状态
若从某一堆中取任意个筹码,由性质一得其必定不是后手必胜状态
若从两堆同时取任意个筹码,因为 $b[i]-a[i]=i$ ,不可能存在另外一组状态使得 $b[j]-a[j]=i$ ,所以其必定不是后手必胜状态

最后证明性质3

假设 $a=b$ 直接取走所有筹码即可
设 $a<b$

若 $a=a[k],b>b[k]$
那么将 $b$ 中多余的 $b-b[k]$ 去掉即可
若 $a=a[k],b<b[k]$
那么我们需要找到差为 $b-a$ 的一组状态,这组状态必然比 $k$ 靠前,也就是 $(a[b-a],b[b-a])$ ,此时 $a,b$ 均减去 $a-a[b-a]$ 即可

若 $a>a[k],b=b[k]$
将 $a$ 中多余的 $a-a[k]$ 去掉即可
若 $a<a[k],b=b[k]$
既然 $a$ 在 $a[]$ 中没有出现,那么必然在某个 $b[]$ 中出现,设 $a=b[j],j<k$
那么直接将 $b$ 减去 $b-a[j]$ ,作为新的 $a$ 位置即可

如何判断某个局面是否为后手必胜状态

威佐夫发现后手必胜状态与黄金分割率有关
具体而言,若k为任意自然数且存在

$$ a_k=\lfloor k\phi\rfloor,b_k=\lceil a_k\phi\rceil $$

那么这是一组后手必胜状态,随便判断下就好了...吧

尼姆博奕(Nim's Game)

两个玩家轮流从不同的堆中移除筹码
在每个回合中,玩家必须移除至少一个筹码,前提是它们都来自同一堆
取完所有筹码一方获胜

显然,通过定义,可以利用记忆化搜索,从最开始的 $P-position$ 或者 $N-position$ 开始,每个局面查询其后继局面的状态以确定当前的状态

但是,这样的复杂度通常是不可接受的,它常常可以达到 $3^{\frac{n}{3}}$ 级别

所以需要一个更高效的判断方法

对于 $Nim$ 游戏,局面是后手必胜当且仅当所有堆筹码的异或和起来为 $0$
这里用 $\oplus$ 代替异或运算

为了证明这个结论,只需要保证

  1. 无法移动的局面为后手必胜
  2. 任何操作都能将后手必胜转化为先手必胜
  3. 存在一个操作使得先手必胜变为后手必胜

要求1显然

要求2:对于某个局面 $(a_1,a_2,\cdots,a_n)$ ,有 $a_1 \oplus a_2\oplus\cdots\oplus a_n=0$
那么一定不存在某个合法的移动 $a_i \rightarrow a_i'$,使得 $a_1 \oplus a_2\oplus\cdots\oplus a_i \oplus\cdots\oplus a_n=0=a_1 \oplus a_2\oplus\cdots\oplus a_i' \oplus\cdots\oplus a_n$
否则, $a_i=a_i'$ 与原假设矛盾
所以说任意操作不可能使得后手必胜转移到后手必胜,满足要求

要求3:对于某个局面 $(a_1,a_2,\cdots,a_n)$ ,有 $a_1 \oplus a_2\oplus\cdots\oplus a_n=k$
那么至少存在一个 $a_i$ 在 $k$ 的最高位上是 $1$
显然 $a_i'=a_i\oplus k<a_i$

证毕

SG函数

这样一类博弈问题,可以抽象到有向图上

给定一个有向无环图和一个起始点上的一枚棋子,两个选手交替的将这枚棋子沿着有向边进行移动,无法移动者失败

也就是说,将原有的每个局面看做一个顶点,每个局面和它的子局面用边连一条有向边

定义关于图的每个顶点的 $SG$ 函数 $g$ : $g(x)=mex\{g(y)|y=x.son\}$ ,其中 $mex(S)$ 是指集合 $S$ 中没有出现的第一个非负整数

首先来看看 $SG$ 函数的性质

  1. 所有没有出边的点,即结束点,显然其 $SG$ 函数为 $0$
  2. 对于所有 $g(x)\neq0$ 的点,必然至少存在一个点使得 $g(y)=0|y=x.son$
  3. 对于所有 $g(x)=0$ 的点,必然不存在点 $g(y)=0|y=x.son$

满足 $N-position/P-position$ 的定义
那么只需要计算出每个节点的 $SG$ 值,便可得知每个节点局面状态

$SG$ 函数为 $0$ 的节点是后手必胜的
$SG$ 函数不为 $0$ 的节点是先手必胜的

但是如果一次有多个游戏/多个点呢?

再来考虑下 $SG$ 函数的意义:当 $g(x)=k$ 时,我们可以将其转移到 $[0,k-1]$ ,但是不能转移到 $k$ ,是不是和 Nim's Game 很像?

相当于将每个点的 $SG$ 函数放在一起,相当于一个 Nim's Game 的状态,那么这个 Nim's Game 的必胜策略就对应着这多个游戏/多个点的必胜状态

所以说,游戏的和的 $SG$ 函数值即它所有子游戏的 $SG$ 函数值的异或

那么,我们可以将一个比较复杂的公平组合游戏化为很多个简单的子游戏,根据每个子游戏的异或值进行必胜策略的决策,从而化简问题

Last modification:January 31st, 2019 at 03:16 pm

Leave a Comment