进阶博弈论

基本定理

一、必胜点与必败点

• \(P\)点：必败点， 在双方都无比聪明的情况下，当前先手的人必败的情况。
• \(N\)点：必胜点，在双方操作都正确的情况下，先手必胜的位置。

几个性质

• 所有终止位置都是必败点。（可当做公理，即所有公式的推理都在这个性质成立的基础上进行）。
• 从任意一个必胜点\(N\)出发，至少有一种方式到达一个必败点\(P\)。
• 从一个必败点\(P\)出发，所有的移动都会到达必胜点\(N\)。

二、无偏博弈

无偏博弈是一类任意局势对于游戏双方都是平等的回合制双人游戏。这里平等的意思是所有可行的走法仅仅依赖于当前的局势，而与现在正要行动的是哪一方无关。换句话说，两个游戏者除了先后手之外毫无区别。此外还需要满足以下性质：

• 完全信息，任意一个玩家都能够知晓整个游戏状态。
• 无随机行动，所有的行动都会转移到一个唯一确定的状态。
• 在有限步内游戏会终止， 此时有位移的必胜者。

三、DAG中的博弈

给定一张有向无环图，在起始定点有一枚棋子，两个顶尖聪明的人交替移动这枚棋子，不能移动的人算输

不要小看这个游戏，事实上，所有无偏博弈问题都可以抽象为这种游戏(即把初始局面看做顶点，把从一个状态可以到另一个状态之间连边)。

SG函数

• SG函数：对于每一个状态的一个尼姆数的函数
• Sprague?Grundy 定理：所有一般胜利下的无偏博弈（定义在上面）都能够转化成尼姆数表达的尼姆堆博弈，一个无偏博弈的尼姆值定义为这个博弈的等价尼姆数。

首先来定义 mex 运算，这是一种集合中的运算，它表示最小不属于这个集合中的自然数。
\(mex \{0. 1, 2, 3\} = 4\)， \(mex \{2, 3 \} = 0\)， \(mex \{\emptyset \} = 0\)
那么我们有运算\(SG(x)=mex{SG(y),<x,y> \in E}\) (E 为边集)。即对于当前状态 x 的 SG 函数，它的值定义为所有的后继状态的 mex 值。

我们来看一下它的性质：

• 所有汇点的 SG 函数都为0。

这个性质比较显然，因为汇点没有后继状态，因此那个集合为空集，所以 SG 函数为 0。

• 当 \(SG(x) = 0\) 时，该节点为必败点。

由 SG 函数的性质可知， x 的后继状态都非 0。满足必败点的定义。

• 当 \(SG(x) \not = 0\) 时， 该节点为必胜点。

由 SG 函数的性质可知， x 的后继状态中只有一个必败点， 满足必胜点定义。

SG定理

游戏和的 SG 函数等于各个游戏 SG 函数的异或和。

翻译成人话就是：对于一个游戏 \(X\)，可以拆分成 n 个小问题， \(x_1, x_2, \dots, x_n\),
那么 \(SG(X) = SG(x_1) \oplus SG(x_2) \oplus \dots \oplus SG(x_n)\)。

至于证明的话...........不完全归纳法算不算。

小结

我只是大自然的搬运工。

进阶博弈论

原文：https://www.cnblogs.com/zzz-hhh/p/13627247.html