找回密码
 欢迎注册
查看: 69152|回复: 35

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

[复制链接]
发表于 2009-10-8 21:44:00 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
我设计了一个游戏。
两人在n*n的正方形棋盘中下子。
每一步轮到谁下是随机决定的。
轮到某一方下子的概率为p,另一方为(1-p)。
双方的胜利条件都是将棋盘的对边用自己的棋子连起来。
其中一方连接上下两条边,棋子是四连通的。
另一方连接左右两条边,棋子是八连通的。

精华
如果觉得以上规则描述得不够清楚,可以在这里阅读具体细节:
http://tieba.baidu.com/f?kz=643280306

为了公平,我们希望当双方均以最佳策略下子时,胜率各为50%。
所以我们应该为执四连通棋子的一方赋予更大的下子概率p,即p≥0.5。
对于不同规模的n,p的值是不同的。
例如:
当n=1时,p取0.5。
当n=2时,p取sqrt(1-sqrt(0.5))。

但对于更大的n,如何求对应的p值?
另外,当n→∞时,p的极限是多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-10-8 21:52:08 | 显示全部楼层
欢迎KeyTo9のFans的到来.
对于较大的n,计算p应该很难.但是我估计极限为1
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-10-8 21:57:07 | 显示全部楼层
上面考虑的不对.如果p大于7/8,那么四连通方基本可以考虑将八连通方的所有棋子给围起来了.所以极限应该小于7/8.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-10-8 22:52:21 | 显示全部楼层
试贴一张n=3的博弈树、方程和求解结果的图片,以便核对数据。



图片来自百度空间的相册。

如果不允许将图片贴在百度以外的论坛,则尝试用此链接查看:

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-10-9 07:54:22 | 显示全部楼层
也非常欢迎KeyTo9のFans的到来。

可以将图片做为附件直接上传到论坛的,
然后将它插入到适当的位置即可(形成图文混排效果)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-10-9 09:04:53 | 显示全部楼层
也非常欢迎KeyTo9のFans的到来。

可以将图片做为附件直接上传到论坛的,
然后将它插入到适当的位置即可(形成图文混排效果)。
gxqcn 发表于 2009-10-9 07:54

好大的图
aee7294e38d3c324b2de0508.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-10-9 16:52:51 | 显示全部楼层
也许极限是$2/3$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-10-10 22:34:55 | 显示全部楼层
关于此游戏,我编了一个人机对战的平台,欢迎试玩。

e2.rar (258.5 KB, 下载次数: 7, 售价: 10 枚金币)

在e2.txt里可以设置参数。

#####

其中第一个参数表示你选哪一方。(1:四连通的绿方 2:八连通的红方)

第二个参数表示正方形棋盘的规模。(15表示棋盘有15行15列)

最好不要超过25*25,因为棋盘太大电脑会跑得很辛苦。

第三个参数表示格子的大小。(40表示一个格子的大小为40像素*40像素)

第四个参数表示红色棋子出现的概率是32768分之几。(默认值13400表示红色棋子出现的概率是13400/32768)

关于游戏界面:

右方的方块表示轮到谁下。

下面的红绿条表示红绿棋子出现的比例。(游戏过程中不会改变)

右上角还有计分条。(计分条很细,不仔细看是看不清的)

这个游戏的输赢有很大的运气成分,所以要玩十几局乃至几十局才知道双方的大致实力。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-10-10 23:47:30 | 显示全部楼层
扒头看看有啥有趣的题目,就看到这个
这个精确值很难地说,我想了个求近似的法子,不知差多远
首先,8的一方太优势了,所以策略上应该几乎不用顾虑自己的连通性,既然一定有一方会赢,那么阻断对方就是胜利;4的一方堵对方困难较大,老老实实向目标前进可能就是比较好的策略
考虑n较大时,各方可能会先散布一些中间点(有些像围棋那样),然后再将中间点连起来。
基于上面假设的策略,计算p:
设4的一方的两个联络点是一条直线上距离n的两点,计算两个点连上的概率
分别计算8方的1次干扰、2次干扰 ... k次干扰
对k次干扰还要区分干扰的连续情况(这需要考虑k的分划数),每r次连续干扰,将导致4方要多费2r步才能绕过。
总之,基于这样的假设求极限也是比较困难的,不过感觉可算了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-20 21:46:42 | 显示全部楼层
我感觉我已经在论坛里呆了快两年了。

可是翻出自己首次在本轮坛发的这篇贴子一看,日期是09年底,说明自己其实呆了一年也不到。

都怪郭兄把我晋升得太快,从“新生入学”->“小试牛刀”直接晋升到“版主”->“超级版主”,

让我高估了自己的资历。

按照正常的步伐,Fans现在应该只是个“实习记者”而已。

对于此问题,Fans的研究已经接近尾声。

从现在起,Fans将陆续把此题的详细解答过程整理好并发上来。

内容挺多的,所以每天有空的时候写一点,又有空的时候再写一点。

直到把所有的解答步骤都写清楚为止。

希望最后用不着Fans亲自来写了。

因为写到一半的时候,论坛里的大牛们可能会等不及了。

于是“啪”的一声把后面的结果全部贴上来,瞬间秒杀此题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 19:25 , Processed in 0.064993 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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