一类不公平博弈总结
以下简称超现实数 Surreal Numbers 为 SN 。
超现实数完整的理论很复杂,这里不详细给出。
超现实数与游戏
一个 SN 可以表示为
若
这样定义 SN 的偏序关系,
一个游戏
简单的情况
不加证明的给出以下重要的性质,实践中往往将 SN 用普通的实数表示,当然不是所有 SN 都能对应到一个实数的,实数域只是超现实数域的一个子集。
- 对于 SN
,有 ,即加法单位元。 - 对于 SN
,如果集合 存在最大值 ,则 。 - 对于 SN
,如果集合 存在最小值 ,则 。 - 对于 SN
, 的值可以由一颗特殊的树确定, 是值在 和 之间的最浅的点(不包括 ),这棵树长这样:
- 对于 SN
, 是值大于 的最浅的点。 - 对于 SN
, 是值小于 的最浅的点。
直观上,可以将一个能对应到实数的 SN 理解为左玩家可以自由操作的次数减去右玩家可以自由操作的次数。
一个游戏可以看做一个 SN
- 如果
,那么左玩家必胜。 - 如果
,那么右玩家必胜。 - 如果
,那么先手必败。 - 如果
和 没有偏序关系,那么先手必胜(这个情况稍后讨论)。
以上四点的逆命题也是成立的。
如果一个游戏
和 0 可以确定偏序关系的
例如公平博弈下的 SG 定理,子游戏的加是 SG 值的异或,事实上公平博弈的游戏对应的 SN 只能是 0 或者是与 0 没有偏序关系的数。
其他的一些性质:
- 对于 SN
,其加法逆(相反数)为 。
更复杂的情况
之前提到过,有些游戏状态对应的
这里要引入三个基本的量:
不难看出
不加证明的给出以下性质:
小于所有正实数且大于所有负实数,与 0 没有偏序关系。 小于所有正实数且大于 0 。 大于所有负实数且小于 0 。 ,也就是说 的逆是其本身。 ,通常记做 , 时与 0 没有偏序关系,否则 当且仅当 。
另外,对于 SG 值为
可以从这些量的角度研究博弈,同样可以从博弈的角度研究这些量。
例如要证明
其他的一些性质:
更更复杂的情况
然而即使有了
由于游戏
例如 Nim 游戏的 mex 规则和 SG 定理,这些东西直接拿超现实数或是
因此,还是要具体问题具体分析。
推荐读物
这里只是总结,希望具体了解超现实数和博弈的关系的话可以去看这些东西。
Gitalk 加载中 ...