数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2010-10-12 14:21:41 | 显示全部楼层
本帖最后由 KeyTo9_Fans 于 2010-10-12 20:10 编辑

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

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

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

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

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

均采用最佳策略的时候,

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

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

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

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

习题$1$:

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

解:

example1.png

习题$2$:

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

解:

example2.png

以上两道习题都很简单。

因为局面$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)$。

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

process.png

好了,现在我们已经知道了:

$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$:

lv1.PNG

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

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

lv2.PNG

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

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

lv3.PNG

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

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

lv4.PNG

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

最高层是空局面$E$。

lv5.PNG

只有当底下所有的$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$

稍后讨论最佳策略下的博弈图(简称博弈图)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-12 20:07:24 | 显示全部楼层
本帖最后由 KeyTo9_Fans 于 2010-10-12 20:12 编辑

定义$4$:

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

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

对于每个顶点$S$(终局除外),都只有两条出边:

$S->P$,$S->Q$。

其中:

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

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

如果有多种最佳走法,则规定:

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

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

例如:

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

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

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

tree_1.PNG

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

tree_2.PNG

本贴的第一张图就是$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:17 | 显示全部楼层
终于连载完了,一直没好意思插楼,题解的连载比小说连载更吊胃口。。。
话说或许可以考虑下多项式的通项,而且目前对n->inf的情况也还没有讨论
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-12 22:03:00 | 显示全部楼层
我一直都在很努力地画图。

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

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

你说得很正确。

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

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

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

我会尽快作决定的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-13 13:41:31 | 显示全部楼层
新问题已经提出。点击此连接查看:

/thread-2710-1-1.html

欢迎讨论。

期限大概$1$个月。

如果没有收到满意的回复,Fans将再次出马,亲自上阵,继续连载,破解该题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-10-14 10:46:06 | 显示全部楼层
LZ的这个问题连载中或许存在某个小缺陷,呵呵。
LZ说f(p,E)是关于p的多项式函数,或许还暗示了决策与p是无关的。

然而,在一些情况下,下一步的决策是与p相关的。
举一个例子来说,见下图的S,(我不知道是如何走到这种局面的。)
假设此时,四连通的绿方幸运的轮到了,那么他是选择1的位置还是选择2的位置呢?
设他选择1和2之后,获胜的几率分别是P1和P2,P1和P2的曲线如图,它们相交于0.618。因此,对于图中的S,f(p,S)是分段的多项式函数。在某些情况下,决策是和p相关的。这种可能性使得题目的复杂度有所增加。
1.JPG
或许游戏可以设计成这样:
1、每次投币,p=0.5;
2、棋盘变成长方形,让四连通的绿方的边比较长,从而补偿连通上的劣势。
问:棋盘的长宽是多少比较公平?

最后,支持7层的观点一下。(呵呵,只是感觉上的,联想起了围棋中扳粘和小尖的关系。)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-14 13:57:57 | 显示全部楼层
本帖最后由 KeyTo9_Fans 于 2010-10-14 14:04 编辑

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

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

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

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

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

根据即兴的回忆,这个反例大概是:

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

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

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

其优点在于:

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

#####

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

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

我在这里还要出续集。

等续集完了之后会考虑楼上的新问题的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-15 00:24:13 | 显示全部楼层
本帖最后由 KeyTo9_Fans 于 2010-10-15 00:25 编辑

下集预告:

Fans的续集指的是什么呢?

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

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

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

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

如果能证明一个定理:

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

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

我们就可以认为:

————————————————————————
两个绝顶聪明的人(比如emath和mathe)玩这个游戏,

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

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

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

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

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

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

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

面对这个路障,Fans又是如何应对的呢?

他能顺利跨过这道坎吗?

敬请收看下集:《跨越路障》
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-16 17:55:58 | 显示全部楼层
题解连续剧《跨越路障》现在开始!

定义$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)$的显式表达式。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-17 20:13:12 | 显示全部楼层
下面公布习题$3$的答案。

————————————————————————
解:

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

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

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

它们是:

col_list.PNG

因为$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)$的递推式。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-12-7 01:44 , Processed in 0.064512 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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