不平等博弈与超现实数(Surreal Number)

Hydroxythio · 2021-03-29 22:19:39 · 个人记录

一些闲话

~~大概是退役之前最后一次写博客了虽然就没写过几次~~。

~~请忽视上面的话。因为某些原因又写了点东西~~。

打模拟赛的时候遇到了一道不平等博弈的题，就顺便研究了一下。

由于本人才疏学浅，如果有一些错误或者疏漏还请见谅。

应该也可以在 Cooper233 巨佬的博客里面看到这些内容（~~不知道他咕没咕~~）。

一些定义

不平等博弈

与平等博弈（公平组合游戏）相对。在 OI 中，一般指这样一类问题：

两人参与，轮流决策，双方均知道游戏的完整信息。
同一状态不可多次到达，无法继续决策的游戏者输，游戏在有限步内一定可以以非平局结束。
游戏者可以做出的决策不同。

超现实数（Surreal Number）

Warning：下面关于超现实数的内容大多是不严谨的，属于感性理解，对于 OI 而言已经够用。严谨的定义还请移步这里。

定义

我们可以这样理解超现实数：一个超现实数 x 是由两个超现实数的集合“拼”在一起组成的，这两个超现实数的集合称为“左集合”和“右集合”，记为 XL,XR。一般地，x = \{XL | XR\}。

超现实数存在一个与实数一一对应的关系，因此在下文中，我们将会借助实数来理解超现实数，并把 XL,XR 理解为两个实数集合（集合内的实数即为超现实数对应的实数）。

记 l = \max(XL), r = \min(XR)（即实数集 XL 中的最大元素和实数集 XR 中的最小元素），特别地，若 XL = \emptyset，那么 l = -\infty，若 XR = \emptyset，那么 r = \infty，一个超现实数 x 合法，当且仅当 l < x < r（这里的 x 指超现实数 x 对应的实数）。

为了方便，在下文中如果出现实数集与超现实数之间的比较，我们均认为是这个实数集中的任意一个元素与这个超现实数对应的实数之间的比较。

偏序关系

假设现在我们有两个超现实数 x = \{XL|XR\},y = \{YL|YR\}，定义偏序关系 \leq，那么有 x \leq y 当且仅当 XL < y \wedge x < YR。

达利函数

如下定义从实数映射到超现实数的达利函数 \delta(x)：（即 x 是一个实数，\delta(x) 是一个超现实数）

