Hackenbush

Hackenbush 是由数学家 John Horton Conway 发明的一个双人游戏，他在组合博弈等领域颇有成果， 是组合博弈论的开创者之一，后面要讲到的 surreal number 也是他所定义和构造的。Hackenbush 有一条称之为 "ground" 的线（或者将其看作点，称之为根，这并没有什么区别）和一些端点，以及若干条线段，每条线段连接两个端点或者一个端点和 ground 线，并且每条线段都和 ground 连通。两个玩家轮流操作，每次选择一条线段删除，同时将那些和 ground 不再连通的线段也一并删除，不能操作的玩家失败。

在最初版本的 Hackenbush 中，每个玩家都可以删除任意一条线段，但在后来，又发明出了每条线段可以被配置成只能其中一个玩家删除的版本。一般来说，有三种版本：

• Original Hackenbush: 或者称之为 Green Hackenbush，只有绿色的边，即最初版本。
• Blue-Red Hackenbush: 蓝色的边只能由玩家一删除，红色的边只能由玩家二删除。
• Blue-Red-Green Hackenbush: 最复杂的版本。

而每种版本，也都还有着链、树和图三种不同复杂性的区别。

接下来，我将分别介绍这三种版本，并尽量给出易懂的过程证明。

nim 和

在三个经典博弈中，我们介绍了 \(\text{nim}\) 和，即异或和，一般用符号 \(\oplus\) 来表示这种操作。接下来，将介绍几种翻硬币游戏。以下内容大部分是我高中时从一篇博客中看到的，但好像找不到原博文了，放了个内容差不多的博客链接在下面，如果想了解更多可以看博客。

\(n\) 枚硬币排成一排，有的正面朝上，有的反面朝上，将其从左至右按 \(1\) 到 \(n\) 编号。A 和 B 轮流翻硬币，每次翻动时，所翻的编号最大的硬币必须是从正面翻到反面，除此之外，还必须满足某种约束条件。不能翻者输。

三个经典博弈

有三个经典的博弈论问题，分别是巴什博弈（Bash Game）、威佐夫博弈（Wythoff Game）和尼姆博弈（Nimm Game），从这三个问题入手，可以对博弈论有一个初步的了解。

准备长期更新，想总结下自己对算法竞赛中博弈论的一些认知，事实上，准确的说，应该称之为组合博弈论。

基础篇

1. 组合游戏 主要描述了组合游戏的定义。
2. 三个经典博弈 介绍了巴什博弈（Bash Game）、威佐夫博弈（Wythoff Game）和尼姆博弈（Nimm Game），并进行一些拓展，同时介绍了 \(\text{SG}\) 函数和 \(\text{SG}\) 定理。

进阶篇

1. 从 nim 和到 nim 积 从翻硬币的一维版本拓展到二维版本，并从 \(\text{nim}\) 和拓展到 \(\text{nim}\) 积。
2. Hackenbush 无向图删边游戏。

高级篇

占位符

题目

1. PE459 \(\text{tartan}\) 定理，\(\text{nim}\) 积

其他资料

占位符

三角剖分

对于二维平面上一个点集 \(V\) ，设其凸包为 \(CH(V)\) ，构造一个边集 \(E\) ，那么点集 \(V\) 的三角剖分 \(T(V)=G=(V,E)\)满足以下条件：

• 是一个平面图，即除了端点，所有边之间没有其他交点。
• 该平面图的任意一个面都是三角面。
• \(CH(V)\) 的边都在 \(E\) 中

##Delaunay 三角剖分

对于一个三角剖分 \(T\) ，若对于其中任意一个三角面，其外接圆内部不包含除三角面端点外 \(V\) 中其他点，则称之为 Delaunay 三角剖分，简称 \(DT\) 。下文中我们所说的三角剖分都指 Delaunay 三角剖分。

什么是组合游戏？

1. 有两个玩家。
2. 有一个状态集合，经常会是无限大的。
3. 每个玩家有从某状态转移到其他状态的规则，若两个玩家规则相同，称之为公平的，否则称之为非公平的。
4. 两个玩家轮流行动。
5. 当一个状态没有后续状态，玩家无法操作，游戏结束，通常规则下，最后一个行动的人获胜，特殊规则下，最后一个行动的人失败。这种状态称之为结束状态。
6. 一般的，游戏总能在有限次数的行动下结束。当游戏无法结束时，称之为平局，下文如不特殊声明，不考虑有这种情况。（这意味着，游戏状态的转移不存在环）

需要注意的是，组合游戏是信息完全的，即任何信息都是公开的，任何行动都是确定的。

在公平的组合游戏中，对于状态集合的每个状态，将其分为两种，一种是先手必胜状态，即首先行动的人必将获得胜利，另一种是后手必胜状态，或者先手必败状态，即首先行动的人必将失败。通过归纳递推，我们可以将所有状态分类：

1. 首先，结束状态必然是后手必胜状态，因为先手无法操作。
2. 能转移到任何一个后手必胜状态的状态都是先手必胜状态。
3. 只能转移到先手必胜状态的状态是后手必胜状态。

题目链接：Project Euler 459

这是 PE 上一个难度为 \(100\%\) 的题，但实际上只要你对博弈论有一定的了解，这道题并不是那么难。

\(N\times N\) 的黑白棋盘，初始全白，两人游戏，将棋盘变全黑的人胜利，每次操作可以将这样的一个子矩阵内棋子全部翻白：

1. 子矩阵右上角是白棋

2. 子矩阵长度是平方数 \((1,4,9,\dots)\)

3. 子矩阵宽度是三角形数 \((1,3,6,10,\dots)\)

对于 \(N=10^6\) 问先手第一步有多少种获胜的决策

这是个二维的棋盘游戏，实际上是两个一维游戏的组合，利用 \(\text{tartan}\) 定理，我们可以通过计算两个一维情况的 \(sg\) 值的 \(\text{nim}\) 积来快速得到二维情况的 \(sg\) 值。