定理$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:54 编辑
定理$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)$
所以如果定理$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
这不正是两个大笨蛋在下这盘棋吗？
题解连续剧《跨越路障》到此告一段落。
下一次是结束语。
此题的完整解答可分为三个阶段。
第一阶段是发现并证明该游戏的基本性质：双方不能同时获胜，必有一方获胜。
第二阶段是在第一阶段的基础上发现并证明该游戏的重要特点：双方的最佳走法是同一个格子。
第三阶段是在第二阶段的基础上计算公平概率：首先设计高效的算法求精确解，然后利用精确解预测极限。
我们在$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为我们提供讨论、交流、学习的平台。
希望大家能够从中学到知识，开拓视野，并感受到分析问题、解决问题的乐趣。
此问题的研究成果已发表在
Entertainment Computing Volume 4 Issue 2 April 2013 Pages 105–113
《娱乐计算》 第4册 第2期 2013年4月 第105至113页
欢迎有英语和数学基础的读者前往该链接研读：
http://www.sciencedirect.com/science/article/pii/S1875952112000225
感谢坛子里的各路高手们给予的帮助。
关于楼主提的最后一个问题："当$n\rightarrow\infty$时，$p$的值是多少（才能使得该游戏公平）？"，楼上已经公开发表论文，
论文声称$p$的值有$95%$的概率落在$$区间里（$9$个有效数字），如下图（最后一行）所示：
该图片是楼上的附件"square .pdf"里第$8$页第$1$栏表$3$的截图。
从表中可以看出，我们的计算结果比已有的最精确结果（$2008$年，Feng, Deng and Blote，$7$个有效数字）多了$2$个有效数字，创下了新的世界纪录。
#####
然而，没过多久，我们的计算结果就被超越了，最新的结果来自参考文献，
文章作者声称$p$的值有$95%$的概率落在$$区间里。
这一说法与楼主的说法一致，而且还更准确了（$13$个有效数字）。
将这一结果ps到上表中，得到最新的表格如下：
参考文献：
Jacobsen, J. L. (2015). "Critical points of Potts and O(N) models from eigenvalue identities in periodic Temperley-Lieb algebras". Preprint. arXiv:1507.03027
由于与【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$，结果是多少呢？
（别试图去数列网站搜答案。如果没有人提交过这个数列，那么即使把整个网站翻个底朝天也不可能找到答案的 :）
经过了9年的追赶，我们终于追上了【Jacobsen, J. L.】在2015年创下的世界纪录，于2024年6月6日成功发表了如下图所示的论文：
我们的论文指出【Jacobsen, J. L.】的计算结果的最后4位是不对的，应该纠正为如图中红线所示的结果
经过这一纠正，楼主提出的第2问（公平概率的极限值）的计算精度的最新世界纪录如下表的【This paper】所示：
我们的计算结果对不对呢？我们的计算精度能保持住多久不被后人超越呢？咱们拭目以待~
我希望以后能有更多类似的世界难题被我们这些业余数学爱好者/民间科学家率先取得突破
太难不会