数学研发论坛

标题: 四连通与八连通的较量 [打印本页]

---

作者: KeyTo9_Fans    时间: 2009-10-8 21:44
标题: 四连通与八连通的较量
我设计了一个游戏。
两人在n*n的正方形棋盘中下子。
每一步轮到谁下是随机决定的。
轮到某一方下子的概率为p，另一方为(1-p)。
双方的胜利条件都是将棋盘的对边用自己的棋子连起来。
其中一方连接上下两条边，棋子是四连通的。
另一方连接左右两条边，棋子是八连通的。

[jh]有趣的问题，解决却需要足够的功底，系统的分析。[/jh]如果觉得以上规则描述得不够清楚，可以在这里阅读具体细节：
http://tieba.baidu.com/f?kz=643280306

为了公平，我们希望当双方均以最佳策略下子时，胜率各为50%。
所以我们应该为执四连通棋子的一方赋予更大的下子概率p，即p≥0.5。
对于不同规模的n，p的值是不同的。
例如：
当n=1时，p取0.5。
当n=2时，p取sqrt(1-sqrt(0.5))。

但对于更大的n，如何求对应的p值？
另外，当n→∞时，p的极限是多少？

---

作者: mathe    时间: 2009-10-8 21:52
欢迎KeyTo9のFans的到来.
对于较大的n,计算p应该很难.但是我估计极限为1

---

作者: mathe    时间: 2009-10-8 21:57
上面考虑的不对.如果p大于7/8,那么四连通方基本可以考虑将八连通方的所有棋子给围起来了.所以极限应该小于7/8.

---

作者: KeyTo9_Fans    时间: 2009-10-8 22:52
试贴一张n=3的博弈树、方程和求解结果的图片，以便核对数据。



图片来自百度空间的相册。

如果不允许将图片贴在百度以外的论坛，则尝试用此链接查看：

---

作者: gxqcn    时间: 2009-10-9 07:54
也非常欢迎KeyTo9のFans的到来。

可以将图片做为附件直接上传到论坛的，
然后将它插入到适当的位置即可（形成图文混排效果）。

---

作者: 〇〇    时间: 2009-10-9 09:04

也非常欢迎KeyTo9のFans的到来。

可以将图片做为附件直接上传到论坛的，
然后将它插入到适当的位置即可（形成图文混排效果）。
gxqcn 发表于 2009-10-9 07:54

好大的图

---

作者: mathe    时间: 2009-10-9 16:52
也许极限是$2/3$

---

作者: KeyTo9_Fans    时间: 2009-10-10 22:34
关于此游戏，我编了一个人机对战的平台，欢迎试玩。

(, 下载次数: 7)

上传

点击文件名下载附件

在e2.txt里可以设置参数。

#####

其中第一个参数表示你选哪一方。（1:四连通的绿方 2:八连通的红方）

第二个参数表示正方形棋盘的规模。（15表示棋盘有15行15列）

最好不要超过25*25，因为棋盘太大电脑会跑得很辛苦。

第三个参数表示格子的大小。（40表示一个格子的大小为40像素*40像素）

第四个参数表示红色棋子出现的概率是32768分之几。（默认值13400表示红色棋子出现的概率是13400/32768）

关于游戏界面：

右方的方块表示轮到谁下。

下面的红绿条表示红绿棋子出现的比例。（游戏过程中不会改变）

右上角还有计分条。（计分条很细，不仔细看是看不清的）

这个游戏的输赢有很大的运气成分，所以要玩十几局乃至几十局才知道双方的大致实力。

---

作者: shshsh_0510    时间: 2009-10-10 23:47
扒头看看有啥有趣的题目，就看到这个
这个精确值很难地说，我想了个求近似的法子，不知差多远
首先，8的一方太优势了，所以策略上应该几乎不用顾虑自己的连通性，既然一定有一方会赢，那么阻断对方就是胜利；4的一方堵对方困难较大，老老实实向目标前进可能就是比较好的策略
考虑n较大时，各方可能会先散布一些中间点（有些像围棋那样），然后再将中间点连起来。
基于上面假设的策略，计算p:
设4的一方的两个联络点是一条直线上距离n的两点，计算两个点连上的概率
分别计算8方的1次干扰、2次干扰 ... k次干扰
对k次干扰还要区分干扰的连续情况（这需要考虑k的分划数），每r次连续干扰，将导致4方要多费2r步才能绕过。
总之，基于这样的假设求极限也是比较困难的，不过感觉可算了

---

作者: KeyTo9_Fans    时间: 2010-7-20 21:46
我感觉我已经在论坛里呆了快两年了。

可是翻出自己首次在本轮坛发的这篇贴子一看，日期是09年底，说明自己其实呆了一年也不到。

都怪郭兄把我晋升得太快，从“新生入学”->“小试牛刀”直接晋升到“版主”->“超级版主”，

让我高估了自己的资历。

按照正常的步伐，Fans现在应该只是个“实习记者”而已。

对于此问题，Fans的研究已经接近尾声。

从现在起，Fans将陆续把此题的详细解答过程整理好并发上来。

内容挺多的，所以每天有空的时候写一点，又有空的时候再写一点。

直到把所有的解答步骤都写清楚为止。

希望最后用不着Fans亲自来写了。

因为写到一半的时候，论坛里的大牛们可能会等不及了。

于是“啪”的一声把后面的结果全部贴上来，瞬间秒杀此题

---

作者: KeyTo9_Fans    时间: 2010-7-21 14:00
首先应该要证明以下两个命题：

（假设某方胜利后不结束游戏，直到整个棋盘都下满棋子为止）

命题一：当整个棋盘下满棋子时，最多只有一方获胜。

命题一的等价表述：双方不能同时获胜。

命题二：当整个棋盘下满棋子时，必有一方获胜。

命题二的等价表述：至少有一方获胜。

