【笔记】博弈论

0 基本概念 & 性质

0.1 博弈论

1 SG 函数

ps. 通过 SG 函数来理解三个基本模型，也是不错的选择。

1.2 定义

\(\text{SG}(x)=\text{mex}\{\text{SG}(y_i)\}\)（其中 \(y_i\) 为 \(x\) 的后继状态）

1.3 SG 定理

由 \(n\) 个博弈图组成的游戏，设起点（即每个连通分量内入读为 0 的点）分别为 \(s_{1}, s_{2}, \dots, s_{n}\)。

当 \(\text{SG}(s_{1})\oplus\text{SG}(s_{2})\oplus\cdots\oplus\text{SG}(s_{n})\neq 0\) 时，先手必胜；反之，先手必败。

1.3.1 证明

2 三个基本模型

2.2 布什博弈

2.2.1 概述

2.2.2 结论

若 \(m+1\nmid n\)，先手必胜；反之，先手必败。

2.2.3 证明

构建决策树

3 例题

3.0 Links

博弈论1

博弈论2

3. 取石子

Key：

本质上是求 SG 值，但是由于最终不许要用 SG 定理，于是 SG 值可以就为 0/1 表示是否先手必胜

令 \(sum=\sum a_i\)

先单独考虑操作 1：若 sum 为奇，必胜；为偶，必败。

可以发现操作 2 其实相当于某人跳过了一次操作，而不改变。

性质 1： 操作 2 就是用来浪费时间的，所以如果可以做就尽量做 。

后继状态：（当前为 \((x,y)\) 表示：全是 1 的堆数 | 其余最多操作次数 = 大于 1 的堆的总和 + 堆数 - 1，特别地，空集 = 0）

1. 取走 1 个

   1. 取 x：\((x-1,y)\)

   2. 取 y：\((x,y-1)\)

      ps. y 中不到最后只剩一堆的时候，不会出现堆的个数变为 1 的（性质 1），所以可以直接减。

2. 合并

   1. 合两个 x：\((x-2,y+2+[y\neq 0])\)

      ps. 特判 y 原先为空集。

   2. 合两个 y：\((x,y-1)\)

   3. 合一个 x 和 一个 y：\((x-1,y+1)\)

注意判断，从 y 转为 x 的情况。

3. 小约翰的游戏

反 Nim 问题。

讨论：

1. 全为 1：n 为偶，必胜；为奇，必败。

2. 有一个不为 1：必胜。（本质上可以归类为 3）

   先手一定可以通过一次操作，将状态转化为偶数个 1。

3. 有多个不为 1：转化为了普通 Nim 问题

   先手想要把情况变为 2，即要把不为 1 的堆拿成只剩一堆，然后让自己处理，于是就转化为了普通 Nim 问题。

4 Trick

1. 有种奇怪的感觉：最后只剩 1 的时候都比较关键。