四连通与八连通的较量

KeyTo9_Fans

首先应该要证明以下两个命题： （假设某方胜利后不结束游戏，直到整个棋盘都下满棋子为止） 命题一：当整个棋盘下满棋子时，最多只有一方获胜。 命题一的等价表述：双方不能同时获胜。 命题二：当整个棋盘下满棋子时，必有一方获胜。 命题二的等价表述：至少有一方获胜。 例如：下图所示（规模$n=2$）的局面中 八连通的红方获胜，四连通的绿方没有获胜，同时满足了以上两个命题。 我们要证明对于所有的$n$以及所有可能的下满棋子的局面，都要满足上述两个命题。 下面讨论第一个命题：双方不能同时获胜。 反证法。 假设双方同时获胜，那么他们的连通路径必定相交。 于是与 一个格子只能属于其中一方 矛盾。 所以假设 双方同时获胜 不成立。 所以双方不能同时获胜。 关于 为什么他们的连通路径必定相交 这个问题， 我们发了一张新的贴子（已经用数学语言严格地定义了四连通和八连通）： http://bbs.emath.ac.cn/viewthread.php?tid=2273 这里就不讨论了。 稍后讨论第二个命题。

wayne

发现KeyTo9_Fans超版很擅长 玩那些 概率迭代型的复杂游戏， 不知 “生命游戏”，“元胞自动机” 是否合你口味？

KeyTo9_Fans

挺适合的，我很喜欢玩。 不过只能看，没办法变成有意思的题目来做。 下面讨论第二个命题：至少有一方获胜。 证明方法：假设四连通没有获胜，利用网络流的基本性质证明八连通获胜。 这个方法曾经在此贴里用过：http://bbs.emath.ac.cn/thread-2018-2-3.html 是用来找绕障碍的环路的： 下面通过网络流的基本性质说明这种构造的正确性。 首先构造一个流量为$1$的合法的网络流： 然后把每个四连通方块看成环形流： 叠加到原来流量为$1$的网络流上： 根据网络流的基本性质，合法的网络流加上环形流，其结果仍然是合法的网络流，且流量不变，仍然为$1$。 好了，现在我们根据网络流的合法性，得到了一条从左下角出发到达右下角的路径。 路径两边肯定是异色的格子。（因为同色格子中间不可能有流量） 好了，现在沿路径左手边的八连通格子走，分$3$种情况讨论： 路径直行：对应的八连通格子也是直行； 路径左拐$90$度：对应同一个八连通格子，原地停留； 路径右拐$90$度：对应的八连通格子往斜向走一步。 按照上述规则，就可以从左下角出发，以八连通的方式到达右下角。 说明八连通方获胜。 （上述过程相当于把右手贴墙法则证了一遍） 把命题一和命题二综合起来，得到这样一个结论： 任何一个下满棋子的局面，有且只有一方获胜，没有双赢或双败的局面。 稍后讨论博弈图。

KeyTo9_Fans

首先我们抛开随机因素不提，讨论完整的博弈图。 完整的博弈图是一个有向图$G(N)$，其中$N$表示棋盘规模。 图$G(N)$的顶点是局面，边是走法。 局面就是格子集合$\{(x,y)|1<=x<=N,1<=y<=N\}$到颜色集合$\{white,green,red\}$的映射。 走法就是从一个局面通过一步合法的落子到达另一个局面的通道。 图$G(1)$有$3$个顶点，$2$条边，如下图所示。 图$G(2)$有$81$个顶点，$216$条边，如下图所示（镜面对称的局面圈在了一起）。 图$G(3)$、$G(4)$、……都太大了，这里就不画了。 稍后讨论完整博弈图的性质。

KeyTo9_Fans

性质$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

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

KeyTo9_Fans

用windows自带的画图工具画的。 虽然这个工具很简陋，但是我使用得很仔细，每一根线条都瞄得很精准。 所以才得到这些漂亮的图的。 性质$2$：若局面$S$有$k$个空白格，则局面$S$对应的顶点$V$有$2k$条出边。 证明： 因为局面$S$有$k$个空白格。 根据游戏规则，任意一方都可以在局面$S$上行动，选择一个空白格，填上自己的颜色。 四连通的绿方有$k$种选择方案，对应$k$种不同的走法； 八连通的红方也有$k$种选择方案，对应$k$种不同的走法。 所以局面$S$一共有$2k$种走法。 因为每种走法对应一条出边， 所以局面$S$对应的顶点$V$有$2k$条出边。 证毕。 稍后讨论性质$3$。

KeyTo9_Fans

性质$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

好了，现在我们开始考虑随机因素。 根据游戏规则，每下一步之前我们都抛一枚硬币。 这枚硬币有$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$是终局且四连通绿方获胜，所以： 例$2$：$S=$(红红绿,红绿绿,绿红红)。 由于$S$是终局且八连通红方获胜，所以： 例$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=$(绿白,白白)时， 稍后讨论函数$f(p,S)$的作用。

KeyTo9_Fans

之前我们做了很多抽象的准备工作：证明了该游戏是胜负分明的，即不能双赢也不能和棋；讨论了完整的博弈图及其性质；定义了一个很抽象的函数$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$出发解决楼主的问题。