例如：下图所示（规模$n=2$）的局面中

(, 下载次数: 24)

上传

点击文件名下载附件

八连通的红方获胜，四连通的绿方没有获胜，同时满足了以上两个命题。

我们要证明对于所有的$n$以及所有可能的下满棋子的局面，都要满足上述两个命题。

下面讨论第一个命题：双方不能同时获胜。

反证法。

假设双方同时获胜，那么他们的连通路径必定相交。

于是与 一个格子只能属于其中一方 矛盾。

所以假设 双方同时获胜 不成立。

所以双方不能同时获胜。

关于 为什么他们的连通路径必定相交 这个问题，

我们发了一张新的贴子（已经用数学语言严格地定义了四连通和八连通）：

http://bbs.emath.ac.cn/viewthread.php?tid=2273

这里就不讨论了。

稍后讨论第二个命题。

---

作者: wayne    时间: 2010-7-24 15:29
发现KeyTo9_Fans超版很擅长 玩那些 概率迭代型的复杂游戏，
不知 “生命游戏”，“元胞自动机” 是否合你口味？

---

作者: KeyTo9_Fans    时间: 2010-7-31 22:03
挺适合的，我很喜欢玩。

不过只能看，没办法变成有意思的题目来做。

下面讨论第二个命题：至少有一方获胜。

证明方法：假设四连通没有获胜，利用网络流的基本性质证明八连通获胜。

这个方法曾经在此贴里用过：http://bbs.emath.ac.cn/thread-2018-2-3.html

是用来找绕障碍的环路的：

(, 下载次数: 22)

上传

点击文件名下载附件

下面通过网络流的基本性质说明这种构造的正确性。

首先构造一个流量为$1$的合法的网络流：

(, 下载次数: 14)

上传

点击文件名下载附件

然后把每个四连通方块看成环形流：



叠加到原来流量为$1$的网络流上：

(, 下载次数: 13)

上传

点击文件名下载附件

根据网络流的基本性质，合法的网络流加上环形流，其结果仍然是合法的网络流，且流量不变，仍然为$1$。

(, 下载次数: 15)

上传

点击文件名下载附件

好了，现在我们根据网络流的合法性，得到了一条从左下角出发到达右下角的路径。

路径两边肯定是异色的格子。（因为同色格子中间不可能有流量）

好了，现在沿路径左手边的八连通格子走，分$3$种情况讨论：

路径直行：对应的八连通格子也是直行；

路径左拐$90$度：对应同一个八连通格子，原地停留；

路径右拐$90$度：对应的八连通格子往斜向走一步。

按照上述规则，就可以从左下角出发，以八连通的方式到达右下角。

(, 下载次数: 16)

上传

点击文件名下载附件

说明八连通方获胜。

（上述过程相当于把右手贴墙法则证了一遍）

把命题一和命题二综合起来，得到这样一个结论：

任何一个下满棋子的局面，有且只有一方获胜，没有双赢或双败的局面。

稍后讨论博弈图。

---

作者: KeyTo9_Fans    时间: 2010-10-5 15:18
首先我们抛开随机因素不提，讨论完整的博弈图。

完整的博弈图是一个有向图$G(N)$，其中$N$表示棋盘规模。

图$G(N)$的顶点是局面，边是走法。

局面就是格子集合$\{(x,y)|1<=x<=N,1<=y<=N\}$到颜色集合$\{white,green,red\}$的映射。

走法就是从一个局面通过一步合法的落子到达另一个局面的通道。

图$G(1)$有$3$个顶点，$2$条边，如下图所示。

(, 下载次数: 24)

上传

点击文件名下载附件

图$G(2)$有$81$个顶点，$216$条边，如下图所示（镜面对称的局面圈在了一起）。

(, 下载次数: 14)

上传

点击文件名下载附件

图$G(3)$、$G(4)$、……都太大了，这里就不画了。

稍后讨论完整博弈图的性质。

---

作者: KeyTo9_Fans    时间: 2010-10-7 13:21
性质$1$：图$G(N)$有$3^{N*N}$个顶点。

证明：

因为图$G(N)$的顶点是局面，

局面是格子集合$\{(x,y)|1<=x<=N,1<=y<=N\}$到颜色集合 {白、绿、红} 的映射，

其中格子集合$\{(x,y)|1<=x<=N,1<=y<=N\}$有$N*N$个元素，

颜色集合 {白、绿、红} 有$3$个元素。

所以格子集合的每$1$个元素都有$3$种不同的成像。

所以格子集合到颜色集合一共有$3^{N*N}$种映射。

所以一共有$3^{N*N}$种局面。

所以图$G(N)$有$3^{N*N}$个顶点。

证毕。

稍后讨论性质$2$。

---

作者: winxos    时间: 2010-10-7 19:59
14# KeyTo9_Fans

一直诧异 Key 版主 这么漂亮的图是用什么画的？

---

作者: KeyTo9_Fans    时间: 2010-10-8 12:07
用windows自带的画图工具画的。

虽然这个工具很简陋，但是我使用得很仔细，每一根线条都瞄得很精准。

所以才得到这些漂亮的图的。

性质$2$：若局面$S$有$k$个空白格，则局面$S$对应的顶点$V$有$2k$条出边。

证明：

因为局面$S$有$k$个空白格。

根据游戏规则，任意一方都可以在局面$S$上行动，选择一个空白格，填上自己的颜色。

四连通的绿方有$k$种选择方案，对应$k$种不同的走法；

八连通的红方也有$k$种选择方案，对应$k$种不同的走法。

所以局面$S$一共有$2k$种走法。

因为每种走法对应一条出边，

所以局面$S$对应的顶点$V$有$2k$条出边。

证毕。

稍后讨论性质$3$。

---