\delta(x) = \begin{cases} \{|\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x = 0 \\ \{x-1|\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x \in Z^+ \\ \{|x+1\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x \in Z^- \\ \{\frac{j-1}{2^k}| \frac{j+1}{2^k}\} \ \ \ \ \ x = \frac{j}{2^k},j \in Z,k \in Z^+ \end{cases}

不难发现对于某些实数无法通过达利函数映射到超现实数，同样也不是所有超现实数都可以通过达利函数来表示，但是在 OI 中，这个玩意就已经够用了。

（重点）超现实数映射到实数

对于一个超现实数 x = \{XL|XR\}，我们试图将其映射到实数。记 SN(x) 表示 x 对应的实数。

首先还是记 l = \max(XL), r = \min(XR)，特别地，若 XL = \emptyset，那么 l = -\infty，若 XR = \emptyset，那么 r = \infty，分以下情况讨论：

若 l < 0 \wedge r > 0，那么有 SN(x) = 0。
若区间 [l,r] 之间存在一个整数，那么：
- 若 0 \leq l，那么 SN(x) = \lfloor l + 1 \rfloor。
- 否则一定有 r \leq 0，那么 SN(x) = \lceil r - 1 \rceil。
否则区间 [l,r] 之间不存在一个整数，那么 SN(x) = \frac{k}{2^j}，满足：
- 在所有满足条件的 j,k 中，优先使 j 最小，如果仍有多个，使 k 最小。

下面我们不再以 x = \{XL|XR\} 来表示一个超现实数（除了加法那部分），等价的，我们将其表示为 x = \{l|r\}（这里的 l,r 与上面的定义相同）。

举四个例子分别对应上述四种情况（按顺序排列）：

\begin{aligned} SN(\{|666\}) &= 0 \\ SN(\{\frac13 | 666\}) &= 1 \\ SN(\{-114514 | -\frac{19}7\}) &= -3 \\ SN(\{\frac{1}{919}|\frac{8}{10}\}) &= \frac12 \end{aligned}

超现实数的加法

现在我们有两个超现实数 x = \{XL|XR\},y = \{YL|YR\}，如下定义超现实数 x + y：

令 L,R 分别表示得到的超现实数的左集合，右集合，那么有：

\begin{aligned} L &= \{u + y | u \in XL\} \cup \{x + v| v \in YL \} \\ R &= \{u + y | u \in XR\} \cup \{x + v | v \in YR\} \end{aligned}

~~不难发现这个定义非常抽象所以~~接下来我们尝试在用 x=\{l|r\} 来表示超现实数的情况下定义超现实数的加法。

令 x = \{xl|xr\}, y = \{yl|yr\}，于是我们得到：x + y = \{\max(xl+y,yl+x)|\min(xr+y,yr+x)\}。

再尝试把 x+y 映射到实数上，~~显然我们不会真的去大力讨论所以抄结论~~得 SN(x+y)=SN(x)+SN(y)。

（重点）超现实数与不平等博弈之间的关系

假设现在有两个玩家 L,R。

假设我们用一个超现实数 x 来描述现在的局面。

假设玩家 L 所有后继状态局面对应的超现实数的集合为 XL，玩家 R 所有后继状态局面对应的超现实数的集合为 XR。

那么 x = \{XL|XR\}。

同理我们可以把 XL,XR 看做数集，也可以把 x 写成 x = \{l|r\}，也可以把 x 映射到实数 SN(x) 上。

那么接下来，一个极其重要的结论：

若 SN(x) > 0，则该局面为玩家 L 必胜。
若 SN(x) < 0，则该局面为玩家 R 必胜。
否则一定有 SN(x)=0，该局面为后手必胜。

然后又是一个极其重要的结论：

如果一个不平等博弈可以分解为多个子游戏，那么这个不平等博弈的 SN 值等于各子游戏的 SN 值的和。

然后就可以做题了。

一些例题

~~暂时只有一道，后续可能会加~~。

POJ 2931

简易题意

一个局面由四堆棋子构成，棋子有黑白两种颜色。
两位玩家 L,R 轮流操作。每轮操作者都必须选择一枚棋子，且 L 只能选择白棋，R 只能选择黑棋。操作者选定一枚棋子后，可以把这枚棋子及其上方的所有棋子移走。不能操作者输掉游戏。
称一个局面对 L 有利，当且仅当这个在局面下，L 无论先手还是后手都能获胜。称一个子局面 C 为给定的三堆棋子，并且一个局面可以表示为 (C,T)，其中 T 是另一堆棋子。称一个子局面 C_1 不比另一个子局面 C_2 更劣，当且仅当对于任意的一堆棋子 T，若局面 (C_2,T) 对 L有利，那么局面 (C_1,T) 也 对 L 有利。
给定两个子局面 C_1,C_2，子局面中每堆棋子均按从下到上的顺序给出，判断子局面 C_1 是否不比子局面 C_2 更劣。如果是，输出 Yes，否则输出 No。

解答

不难发现这是一个不平等博弈，并且一个局面可以分解为四个子游戏（每一堆棋子是一个子游戏）。

于是我们来考虑一堆棋子的 SN 值。

规定初始状态为 \{|\}，此时后手必胜，那么有 SN(\{|\}) = 0。

接下来加棋子的过程均从下往上考虑。

考虑加一个白棋，那么此时的 SN = \{0|\} = 1。

加 k 个白棋，那么此时的 SN = \{0,1,2,\cdots,k-1|\} = k。

如果是加一个黑棋，那么 SN = \{|0\} = -1。

加 k 个黑棋， SN = \{|0,-1,-2,\cdots,1-k\} = -k。

观察一下，如果从初始状态开始加 k 个棋子，颜色都相同，那么 |SN| = |k|，白棋取正，黑棋取负。

假设现在的局面的 SN 为 k（即加了 k 个白棋），考虑加一个黑棋：SN = \{k-1|k\} = k - \frac12。

再加一个黑棋：SN = \{k-1|k-\frac12\} = k - \frac34 = k - \frac12 - \frac14。

再加一个白棋：SN = \{k-\frac34|k-\frac12\} = k - \frac12 - \frac14 + \frac18。

总结一下，在加了第一个异色棋子之后，再往后加不管是跟上一个同色还是异色，对 SN 的贡献均是 \pm \frac1{2^k} 的形式，其中 k = 当前位置-第一个异色棋子位置+1 ，黑棋取负，白棋取正。

然后把两个子局面的 SN 算出来，若 SN(C_1) < SN(C_2)，答案是 No，否则答案是 Yes。

时间复杂度 O(n)。

贴个码，注意没加多测：

#include <stdio.h>

typedef long long ll;

const int MAX_N = 50 + 5;

int len[3], a[MAX_N];
char s[MAX_N];

ll calc(ll N) {
    int i;
    ll res = 0, Base = 1ll << 50;
    for (i = 1; i <= N && a[i] == a[1]; i ++)
        if (a[i]) res += Base;
        else res -= Base;
    for (Base >>= 1; i <= N; i ++, Base >>= 1)
        if (a[i]) res += Base;
        else res -= Base;
    return res;
}

ll solve() {
    ll sn = 0;
    scanf("%d%d%d", len, len + 1, len + 2);
    for (int i = 0; i < 3; i ++) {
        for (int j = 1; j <= len[i]; j ++) {
            scanf("%s", s);
            a[j] = s[0] == 'W';
        }
        sn += calc(len[i]);
    }
    return sn;
}

int main() {
    ll sn0 = solve();
    ll sn1 = solve();
    if (sn0 < sn1) printf("No\n");
    else printf("Yes\n");
    return 0;
}