博弈-Green Hackenbush(删边游戏,《Game Theory》译文)

向右看齐 2021-09-15 21:50 577阅读 0赞

转自:[http://blog.sina.com.cn/s/blog\_8f06da990101252l.html][http_blog.sina.com.cn_s_blog_8f06da990101252l.html]

Green Hackenbush

Hackenbush游戏是通过移除一个有根图的某些边，直到没有与地板的相连的边。地板用虚线来表示，其中移除某一条边的时候，那条边以上所连着的所有边都会移除，就像砍树枝那样，树枝以上的部分也会被移除。

在这节中，我们讨论这个游戏的公平版本，每个玩家在他的回合可以删除任意的边。这个版本叫做Green Hackenbush，每条边都是绿色的，下面我们简称GH游戏。这里还有一个不公平版本，叫做Blue-Red Hackenbush，有些边是蓝色，有些边是红色，而玩家一只能删除蓝色边，玩家二只能删除红色边。总的来说，Hackenbush游戏，可能会有只供玩家一删除的蓝色边，只供玩家二删除的红色边，还有两个玩家都可以进行操作的绿色边。

1 Bamboo Stalks

作为GH游戏的介绍，我们先研究下面的Figure 6.1。n条线段的bamboo stalks游戏是具有n条边的线形图。一步合法的操作是移除任意一条边，玩家轮流进行操作，最后一个进行操作的玩家获胜。n条线段的bamboo stalks游戏能够移动到任意更小线段数(0到n-1)的bamboo stalks游戏局面当中。所以n条线段的bamboo stalks游戏是等同于nim游戏中其中拥有n个石子的一堆。玩一组bamboo stalks游戏就相当于玩nim游戏。

![1344074299_6393.jpg][]

‘

例如，左边的三根竹竿构成的“森林”相当于具有石子数分别为3、4、5三堆石子的nim游戏。就我们所知，3^4^5=2，这是一个能够移动到P局面的N局面，办法是通过取走三根线段的竹竿上的第二根线段，留下一根。而结果变成右边的竹竿分布，而此时的SG值是0，是P局面。

2 Green Hackenbush on Trees

通过bamboo stalks游戏，我们知道GH游戏是换了个形式的nim游戏而已。可是如果我们允许比bamboo stalks游戏更多结构呢？让我们看下在Figure 6.2中由三棵根树组成的森林。根树是一种图，带有一个最高的节点，叫做根，这个根到任意一个其他节点的路径都是独一无二的。实质上就是说这个图不含有圈。

![1344074310_4057.jpg][]

一次合法操作是移除任意一条不与地面相连的线段，此时次线段以上的子树都会被移除。既然这个游戏是公平的，而且根据我们学过的nim游戏，这样的树相当于nim游戏的一些堆，或者说是bamboo stalks游戏（到了这里明白bamboo stalks游戏与nim游戏的单堆是等价的）。这个问题就是寻找每棵树的SG值。

这里我们要用上一个原理，叫做**Colon Principle**：当树枝在一个顶点上时，用一个非树枝的杆的长度来替代，相当于他们的n异或之和。

让我们看看这条原理是如何在Figure 6.2中寻找与左树等价的竹竿。这里有两个节点拥有树枝。较高的那个节点拥有两个树枝，每个树枝上有两个节点。1^1=0，所以这两个树枝可以用一个带有0个节点树枝来代替，也就是说可以把这两个树枝给去掉。那就剩下了一个Y形树了，因为同样道理这个Y形树的两个树枝也要被去掉。此时就剩下了一个线段数为1的竹竿游戏模型了。

看Figure 6.3，是Figure 6.2中第二棵树的处理办法，最后可以得到线段数为8的竹竿游戏。第三棵树也可以同样处理，结果是线段数为4的竹竿游戏。（注意，这里所指的竹竿游戏都实质上是nim游戏中的单堆石子）

![1344074319_7883.jpg][]

现在我们可以计算一下图6.2三棵树的sg值，也就是1^8^4=13.既然这个SG值不为0，那么就是一个N局面，先手必胜。问题是要怎么找到胜利方法。很明显这里有一个必胜移动，通过将第二棵树进行操作使得它的SG值为5.可是我们要找哪条边呢？

Figure 6.3的最后一个树长度是8，因为它的前一棵树的三个树枝长度分别是3,2,6，异或值为3^2^6=7，用长度为7的竹竿代替三个树枝后，树的长度就是根加上竹竿长度，即1+7=8。为了最后SG达到5，即使树的长度为5，我们要用长度为4的竹竿来替代那三个树枝。因为2^6=4，所以我们只要将最左边的树枝去掉就行了，当然我们也可以将树枝改动成3^1^6=4.

修剪树的方法用冒号给出了，把所有的树化简为一个单一的竹竿。一个从最高的树枝开始，然后用原理归纳往下到根部。我们现在展示这个原理对于含圈和多重根边的图同样适用。

**        Colon Principle****的证明：**假设一个任意固定的图G，一个任意节点x，让H1和H2为任意的树，且拥有相同的SG值。考虑这样两个图G1=Gx:H1和G2=Gx:H2，Gx：Hi表示该图是把树Hi连接图的x节点。Colon Principle阐述的是两个图G1、G2拥有相同的SG值。看看Figure 6.4的两个游戏。

G1、G2拥有相同的SG值意味着两个游戏的总SG值为0，G1+G2的和是一个P局面，也就是必败

![1344074330_2393.jpg][]

先手一旦在其中一幅图中取走任意一条边，后手即可在另一幅图中取走相同的一条边。轮流下去，最后肯定是后手获胜。所以当树枝在一个顶点上时，用一个非树枝的杆的长度来替代，二者的结果是等价的。

**   3 Green Hackenbush on** **general rooted graphs**

现在让我们来考虑不规则的图。这些图可能会有圈，会有几条根。看Figure 6.5.

![1344074344_3374.jpg][]

同样，上面的三个图，每个图都相当于nim游戏的一个堆，三个图组成了一个nim游戏。接下来我们要找到这些图等价的nim堆，方便我们解决问题。这要用到融合原则。我们可以把两个相邻的节点合成一个节点，并把它们之间的边弯曲，变成一个圈。一个圈是把自己作为边的另一端的一种边。比如Figure 6.5的最右边那个杂戏表演者的头就是一个圈。在GH游戏中，一个圈是可以被一个叶子（一条没有任何树枝与它相连的边）所代替的，见Figure 6.6中第三幅图到第四幅图的转化。

**        The Fusion Principle**：任何环内的节点可以融合成一点而不会改变图的sg值。（下面我们称它为融合原则）

融合原则允许我们把任意一个根图简化为一个等效的可以通过冒号原则（即Colon Principle）简化为竹竿的树。

如下图左部分所示的一个门，在地板上的两个节点是同样的节点来的（记住地板相当于一个单独的节点），所以实际上是一个有一个节点与地板相连的三角形，即第二幅图。融合原则告诉我们，这相当于一个单独的节点有三个圈与它相连。所以造就了第三幅到第四幅的转变，过程是把任意两点收缩成一个圈，3个点两两收缩便可得到三个圈。每个圈又相当于长度为1的竹竿，它们的异或和还是长度为1的竹竿。

![1344074353_9113.jpg][]

我们会发现，拥有奇数条边的环可简化为一条边，偶数条边的环可简化为一个节点。例如，在Figure 6.5中的第二幅图圣诞树中的有四条边的环，会缩减成一个节点，所以这圣诞树最后会简化为一个长度为1的竹竿。相似的，房子上的烟囱变成一个单独的节点，右边的窗户变成一个点，继续下去，就可以看出房子的SG值为3。

融合原则的证明比冒号原则的证明更长，所以在此不做解释。

![1344074363_4081.jpg][]

附注：

本文译自《Game Theory》，由于这篇文章是译文，语言上可能有些不恰当，下面做些补注。

GH游戏：即 **Green Hackenbush****，**这篇文章探讨的博弈游戏。

竹竿游戏：即**Bamboo Stalks****，**是直译过来的。

冒号原则：即**Colon Principle****，**这个虽然是直译，可是不太好，有保留。

融合原则：即**Fusion Principle**

[http_blog.sina.com.cn_s_blog_8f06da990101252l.html]: http://blog.sina.com.cn/s/blog_8f06da990101252l.html
[1344074299_6393.jpg]: https://img-my.csdn.net/uploads/201208/04/1344074299_6393.jpg
[1344074310_4057.jpg]: https://img-my.csdn.net/uploads/201208/04/1344074310_4057.jpg
[1344074319_7883.jpg]: https://img-my.csdn.net/uploads/201208/04/1344074319_7883.jpg
[1344074330_2393.jpg]: https://img-my.csdn.net/uploads/201208/04/1344074330_2393.jpg
[1344074344_3374.jpg]: https://img-my.csdn.net/uploads/201208/04/1344074344_3374.jpg
[1344074353_9113.jpg]: https://img-my.csdn.net/uploads/201208/04/1344074353_9113.jpg
[1344074363_4081.jpg]: https://img-my.csdn.net/uploads/201208/04/1344074363_4081.jpg