作者: KeyTo9_Fans    时间: 2010-10-8 12:28
性质$3$：图$G(N)$一共有$2/3*N^2*3^{N^2}$条边。

证明：

根据性质$2$，我们很容易得知：边的数量是空白格数量的$2$倍。

于是我们计算图$G(N)$中$3^{N*N}$个顶点对应的$3^{N*N}$个局面的空白格数量之和。

因为每个局面有$N*N$个格子，

所以$3^{N*N}$个局面一共有$N*N*3^{N*N}$个格子。

因为空白格数量占总格子数量的$1/3$，

所以$N*N*3^{N*N}$个格子中，有$1/3*N*N*3^{N*N}$个空白格。

因为边的数量是空白格数量的$2$倍，

所以图$G(N)$一共有$2/3*N*N*3^{N*N}$条边，即$2/3*N^2*3^{N^2}$条边。

证毕。

稍后在图$G(N)$上讨论楼主设计的游戏。

---

作者: KeyTo9_Fans    时间: 2010-10-11 10:07
好了，现在我们开始考虑随机因素。

根据游戏规则，每下一步之前我们都抛一枚硬币。

这枚硬币有$p$的概率抛到正面，有$q$的概率抛到反面。

其中$q=1-p$。

如果抛到正面，则下一步由四连通绿方落子，

如果抛到反面，则下一步由八连通红方落子。

定义$3$：

—————————————————————
对于图$G(N)$中的每个顶点$V$对应的局面$S$，

定义函数$f(p,S)$。

其中$p$是四连通绿方的落子概率。

当$S$不是终局的时候，$f(p,S)$的表达式如下：

$f(p,S)=p*max\{f(p,P_1),f(p,P_2),...,f(p,P_k)\}+q*min\{f(p,Q_1),f(p,Q_2),...,f(p,Q_k)\}$

其中：

$q=1-p$。

$k$是局面$S$的空白格数量。

$P_1,P_2,...,P_k$是局面$S$经过四连通绿方的一步落子到达的局面。

$Q_1,Q_2,...,Q_k$是局面$S$经过八连通红方的一步落子到达的局面。

当$S$是终局的时候：

如果四连通绿方获胜，则$f(p,S)=1$，

如果八连通红方获胜，则$f(p,S)=0$。
—————————————————————

由于定义$3$过于抽象，下面举$3$个具体的例子形象地说明定义$3$。

例$1$：$S=$(红红绿,绿绿绿,绿红红)。

由于$S$是终局且四连通绿方获胜，所以：

(, 下载次数: 20)

上传

点击文件名下载附件

例$2$：$S=$(红红绿,红绿绿,绿红红)。

由于$S$是终局且八连通红方获胜，所以：

(, 下载次数: 15)

上传

点击文件名下载附件

例$3$：$p=0.6$，$S=$(绿白,白白)。

由于$S$不是终局，有$3$个空白格，所以$k=3$。

因为$P_1,P_2,...,P_k$是局面$S$经过四连通绿方的一步落子到达的局面，所以：

$P_1=$(绿绿,白白)，

$P_2=$(绿白,绿白)，

$P_3=$(绿白,白绿)。

因为$Q_1,Q_2,...,Q_k$是局面$S$经过八连通红方的一步落子到达的局面，所以：

$Q_1=$(绿红,白白)，

$Q_2=$(绿白,红白)，

$Q_3=$(绿白,白红)。

因为

$f(p,S)=p*max\{f(p,P_1),f(p,P_2),...,f(p,P_k)\}+q*min\{f(p,Q_1),f(p,Q_2),...,f(p,Q_k)\}$

所以当$p=0.6$，$S=$(绿白,白白)时，

(, 下载次数: 20)

上传

点击文件名下载附件

稍后讨论函数$f(p,S)$的作用。

---

作者: KeyTo9_Fans    时间: 2010-10-11 11:26


之前我们做了很多抽象的准备工作：证明了该游戏是胜负分明的，即不能双赢也不能和棋；讨论了完整的博弈图及其性质；定义了一个很抽象的函数$f(p,S)$。

从这里开始，我们要解决具体的问题了。

定理$1$：

————————————
如果双方都是绝顶聪明的，

那么从局面$S$开始对弈，

四连通绿方的胜利概率就是函数$f(p,S)$的值。
————————————

由于局面$S$有$3^{N*N}$种，我们不可能一个一个地进行讨论。

我们把局面$S$按照空白格的数量$k$进行分类，然后用数学归纳法证明定理$1$。

证明：

一、基础步骤：证明定理$1$对于$k=0$成立。

此时$S$是空白格数量为$0$的终局$F$。

如果四连通绿方把上下两边连起来了，那么四连通绿方的获胜概率是1。

此时根据定义$3$，我们有$f(p,S)=1$，与四连通绿方的胜利概率相等。

如果八连通红方把左右两边连起来了，那么四连通绿方的获胜概率是0。

此时根据定义$3$，我们有$f(p,S)=0$，也与四连通绿方的胜利概率相等。

综上所述：

当$k=0$时，四连通绿方的胜利概率就是函数$f(p,S)$的值。

即定理$1$对于$k=0$成立。

二、归纳步骤：假设定理$1$对于$k=m$成立，证明定理$1$对于$k=m+1$也成立。

对于具有$(m+1)$个空格子的局面$S$，

四连通绿方有$p$的落子概率，

八连通红方有$q$的落子概率。

如果下一步是四连通绿方落子，

他有$(m+1)$种下法，

使得局面$S$变成$P_1,P_2,...,P_{m+1}$的其中一种。

这些局面均只剩$m$个空格子。

因为定理$1$对于$k=m$成立，

所以从局面$P_1,P_2,...,P_{m+1}$开始对弈，四连通绿方的胜利概率分别是

$f(p,P_1),f(p,P_2),...,f(p,P_{m+1})$

