无偏博弈----豆芽游戏 (Sprouts)

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

3graph.exe.zip (112.8 KB) 本附件包括：

• 3graph.exe

2014-8-31 12:29:45 上传

豆芽游戏 (Sprouts)

       Sprouts发源于英国，1967年二月的某个下午，剑桥大学的教授康威（John Horton Conway）与研究生派特森（Michael Stewart Paterson）共同创造了这个抽象略并且为无偏博弈的纸笔游戏。

玩法：

       首先，在纸上任意画n个点。然后两个人轮流在图中加上一条线（线的两端可以连接两个点，也可以连在同一点上），并在新增的线上任意加上一点。

你加的这条线可以九弯十八拐，但就是不能穿过自己，或其他之前画好的线与点。而且，每个点最多只能与三条线相接。当这个图再也无法加线的时候，游戏就结束了，画到最后一条线的人获胜。这是一般的玩法，也可以做相反规定：画到最后一条线的人落败。

       现在我们先来看看游戏开始时只有1点的情况：

先玩的人只有一种画法——画一条线由该点连至自己。

于是后玩的人，不论是在圈内加一条线将两点连起来，还是在圈外加线将两点连起来，都会让先玩的人无法再加线，所以后玩的人获得胜利。

事实上，对后玩的人来说，这两种画法其实是一样的，也就是说圈内和圈外是没有分别的。如果我们将第一个图形画在一颗球上，

此时你可以在球面上任意移动黑线与绿线，只要不跨过另一条线，都表示同一个图。于是，你可以将右边那条黑线绕过球的后方，移到左边那条黑线的左方。

然后将球转一下，从球的左边看来，正是第二个图。

       以下是一个豆芽游戏开始时为3个点的例子。这些图形是不是很像一个小嫩芽在不断长大呢？

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：Out Michael Stewart Conway 共同创造 豆芽 游戏

豆芽游戏在纸上呈现的图形，我们称之为平面图。下面我们先介绍一些与图(graph)有关的资讯。

1.    图(graph)

       一个图就是由一堆点(vertex)与一堆边(edge)所形成的。

2.    秩(degree)：

       如果两点之间以一条边相连，则这两点互为邻居。一个点的邻居数就称为这个点的秩。如下图中红点的秩为3，蓝点的秩为1。

3.    平面图(planargraph)：

       一个图如果可以画在平面上使得所有的边都互不跨越（端点除外），即为平面图。虽然下图中的红边横跨蓝边，但是利用图的同构性质，我们可以将红边拉出来，从外面走，便得到一个平面图：

   

       在图论中，我们称上面这两个图的关系为同构（isomorphism）。两个同构的图，它们点数相同，边数相同，点与边的关系也相同——如图中的红点，都以两条黑线与另一红点相连，并以一条绿线与绿点相连，而绿点则是分别以一条绿线与两个红点相连。

4.    一个图中秩的总和为边数的两倍：

       若点A与点B间有一条边，我们想像是A与B在握手。则秩的总和，就可以看成是每个人握手的次数总和；而边数代表的则是实际握手次数。当A和B握手的时候，B也和A握手，所以手只握了一次，却会被算两次（A, B各一次）。因此，每个人握手的次数总和会是实际握手数的两倍。如下图，边数为4，而2个黑点的秩为2，红点的秩为3，蓝点的秩为1，总和是8，正好是边数的2倍。

5.    连通图(connectedgraph)：

       由图中某一点开始延著边走至另一点，途中只要没有重複经过同一点，它所经过的边就称为一条路径（path）。如下图，红色的边就是两条由蓝点至蓝点的路径：

        

       而所谓的连通图，即是该图中的任两点间都可以找到一条路径。

6.    迴圈(circuit)：

       一条路径的起点与终点若为同一点，则称为一个迴圈。

7.    面（face）：

       一个平面图总是会将平面划分成几个区域，这些区域称为面，有几个区域就有几个面。如：

豆芽游戏 (Sprouts)

一定会结束吗？

       了解游戏规则后，也许有人会想：这个游戏一定会结束吗？会不会有一个可以一直加线的图呢？别耽心，康威告诉你这个游戏一定会在你加上第3n–1条线时，或在那之前结束：

       游戏规则告诉你，每个点都有三条“命”，也就是说，每个点都可以接出三条线。当一个点把它的三条命都用光，即接了三条线时，便“死”了，你再也不可以把其他线加到这个点上。因此，若游戏开始时纸上有n个点，则纸上存在3n条命。然后你每加上一条线，就用掉两条命（线有两端，各用一条命），但你又在线上画上一个新点，添了一条命。总体来看，就是每次都让这个游戏少一条命。

当游戏进行到最后剩下一条命时，就无法再加线，游戏也就结束了。因此这个游戏最多只能加上3n–1条线。

       如果游戏结束时的图为G0，则图裡所有点的秩，最小为2，最大为3。若是图中有一点的秩为1，则游戏仍可继续，因为可以在该点上画一个圈由自己连到自己，所以G0中所有点的秩至少都是2；而秩最大为3是因为每个点只有3条命。

我们可以再将G0变成图G——其中所有点的秩都是3：

       假设x是一个秩为2的点，y是x的邻居之一，于是我们拿走x，将原本与x相连的两条边接成一条，并将这条边及y点涂成红色，纪录x的位置。

连通的平面图有一个特性：图中的点数与面数之和恰等于边数加2。这就是所谓的尤拉公式：V + F = E + 2

其中V代表点的个数，F代表面的个数，而E是边数。

让我们看看几个例子：

有了这些资讯，我们便可以得到下面这个结论：

引理：

       假设游戏开始时有m个点，游戏玩了p次（加上3p条线）后结束，结束时的图为G0。若G (G0)为一连通图，则f = 2+ p–m，其中f是G0的面数。

       我们注意到，G中任一个面都一定只有一条红色的边，否则的话，表示在G0中，这个面裡有两个秩为2的点，如：

所以还可以加一条线连接这两点，与游戏已结束的假设矛盾。因此，红边的个数一定会小于或等于面的个数，若f为面的个数则fr。若G不为一连通图，我们可以将G分成若干连通部分(connectedcomponent)来讨论，情形类似。因此我们只讨论G为一连通图之情形。

       若G为一连通图，由引理我们知道f = 2 + p–m，且 r = 3m–p，于是

        

游戏是否可以在玩了2m–1次（p =2m – 1）之后就结束呢？假设p =2m–1，由引理知：

f = 2 + p – m

  = 2+ (2m – 1) – m

  = m+ 1

r = 3m – p

  =3m – (2m – 1)

  = m+ 1

得到 f = r，这表示每一个面都有一条红边，且不和其他面共用（否则f > r）。然而，因为G中每个点的秩皆为3，那麽G中至少存在一个迴圈 (Why?)。如果G中有迴圈，则看最小的迴圈，它会是一个封闭曲线，将平面分成圈内与圈外，如下图中包围黄面的迴圈：

所以这个迴圈上的边一定是两个面的交界，也就是说，迴圈内的面一定得和其他面共用红边，与f = r矛盾。

       因此，一个开始时有m点的游戏，至少要玩2m次才会结束，至多玩3m-1次就会结束。所以一个开始有3点的游戏，至少要玩6次才可能结束，且最多只能玩9次就会结束。