博弈论笔记

Conan15 · 2024-12-14 16:40:50 · 算法·理论

零、前言

NOIP2024 挂大分了。\ fz \to xm 为了防止心态崩溃就找了个专题学学转移注意力。

往事流转在你眼眸\ 一边遗忘一边拼凑\ 如我虔诚合十双手\ 唯愿你能得到拯救

一、博弈论基础

定义

对于一个游戏局面，有两个玩家 A,B 分别对它操作，最后的结果是先手必胜或后手必胜，双方的操作方式和目的相似。

本文将必胜态记为 S，必败态记为 T。

必胜态：当前游戏局面存在至少一种操作方案使得游戏局面变为必败态。
必败态：当前游戏局面的所有操作方案都会使得游戏局面变为必胜态。
子游戏：将原游戏拆分成若干个同时进行的游戏，可以随机挑选一个子游戏进行操作。

Nim 游戏

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

二、一些常用思想

1. 从最简单情况开始思考

对于 Nim 游戏进行分析。

这里约定用 \{3\} 表示总共有 1 堆石子，这堆石子有 3 个，同理 \{2,3\} 表示有 2 堆石子分别为 2,3 个。

最简单的是 n=1，显然先手必胜。
然后考虑 n=2，最简单的是两堆石子相等，这里开始变得较为复杂了，所以引入第二种思想。

2. 后手抵消先手

即后手可以通过模仿先手的操作，使得先手的操作无效。

对于 n=2 石子数量相等的情况，设两堆分别为 A,B。先手在 A 拿走 x 个，则后手也在 B 拿走 x 个。
此时后手可以通过这样的操作保证两堆石子数量相等，到最后一定是先手必败。
否则显然是先手必胜，因为先手可以先进行一步操作使得后手面临两堆石子相等的必败态。

3. 子游戏

如果一个局面是 \{T,T\}，即两个子游戏都是必败态，那么显然先手必败。
- 假设先手任意选择一个子游戏进行操作，则后手陪它玩这个子游戏，直到先手输了操作另一个子游戏，最后一定先手必败。
如果局面是 \{S,T\} 或 \{T,S\} 呢？
- 先手一定能通过操作一次 S 使得局面变为 \{T,T\}。
- 即后手必败，先手必胜。
如果局面是 \{S,S\} 又会怎样呢？
- 这并不确定。
- 首先注意一下必胜态可以转移到必败态，也可以转移到必胜态。
- 先手一定不会选择转移到必败态，因为转移后 \{S,T\} 就会使得后手必胜，先手必败。
- 然而一个必胜态有多少个后继必胜态是未知的，所以无法确定。

这里重新思考一下，令 S=1,T=0，则有：

这个东西看上去很像或运算或者异或运算。

这里直接给出结论：所有石子数量异或和如果是 0 先手必败，否则先手必胜。

三、SG 函数（重点）

对于任意一个子游戏 u，定义 sg(u) = mex \{sg(v) | u \to v \}，u \to v 表示可以从 u 局面转移到 v 局面，mex 表示集合内未出现的最小非负整数。

Nim 游戏可以直接异或的原因是 sg(u)=u，实际上是做 sg(u) 的异或和。\ 为什么 sg(u)=u？因为 u \to v 中 v 满足 0 \leq v \lt u，所以 sg(u) = mex \{sg(v)\} = u。\ 对于一个游戏局面，如果所有子游戏的 sg 异或和为 0，则先手必败，否则先手必胜。

四、解题思路

1. 暴力求解 sg 值

按照定义和题目大意做，对每个局面记一个 mex 桶，依靠后继状态求出每个局面的 sg 值。

例题：POI2000 Stripes

有一排石子共 L 个，两人交替操作，每次可以选连续一段 A,B 或 C 个石子，不能取石子的输，问先手是否必胜。\

SG 板子题，直接枚举局面，枚举选 A,B,C，枚举从哪里开始选，然后分割成左右两个子游戏做，异或得到 sg 值。

2. 拆分为子游戏

如何设计子游戏？
如何求出子游戏的 sg 值？
把子游戏合并。

例题：P3185 [HNOI2007] 分裂游戏

首先第一个问题是：怎么设计 sg 值？\ 首先观察到：如果设 sg(x) 表示一堆 x 个石子。但显然会出现一个问题：在第一堆和在最后一堆的 x 个石子它的意义是不一样的，因为分裂往后放的选择和机会都不均等。\ 而且这题和 Nim 游戏不一样，首先它可以加石子，而 Nim 只能减；其次这题跟位置有关。

考虑后手抵消先手，设先手从 i 拿，在 j,k 放，那么后手也这么做，于是这就和奇偶性相关。\ 后手可以一直模仿先手直到先手把唯一一颗石子拿走。这意味着如果后手可以一直模仿先手，那么就必胜，因为先手每次操作完后手一定能操作。\ 综上，在第 i 堆取石子，有 2 个和有 4 个本质上是相同的，即只需要考虑奇偶性。\ 那么 a_i 序列就变成了 01 序列，表示偶数或奇数。

既然答案和位置有关系，那么就设 sg(i) 表示一个石子在 i 位置的 sg 值。\ （这里 a_i 已经对 2 取模）对于 a_i=0，肯定不改变后面石子的奇偶性，因为后手不断模仿先手。\ 对于 a_i=1 呢？枚举 j,k，然后把 sg(j),sg(k) 异或扔进桶里做 mex。

做完了吗？还要知道第一步有多少种取法，怎么取。\ 从初始状态枚举每个状态，看哪些状态 $sg$ 是 $0$（即必败态），然后暴力枚举求方案数。 ## 3. 转化为 Nim 游戏 > #### 例题：Northcott Game > 有一个 $n$ 行 $m$ 列（$1 \leq n \leq 1000, 2 \leq m \leq 100$）的棋盘，每行有一个黑棋子（先手）和一个白棋子（后手），每次可以把某一行自己的棋子移动到同一行任意一格，但不能越过对方的棋子。不能移动的人输，求先手是否必胜。 Nim 游戏的变种。观察到如果黑棋和白棋紧贴，黑棋先手，那么白棋只需要接着紧贴黑棋（后手模仿先手）即可。\ 所以把 $abs(x-y)-1$ 作为这一堆石子的数量，做 Nim 游戏即可，其中 $x,y$ 分别为这一行中黑棋和白棋的位置。 ## 4. 找规律求解 $sg$ 函数复杂度太高时可以通过找规律降低复杂度。 > 例题：A Simple Nim\ > 有 $n$ 堆石子，两人轮流操作，可以任选操作类型，操作有两种： > 1. 把一堆 $\geq 3$ 的石子分为三堆。 > 2. 从一堆石子内取走若干个。\ > 有 $T$ 组多测，$T \leq 100, 1 \leq n \leq 10^6, 1 \leq a_i \leq 10^9$。 $a_i$ 太大了，所以打表找规律，然后直接干即可。 > 例题：巴什博弈本质上也是推 SG 函数然后找规律。