由于四连通绿方绝顶聪明，所以他会从中找出一个最大值，使得自己的胜利概率为

$max{f(p,P_1),f(p,P_2),...,f(p,P_{m+1})}$

如果下一步是八连通红方落子，

他也有$(m+1)$种下法，

使得局面$S$变成$Q_1,Q_2,...,Q_{m+1}$的其中一种。

这些局面均只剩$m$个空格子。

因为定理$1$对于$k=m$成立，

所以从局面$Q_1,Q_2,...,Q_{m+1}$开始对弈，四连通绿方的胜利概率分别是

$f(p,Q_1),f(p,Q_2),...,f(p,Q_{m+1})$

由于八连通红方也绝顶聪明，所以他会从中找出一个最小值，使得对方的胜利概率为

$min{f(p,Q_1),f(p,Q_2),...,f(p,Q_{m+1})}$

综上所述，对于具有$(m+1)$个空格子的局面$S$，

$f(p,S)=p*max{f(p,P_1),f(p,P_2),...,f(p,P_{m+1})}+q*min{f(p,Q_1),f(p,Q_2),...,f(p,Q_{m+1})}$

所以定理$1$对于$k=m+1$成立。

根据数学归纳法，定理$1$对于所有的$k$都成立。

证毕。

根据定理$1$，楼主的问题等价于：

————————————
求$p$，使得$f(p,E)=0.5$。
————————————

稍后从定义$3$出发解决楼主的问题。

---

作者: KeyTo9_Fans    时间: 2010-10-12 14:21


之前我们提到了楼主的问题等价于

————————————
求$p$，使得$f(p,E)=0.5$。
————————————

这是因为我们定义的$f(p,S)$的含义是

—————————————
四连通绿方的落子概率为$p$，

双方从局面$S$开始对弈，

均采用最佳策略的时候，

四连通绿方的胜利概率。
—————————————

这个含义是通过定理$1$得到的。

当$S$是空棋盘$E$的时候，如何求$f(p,E)$的值呢？

为了能清楚地回答这个问题，我们先做两道简单的习题。

习题$1$：

$S=$(红红绿,白绿绿,绿红红)，求$f(p,S)$。

解：

(, 下载次数: 21)

上传

点击文件名下载附件

习题$2$：

$S=$(红红绿,白绿绿,红绿红)，求$f(p,S)$。

解：

(, 下载次数: 18)

上传

点击文件名下载附件

以上两道习题都很简单。

因为局面$S$只有$1$个空格子，

所以我们把这个空格子分两种情况讨论：

$1$.这个空格子被四连通绿方占据，概率为$p$；

$2$.这个空格子被八连通红方占据，概率为$q$。

然后把这两种情况综合起来就得到了结果。

如果局面$S$有$2$个空格子，就没有这么简单了。

因为双方都面临$2$个选择。

对于四连通绿方来说，他要比较$f(p,P_1)$和$f(p,P_2)$哪个大。

如果$f(p,P_1)$大，那么他就把$S$变成$P_1$；

如果$f(p,P_2)$大，那么他就把$S$变成$P_2$。

而$f(p,P_1)$和$f(p,P_2)$都是只有$1$个空格子的简单问题，所以可直接求得答案。

对于八连通红方来说，他要比较$f(p,Q_1)$和$f(p,Q_2)$哪个小。

如果$f(p,Q_1)$小，那么他就把$S$变成$Q_1$；

如果$f(p,Q_2)$小，那么他就把$S$变成$Q_2$。

而$f(p,Q_1)$和$f(p,Q_2)$也都是只有$1$个空格子的简单问题，所以也直接求得答案。

通过上述分析，我们就可以清楚地认识到：

对于没有空格子的终局$F$，$f(p,F)$是已知量。

对于有$1$个空格子的局面$S$，可根据相应的$f(p,F)$求得$f(p,S)$。

解决了$1$个空格子的局面$S$的问题，就可以求$2$个空格子局面的$f(p,S)$。

……

解决了$m$个空格子的局面$S$的问题，就可以求$(m+1)$个空格子局面的$f(p,S)$。

下图形象地表示了这一过程。

(, 下载次数: 16)

上传

点击文件名下载附件

好了，现在我们已经知道了：

$E$是空格子数最多的局面，有$N^2$个空格子。

（我们用$k$来表示局面$S$的空格子数）

要求$f(p,E)$，就要从$k=0$开始，求$k=1$的$f(p,S)$，$k=2$的，$k=3$的，……，$k=N^2-1$的。

最后才能根据$k=N^2-1$的$f(p,S)$求得$f(p,E)$的值。

我们重新翻出图$G(2)$来具体观察这一过程。



图$G(2)$分了$5$层，其中最底层是$16$个终局$F$：

(, 下载次数: 17)

上传

点击文件名下载附件

这一层的$f(p,S)$值不是$0$，就是$1$。

倒数$2$层是$k=1$的局面。

(, 下载次数: 16)

上传

点击文件名下载附件

这一层的$f(p,S)$值由最底层的$f(p,S)$决定。

中间层是$k=2$的局面。

(, 下载次数: 16)

上传

点击文件名下载附件

这一层的$f(p,S)$值由倒数$2$层的$f(p,S)$决定。

第$2$层是$k=3$的局面。

(, 下载次数: 17)

上传

点击文件名下载附件

这一层的$f(p,S)$值由第$3$层的$f(p,S)$决定。

最高层是空局面$E$。

(, 下载次数: 15)

上传

点击文件名下载附件

只有当底下所有的$f(p,S)$求出来，才能求得$f(p,E)$。

通过上述分析，我们可以知道：

求$f(p,E)$就相当于在图$G$上遍历一遍，走遍所有的顶点和所有的边。

而图$G(N)$的顶点数为$3^{N*N}$，边数为$2/3*N^2*3^{N^2}$。

