找回密码
 欢迎注册
楼主: KeyTo9_Fans

[原创] 四连通与八连通的较量

[复制链接]
 楼主| 发表于 2010-7-21 14:00:08 | 显示全部楼层
首先应该要证明以下两个命题:

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

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

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

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

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

例如:下图所示(规模$n=2$)的局面中

final_1.PNG

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

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

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

反证法。

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

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

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

所以双方不能同时获胜。

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

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

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

这里就不讨论了。

稍后讨论第二个命题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-24 15:29:34 | 显示全部楼层
发现KeyTo9_Fans超版很擅长 玩那些 概率迭代型的复杂游戏,
不知 “生命游戏”,“元胞自动机” 是否合你口味?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-31 22:03:59 | 显示全部楼层
挺适合的,我很喜欢玩。

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

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

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

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

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

8_path.PNG

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

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

8_flow.PNG

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



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

8_flow_p.PNG

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

8_flow_pp.PNG

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

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

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

路径直行:对应的八连通格子也是直行;

路径左拐$90$度:对应同一个八连通格子,原地停留;

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

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

8_flow_r.PNG

说明八连通方获胜。

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

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

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

稍后讨论博弈图。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-5 15:18:58 | 显示全部楼层
首先我们抛开随机因素不提,讨论完整的博弈图。

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

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

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

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

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

graph1.PNG

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

graph2.PNG

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

稍后讨论完整博弈图的性质。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-7 13:21:22 | 显示全部楼层
性质$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$。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-10-7 19:59:26 | 显示全部楼层
14# KeyTo9_Fans

一直诧异 Key 版主 这么漂亮的图是用什么画的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-8 12:07:10 | 显示全部楼层
用windows自带的画图工具画的。

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

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

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

证明:

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

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

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

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

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

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

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

证毕。

稍后讨论性质$3$。

评分

参与人数 1威望 +3 经验 +3 收起 理由
winxos + 3 + 3

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-8 12:28:56 | 显示全部楼层
性质$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)$上讨论楼主设计的游戏。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-11 10:07:53 | 显示全部楼层
好了,现在我们开始考虑随机因素。

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

这枚硬币有$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$是终局且四连通绿方获胜,所以:

f(p,F)=1.PNG

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

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

f(p,F)=0.PNG

例$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).PNG

稍后讨论函数$f(p,S)$的作用。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-11 11:26:14 | 显示全部楼层
本帖最后由 KeyTo9_Fans 于 2010-10-11 18:34 编辑

之前我们做了很多抽象的准备工作:证明了该游戏是胜负分明的,即不能双赢也不能和棋;讨论了完整的博弈图及其性质;定义了一个很抽象的函数$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$出发解决楼主的问题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 05:28 , Processed in 0.048863 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表