博弈论

· · 个人记录

（〇）引言

博弈论，又称为对策论（Game Theory）、赛局理论等，既是现代数学的一个新分支，也是运筹学的一个重要学科。

在竞赛中，有时看待博弈论一类的题目时感觉无从下手，甚至无法理解什么是“必胜策略”。本文将深入浅出地探究博弈论的内在逻辑。

（一）一些重要概念

为了更好地理解什么是博弈论，什么是一个局面下的“必胜”或者“必败”状态，提前引入一些\operatorname{sg}函数中的概念。

如果我们将博弈中每一种可能出现的情况看做一个点，对于任意可以转换的两个点之间连一条有向边。例如，假设当前的局面为A，经过一次操作后，状态可以变为B，那么就连一条A\to B的有向边。

定义某个点的先手是第一个到达该点者，后手是第二个到达该点者。（本文的博弈只有两方）

对于所有的点，我们可以将其分为两类：

1.必胜点：指到达这个点后，无论后手作出怎样的选择，先手都会胜利。（即存在当前先手的必胜策略）

2.必败点：指先手到达这个点后，后手存在可以到达必胜点的方法。（即存在当前后手的必胜策略）

记必胜点对应的状态是必胜态，必败点对应的状态是必败态，那么：

P-position：必败态(简记为P)，即Previous-position,可以直观的认为处于这种状态的人一定会输。

N-position：必胜态(简记为N)，即Next-position，可以直观的理解为处于这种状态的人一定会赢。

容易看出，必胜点和必败点是相互关联的。它们的内在联系是：

  1. 无法移动的状态(即terminal-position)为P
  2. 可以移动到P的局面为N
  3. 所有移动都会进入N的局面为P

无法移动的状态就是游戏终局，根据规则，进入终局者输（即无法移动者输）。