所以求$f(p,E)$的时间复杂度是$O(N^2*3^{N^2})$。

这个数列增长得很快。

前$5$项是：

$3$
$324$
$177147$
$688747536$
$21182215236075$

对于第$5$项，计算机已经无能为力了。

因为是实数运算，所以计算机每秒大约处理$10^8$次运算。

$21182215236075$次运算需要$211822$秒，约等于$3$天。

而令$f(p,E)=0.5$是一个二分（或者是迭代）的过程。

我们要对$p$进行猜测，然后看$f(p,E)$的值与$0.5$的差距，根据差距决定下一个$p$值。

而每算一次$f(p,E)$就要$3$天，这是不能接受的。

所以我们只能提供$N=1$到$N=4$的答案：

$N=1$: $p=0.50000000000000$
$N=2$: $p=0.54119610014620$
$N=3$: $p=0.55929631600132$
$N=4$: $p=0.56972413396803$

稍后讨论最佳策略下的博弈图（简称博弈图）。

---

作者: KeyTo9_Fans    时间: 2010-10-12 20:07


定义$4$：

—————————————————
对于给定的$p$，定义有向图$GB(p,N)$。

其顶点$S$是双方均采取最佳策略时对弈可达的局面。

对于每个顶点$S$（终局除外），都只有两条出边：

$S->P$，$S->Q$。

其中：

$S->P$是四连通绿方从局面$S$开始的最佳走法；

$S->Q$是八连通红方从局面$S$开始的最佳走法。

如果有多种最佳走法，则规定：

先从上到下，然后从左到右数，

数到第一个最佳的格子作为最佳的走法。
—————————————————

例如：

当$S=$(白白,白白)时，(绿白,白白)、(白绿,白白)、(白白,绿白)、(白白,白绿)都是四连通绿方的最佳走法。

根据先从上到下，然后从左到右数的规则，选取第一种走法(绿白,白白)为最佳走法。

下图是$GB(p,1)$。

(, 下载次数: 21)

上传

点击文件名下载附件

下图是$GB(p,2)$（无论$p$取何值，双方的最佳走法不变）。

(, 下载次数: 17)

上传

点击文件名下载附件

本贴的第一张图就是$GB(p,3)$（无论$p$取何值，双方的最佳走法不变）。



从上面的几幅图可以看出，$f(p,E)$是关于$p$的多项式函数。

$f(p,E)=0.5$是一个一元$N^2$次方程。

当$N>2$时，方程的次数大于$4$，没有公式解。

所以仍然需要用二分法（或迭代法）来求$p$。

要得到$f(p,E)$的多项式，我们需要预先知道最佳策略。

要知道最佳策略，就必须把$f(p,E)$底下的所有$f(p,S)$求出来。

时间复杂度仍然是$O(N^2*3^{N^2})$。

唯一的好处是我们可以很方便地得到更精确的结果：

$1$: $0.50000000000000000000000000000000$
$2$: $0.54119610014619698439972320536639$
$3$: $0.55929631600132353475576392078938$
$4$: $0.56972413396802715322804051835303$

楼主的问题解答到此告一段落。

稍后我将提出新的问题。

---

作者: 没——问题    时间: 2010-10-12 20:49
终于连载完了，一直没好意思插楼，题解的连载比小说连载更吊胃口。。。
话说或许可以考虑下多项式的通项，而且目前对n->inf的情况也还没有讨论

---

作者: KeyTo9_Fans    时间: 2010-10-12 22:03
我一直都在很努力地画图。

因为没有图实在是太抽象，一点都不好解释。

花了很多时间，不好意思让你久等了。

你说得很正确。

我提出新问题的目的就是希望大家能参与进来一起讨论，

从而得到多项式的通项，最终得到n->inf的结果。

我在考虑新问题是直接在这里提还是开新贴。

我会尽快作决定的。

---

作者: KeyTo9_Fans    时间: 2010-10-13 13:41
新问题已经提出。点击此连接查看：

http://bbs.emath.ac.cn/thread-2710-1-1.html

欢迎讨论。

期限大概$1$个月。

如果没有收到满意的回复，Fans将再次出马，亲自上阵，继续连载，破解该题。

---

作者: zgg___    时间: 2010-10-14 10:46
LZ的这个问题连载中或许存在某个小缺陷，呵呵。
LZ说f(p,E)是关于p的多项式函数，或许还暗示了决策与p是无关的。

然而，在一些情况下，下一步的决策是与p相关的。
举一个例子来说，见下图的S，（我不知道是如何走到这种局面的。）
假设此时，四连通的绿方幸运的轮到了，那么他是选择1的位置还是选择2的位置呢？
设他选择1和2之后，获胜的几率分别是P1和P2，P1和P2的曲线如图，它们相交于0.618。因此，对于图中的S，f(p,S)是分段的多项式函数。在某些情况下，决策是和p相关的。这种可能性使得题目的复杂度有所增加。
(, 下载次数: 19)

上传

点击文件名下载附件

或许游戏可以设计成这样：
1、每次投币，p=0.5；
2、棋盘变成长方形，让四连通的绿方的边比较长，从而补偿连通上的劣势。
问：棋盘的长宽是多少比较公平？

最后，支持7层的观点一下。（呵呵，只是感觉上的，联想起了围棋中扳粘和小尖的关系。）

---

作者: KeyTo9_Fans    时间: 2010-10-14 13:57


值得一提的是，连载中只有$1$个定理：$f(p,S)$是胜利概率。

除此之外，任何缺少严谨证明的论断，我都没有把它当成定理。（包括“必有一方获胜”和“不能同时获胜”）。

为了推翻“决策与$p$无关”的论断，我费尽心思去找反例。

结果找了很久，只找到$N=5$的一个反例。

由于过久没有关注这个问题，导致这个反例已经遗忘了。

