博弈论
特点
- 两个以上玩家
- 状态为有限的集合
- 双方轮流操作
- 具有规则
- 有限次操作结束
- 有胜负
- 两人足够聪明
必定点
必胜(败)点:在该点进行操作的人必胜(败)
属性
$1.$ 所有终结点为必败点
$2.$ 每个必胜点至少有一个操作进入必败点
$3.$ 必败点只能走入必胜点
图示
巴什博弈
$2$ 人, $n$ 枚石子,双方轮流选取,不能拿或且不可拿超过 $x$ 枚,没石子可拿的人就输了
这个问题由于两个人一定足够聪明,他们会有一种“跟着选”的策略
即:如果当前石子数为 $x+1$ 的倍数,那么如果一个人拿了 $a$ 个,那么第二个人只要跟着拿 $(x+1)-a$ 个就一定可以赢
那么如果 $n$ 是 $x+1$ 的倍数,那么第一个人就一定会输
同时如果不是的话,第一个人可以把这 $n$ 个石子变成 $x+1$ 的倍数,他就一定可以获胜了
尼姆博弈
$2$ 人,多堆石子,每个人选取其中一堆石子取走任意个石子
三堆石子分析
$(0,0,0)$ 必败
$(0,0,x)$ 必胜
$(0,1,1)$ 必败
$(0,x,x)$ 必败
$(x,y,z)$ $?$
尼姆和
按位的异或(上面是 $x\oplus y\oplus z$)
其中 $0$ 必败,否则必胜
证明: 例如三堆石子为 $13,12,8$
\(\frac{\begin{aligned}13&=1101_2\\12&=1100_2\\\oplus\;\;\;\;8&=1000_2\end{aligned}}{nim\_sum=1001_2=9}\)
如果有方法令 $9$ 变成 $0$ 则必胜(属性 $②$ )
可以令第一个数变成 $0100$ ,则
\(\frac{\begin{aligned}13&=0100_2\\12&=1100_2\\\oplus\;\;\;\;8&=1000_2\end{aligned}}{nim\_sum=0000_2=0}\)
朴素做法:结果从前往后,第一个 $1$ 上面一定是有奇数个 $1$ ,选择一行该位置为 $1$ 的,这个位置变成 $0$ ,后面再遇到选取同行并取反
$\therefore$ 满足
如果任意方法都会让结果非 $0$ 则必败(属性 $③$ )
本身已经是 $0000$ 平衡了,即任意位置都有偶数个 $1$
操作后必定会改变其中一列的 $1$ 的个数成为奇数个,打破平衡使结果非 $0$ ,必败
$\therefore$ 满足
问题
$Question$ | $Answer$ |
---|---|
判断先手输赢 | 根据起始状态的尼姆和 |
求先手拿石子可赢的方案数量 | 看尼姆和第一位 $1$ 上面有多少个 $1$ ,因为不可以加石子 |
$SG$ 函数
$x$ 节点的 $sg$ 值是不等于 $x$ 后继节点的 $sg$ 值的最小非负整数
即: $sg(x)=mex({sg[son_x]})$
其中 $0$ 必败,否则必胜
证明:看巴什博弈(最多可以拿三个)
终结状态 $sg$ 必 $0$ ,非零必胜 (属性 $①$ )
能转移到 $0$ 的均必胜(属性 $②$ ),在 $sg$ 内必定不为 $0$
不能转移到 $0$ ,即必须转移到正整数,本身一定是 $0$ ,必败(属性 $③$ )
例
$1$
$3$ 堆石子, $5,7,9$ 个。轮流拿石子,必拿但不超过三个。讨论先手的输赢
看作 $3$ 个巴什博弈:
$sg(5)=5\%4=1$
$sg(7)=7\%4=3$
$sg(9)=9\%4=1$
多用尼姆和与 $sg$ 函数相结合,全局输赢 $=sg(x_1)\oplus sg(x_2)\oplus\dots\oplus sg(x_n)$
本问题中讨论即 $res_sg$ 为 $0$ 则先手必败,否则先手必胜
$2$
给定规则数 $n$ ,即可以拿走 $a[1~n]$ 个石子
给定情况数 $m$ ,每种情况有 $o$ 堆牌,每堆 $x[1~o]$ 张,讨论每种情况的先手输赢
程序采用记忆化搜索
int n, m; // 规则数,情况数
int a[100]; // 规则
<br>
int sg[10001];
inline int SG ( int all ) {
bool vis[101] = {0};
for ( int i = 0; i < n; i ++ ) {
int remain = all - a[i]; // 剩余的石子数
if (remain < 0) break; // 少于0个不存在
if ( sg[remain] == -1 ) sg[remain] = SG(remain); // 继续递归子状态的sg值
vis[sg[remain]] = 1; // 子状态sg值标记一下
}
for ( int i = 0; ; i ++ ) if ( !vis[i] ) return i; // sg定义
}
int main () {
cin >> n;
for ( int i = 0; i < n; i ++ ) cin >> a[i];
sort(a, a + n); // 可以在sg内部选取拿走的石子数量上进行 break 优化
memset(sg, -1, sizeof sg);
sg[0] = 0;
cin >> m; while ( m -- ) {
int res_sg = 0;
int o; cin >> o; while ( o -- ) {
int x; cin >> x;
if ( x == -1 ) sg[x] = SG(x);
res_sg ^= sg[x];
}
if ( res_sg == 0 ) cout << "先手必败" << endl;
else cout << "先手必胜" << endl;
}
}