四连通与八连通的较量

KeyTo9_Fans

定理$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

定理$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

此题的完整解答可分为三个阶段。

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

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

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

我们在$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

此问题的研究成果已发表在

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

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

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

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

square .pdf (999.67 KB, 下载次数: 24)

2015-8-29 18:27 上传

点击文件名下载附件

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

KeyTo9_Fans

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

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



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

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

#####

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

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

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

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



参考文献：

[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

由于与【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$，结果是多少呢？

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