根据即兴的回忆，这个反例大概是：

$S=$(白白白白白,绿绿绿白白,白白白白白,白白白白白,白白白红白)。

我在这里要赞一下楼上这位仁兄。

因为楼上找的这个反例比我找到的这个反例更有代表性。

其优点在于：

$1$. 简单。是$N=4$的反例。
$2$. 优美。以$0.618$作为分界点。

#####

另外，楼上提的新问题可以作为该问题的后续工作。

如果有必要，可以发起一个新话题。

我在这里还要出续集。

等续集完了之后会考虑楼上的新问题的。

---

作者: KeyTo9_Fans    时间: 2010-10-15 00:24


下集预告：

Fans的续集指的是什么呢？

他为什么扔下n->inf不管，就提出新问题了呢？

原来这个世界上不存在绝顶聪明的人。

即使存在，他们也太辛苦了。

他们的脑子要转$N^2*3^{N^2}$圈才能下一步棋，实在是太辛苦他们了。

如果能证明一个定理：

————————————————————————
两个问题的答案是相同的。

即对于所有的$N$，两个问题具有相同的公平概率$p$。
————————————————————————

我们就可以认为：

————————————————————————
两个绝顶聪明的人（比如emath和mathe）玩这个游戏，

等价于两个大笨蛋（比如Fans和东方角落）玩这个游戏。
————————————————————————

于是我们就不再需要当绝顶聪明的人了。

我们就可以轻轻松松地，以两个大笨蛋的角色去尽情享受这个游戏。

难怪Fans要提出新问题，让KeyTo9_Fans和KeyTo9都变成大笨蛋。

然而，zgg___仁兄指出：决策是与$p$值相关的。

这是否意味着绝顶聪明的人玩出来的多项式需要分段，大笨蛋玩出来的多项式不需要分段呢？

如果是的话，这无疑是上述定理的一个路障。

面对这个路障，Fans又是如何应对的呢？

他能顺利跨过这道坎吗？

敬请收看下集：《跨越路障》

---

作者: KeyTo9_Fans    时间: 2010-10-16 17:55
题解连续剧《跨越路障》现在开始！

定义$5$：

———————————————————
对于任意的局面$S$，定义函数$g(p,S)$。

$g(p,S)$的含义如下：

$p$是硬币抛到正面朝上的概率，

$k$是局面$S$的空白格数量，

我们连抛$k$次硬币，

然后根据抛硬币的结果依次给$k$个空白格涂上颜色：抛到正面涂绿色，抛到反面涂红色。

我们把涂完颜色后四连通绿方的胜利概率记为$g(p,S)$。
———————————————————

为了加深理解，我们来做一道习题。

习题$3$：$p=0.5$，$S=$(绿白,白白)，求$g(p,S)$的值。

答案将在下一次公布。

下一次讨论$g(p,S)$的显式表达式。

---

作者: KeyTo9_Fans    时间: 2010-10-17 20:13
下面公布习题$3$的答案。

————————————————————————
解：

因为$S=$(绿白,白白)，有$3$个空白格，

所以$k=3$，我们要连抛$3$次硬币。

连抛$3$次硬币有$2^3=8$种结果，对应$8$种涂色方案。

它们是：

(, 下载次数: 30)

上传

点击文件名下载附件

因为$p=0.5$，所以每种涂色方案的概率均为$1/8$。

因为这$8$种涂色方案中，有$5$种涂色方案为四连通绿方胜利，

所以$g(p,S)=5/8$。
————————————————————————

定理$2$：

———————————————————
$g(p,S)=\sum_{i=0}^k c_i*p^i*q^{k-i}$

其中：

$q=1-p$，

$k$是局面$S$的空白格数量，

$c_i$是$i$个空白格涂绿色，$(k-i)$个空白格涂红色时，使得四连通绿方胜利的涂色方案数。
———————————————————

证明：

因为硬币抛到正面朝上的概率是$p$，反面朝上的概率是$q$，

所以出现包含$i$次正面朝上，$(k-i)$次反面朝上的特定的硬币序列的概率是$p^i*q^{k-i}$。

因为抛出两个不同的特定的硬币序列是两个不相容的事件，

所以根据$g(p,S)$的定义，

我们把使得四连通绿方胜利的特定的硬币序列的概率相加，

得到$g(p,S)=\sum_{i=0}^k c_i*p^i*q^{k-i}$。

证毕。

下一次讨论$g(p,S)$的递推式。

---

作者: KeyTo9_Fans    时间: 2010-10-19 17:03
定理$3$：

——————————————————————————————
对于所有的$i(1<=i<=k)$，均成立$g(p,S)=p*g(p,P_i)+q*g(p,Q_i)$。

其中：

$k$是局面$S$的空白格数量，

$P_i$是局面$S$的第$i$个空白格染成绿色的局面，

$Q_i$是局面$S$的第$i$个空白格染成红色的局面。
——————————————————————————————

证明：

因为我们要连抛$k$次硬币，

第$1$次决定局面$S$的第$1$个空白格的颜色，

第$2$次决定局面$S$的第$2$个空白格的颜色，

……

第$k$次决定局面$S$的第$k$个空白格的颜色。

由于决定的顺序不影响最终的结果，

我们不妨先决定局面$S$的第$i$个空白格的颜色，

然后再决定剩余的$(k-1)$个空白格的颜色。

于是我们对第$i$个空白格的颜色分情况讨论。

这个空白格有$p$的概率染成绿色，变成局面$P_i$，有$q$的概率染成红色，变成局面$Q_i$，

所以$g(p,S)=p*g(p,P_i)+q*g(p,Q_i)$。

证毕。

下一次我们将会了解到为什么两个绝顶聪明的人下这盘棋，等价于两个大笨蛋下这盘棋。

---

作者: KeyTo9_Fans    时间: 2010-10-20 19:48


定理$4$：

————————————————————
对于所有$p$和$S$，均成立$f(p,S)=g(p,S)$。
————————————————————

我们将$S$按空白格数量$k$进行分类，然后用数学归纳法证明定理$4$。

证明：

一、基础步骤：证明定理$4$对于$k=0$成立。

此时的局面$S$是终局$F$，分两种情况讨论：

$1$. 四连通绿方获胜，则有$f(p,S)=g(p,S)=1$，

$2$. 八连通红方获胜，则有$f(p,S)=g(p,S)=0$。

综上所述，定理$4$对于$k=0$成立。

二、归纳步骤：假设定理$4$对于$k=m$成立，证明定理$4$对于$k=m+1$成立。

当$k=m+1$时，根据$f(p,S)$的定义，我们有

$f(p,S)=p*max\{f(p,P_1),...,f(p,P_{m+1})\}+q*min\{f(p,Q_1),...,f(p,Q_{m+1})\}$

$=max\{p*f(p,P_1),...,p*f(p,P_{m+1})\}+min\{q*f(p,Q_1),...,q*f(p,Q_{m+1})\}$

其中局面$P_1,...,P_{m+1}$和$Q_1,...,Q_{m+1}$均为包含$m$个空白格的局面。

由于定理$4$对于$k=m$成立，所以有

$f(p,S)=max\{p*g(p,P_1),...,p*g(p,P_{m+1})\}+min\{q*g(p,Q_1),...,q*g(p,Q_{m+1})\}$

根据定理$3$，对于所有的$i$，我们有

$g(p,S)=p*g(p,P_i)+q*g(p,Q_i)$

所以$q*g(p,Q_i)=g(p,S)-p*g(p,P_i)$

所以

$f(p,S)=max\{p*g(p,P_1),...,p*g(p,P_{m+1})\}+min\{g(p,S)-p*g(p,P_1),...,g(p,S)-p*g(p,P_{m+1})\}$

$=max\{p*g(p,P_1),...,p*g(p,P_{m+1})\}+[g(p,S)-max\{p*g(p,P_1),...,p*g(p,P_{m+1})\}]$

$=g(p,S)$

所以如果定理$4$对于$k=m$成立，则定理$4$对于$k=m+1$成立。

综上所述，定理$4$对于所有的$k$都成立。

证毕。

定理$4$是一个很强悍的定理。

因为$f(p,S)$是两个绝顶聪明的人下出来的胜利概率，$g(p,S)$是两个大笨蛋下出来的胜利概率。

无论$p$取何值，局面$S$是什么样子，$f(p,S)$和$g(p,S)$竟然是恒等的。

所以定理$4$说明了两个绝顶聪明的人下这盘棋，等价于两个大笨蛋下这盘棋。

如果这样说还不够直白，我们再来看定理$4$的一个推论。

推论$1$：

———————————————————————————
无论$p$取何值，局面$S$（终局除外）是什么样子，

双方从局面$S$开始对弈，他们的最佳走法都是同一个格子。
———————————————————————————

证明：

根据定理$3$，我们有

$g(p,S)=p*g(p,P_i)+q*g(p,Q_i)$

根据定理$4$，我们把$g$换成$f$，得到

$f(p,S)=p*f(p,P_i)+q*f(p,Q_i)$

由于无论$i$取何值，等式左边的值不变，

所以当$f(p,P_i)$达到最大值的时候，$f(p,Q_i)$就达到了最小值。

所以双方的最佳走法是同一个格子。

证毕。

有了推论$1$，我们就可以很直白地解释为什么两个绝顶聪明的人下这盘棋，等价于两个大笨蛋下这盘棋：

因为双方的最佳走法是同一个格子，

所以两个绝顶聪明的人下这盘棋，

就相当于以某种顺序对$N^2$个格子进行随机染色，

具体染成什么颜色完全是根据抛硬币的结果来决定的。

由于交换染色的顺序不影响最终染色结果的概率分布，

所以我们总可以先染第$1$个格子、然后第$2$个格子、……、最后第$N^2$个格子。

就像mathe大师在此贴$4$楼提到的那样：

http://bbs.emath.ac.cn/thread-2710-1-1.html

这不正是两个大笨蛋在下这盘棋吗？

题解连续剧《跨越路障》到此告一段落。

下一次是结束语。

---

作者: KeyTo9_Fans    时间: 2010-10-23 23:21
此题的完整解答可分为三个阶段。

第一阶段是发现并证明该游戏的基本性质：双方不能同时获胜，必有一方获胜。

第二阶段是在第一阶段的基础上发现并证明该游戏的重要特点：双方的最佳走法是同一个格子。

第三阶段是在第二阶段的基础上计算公平概率：首先设计高效的算法求精确解，然后利用精确解预测极限。

我们在$11#$到$13#$讨论了第一阶段的问题，基本完成了任务，遗留下来的问题是：

http://bbs.emath.ac.cn/viewthread.php?tid=2273

该问题的期限大概为$1$年。

如果没有收到满意的答复，Fans将亲自上阵，破解该题！

在$14#$到$32#$讨论了第二阶段的问题，完美地完成了任务，证明了双方的最佳走法是同一个格子，对弈的过程等价于随机染色。

于是楼主的问题就和该问题等价了：

http://bbs.emath.ac.cn/thread-2710-1-1.html

第三阶段的工作将在上述链接的贴子中开展。

如果感兴趣，欢迎继续关注。

此游戏的人机对战平台已经打包好上传了，在本贴的$8$楼，欢迎下载并试玩。

此贴的连载到此全部结束。

感谢大家的关注和参与，感谢emath为我们提供讨论、交流、学习的平台。

希望大家能够从中学到知识，开拓视野，并感受到分析问题、解决问题的乐趣。

---

作者: KeyTo9_Fans    时间: 2015-8-14 16:22
此问题的研究成果已发表在

Entertainment Computing        Volume 4        Issue 2        April 2013        Pages 105–113

        《娱乐计算》                        第4册        第2期        2013年4月        第105至113页

欢迎有英语和数学基础的读者前往该链接研读：

http://www.sciencedirect.com/sci ... i/S1875952112000225

(, 下载次数: 19)

上传

点击文件名下载附件

感谢坛子里的各路高手们给予的帮助。

---

作者: KeyTo9_Fans    时间: 2015-12-10 19:17
关于楼主提的最后一个问题："当$n\rightarrow\infty$时，$p$的值是多少（才能使得该游戏公平）？"，楼上已经公开发表论文，

论文声称$p$的值有$95%$的概率落在$[0.59274605065,0.59274605125]$区间里（$9$个有效数字），如下图（最后一行）所示：

(, 下载次数: 31)

上传

点击文件名下载附件

该图片是楼上的附件"square .pdf"里第$8$页第$1$栏表$3$的截图。

从表中可以看出，我们的计算结果比已有的最精确结果（$2008$年，Feng, Deng and Blote，$7$个有效数字）多了$2$个有效数字，创下了新的世界纪录。

#####

然而，没过多久，我们的计算结果就被超越了，最新的结果来自参考文献[19]，

文章作者声称$p$的值有$95%$的概率落在$[0.59274605079206,0.59274605079214]$区间里。

这一说法与楼主的说法一致，而且还更准确了（$13$个有效数字）。

将这一结果ps到上表中，得到最新的表格如下：

(, 下载次数: 27)

上传

点击文件名下载附件

参考文献：

[19]Jacobsen, J. L. (2015). "Critical points of Potts and O(N) models from eigenvalue identities in periodic Temperley-Lieb algebras". Preprint. arXiv:1507.03027

---

作者: KeyTo9_Fans    时间: 2017-11-11 21:59
由于与【Jacobsen, J. L., 2015】的计算结果相比，我们的计算结果落后得太多了（落后了$4$个有效数字），实在难以赶超。

因此我打算放弃研究该游戏【抛硬币决定谁走子】的设定，转而研究该游戏【以固定序列走子】的设定。

毕竟【抛硬币决定谁走子】的运气成分太大，需要大战几百局甚至几千局才能体现出玩家的实力差距。

（就好比如果抛硬币来下围棋，那么双方主要是拼人品，而不是拼实力了）

而【以固定序列走子】则完全没有运气成分，谁赢谁输是确定的，就看玩家能否熟练掌握必胜策略了。

（围棋也是，确定贴目后，谁赢谁输是确定的，只是尚未找到必胜策略罢了）

按照新的设定重新定义的问题如下：

两个玩家（四连通方 和 八连通方）在$n\times n$的正方形棋盘里下子。

四连通方的胜利条件是连接棋盘的上下两边，

八连通方的胜利条件是连接棋盘的左右两边。

四连通方的落子密度为$p$，

八连通方的落子密度为$(1-p)$。

给定双方的落子密度后，双方使用计数器来确定落子序列：

四连通方的计数器的初始值是$(1-p)$，

八连通方的计数器的初始值是$p$，

每次由计数器值小的一方落子（如果计数器值相同，则由四连通方落子），

四连通方落子后，计数器的值增加$(1-p)$，

八连通方落子后，计数器的值增加$p$。

求$p$的阈值，使得大于等于该阈值为四连通方获胜，小于该阈值为八连通方获胜。

-----

对于上述新问题，我们有以下结论：

-----

当$n=1$时，$p$的阈值为$1/2$：谁先下谁赢。

-----

当$n=2$，$p=3/5$时，

四连通方的计数序列为：$2/5,4/5,6/5$，

八连通方的计数序列为：$3/5,6/5$，

得到走子序列：四八四四，

于是四连通方必胜。

而如果$p$的值比$3/5$小一丁点儿，走子序列就变成【四八四八】了，结果八连通方必胜。

所以当$n=2$时，$p$的阈值为$3/5$。

-----

当$n=3$，$p=4/7$时，

四连通方的计数序列为（分母$7$省略）：$3,6,9,12,15$，

八连通方的计数序列为（分母$7$省略）：$4,8,12,16$，

得到走子序列：四八四八四四八四，

于是四连通方必胜。

而如果$p$的值比$4/7$小一丁点儿，走子序列就变成【四八四八四八四四】了，结果八连通方必胜。

所以当$n=3$时，$p$的阈值为$4/7$。

-----

当$n=4$，$p=7/12$时，

四连通方的计数序列为：$5,10,15,20,25,30,35$，

八连通方的计数序列为：$7,14,21,28,35$，

得到走子序列：四八四八四四八四八四四八，

于是四连通方必胜。

而如果$p$的值比$7/12$小一丁点儿，走子序列就变成【四八四八四四八四八四八四】了，结果八连通方必胜。

所以当$n=4$时，$p$的阈值为$7/12$。

-----

当$n=5$，$p=11/19$时，

四连通方的计数序列为：$8,16,24,32,40,48,56,64,72,80,88$，

八连通方的计数序列为：$11,22,33,44,55,66,77,88$，

得到走子序列：四八四八四四八四八四八四四八四八四四八，

于是四连通方必胜。

而如果$p$的值比$11/19$小一丁点儿，走子序列就变成【四八四八四四八四八四八四四八四八四八四】了，结果八连通方必胜。

所以当$n=5$时，$p$的阈值为$11/19$。

-----

对于更大的$n$，结果是多少呢？

（别试图去数列网站搜答案。如果没有人提交过这个数列，那么即使把整个网站翻个底朝天也不可能找到答案的        :）

---

欢迎光临 数学研发论坛 (https://bbs.emath.ac.cn/)

Powered by Discuz! X3.5