四连通与八连通的较量

KeyTo9_Fans

我设计了一个游戏。 两人在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的极限是多少？

mathe

欢迎KeyTo9のFans的到来. 对于较大的n,计算p应该很难.但是我估计极限为1

mathe

上面考虑的不对.如果p大于7/8,那么四连通方基本可以考虑将八连通方的所有棋子给围起来了.所以极限应该小于7/8.

KeyTo9_Fans

试贴一张n=3的博弈树、方程和求解结果的图片，以便核对数据。 图片来自百度空间的相册。 如果不允许将图片贴在百度以外的论坛，则尝试用此链接查看：

gxqcn

也非常欢迎KeyTo9のFans的到来。 可以将图片做为附件直接上传到论坛的， 然后将它插入到适当的位置即可（形成图文混排效果）。

〇〇

也非常欢迎KeyTo9のFans的到来。 可以将图片做为附件直接上传到论坛的， 然后将它插入到适当的位置即可（形成图文混排效果）。 gxqcn 发表于 2009-10-9 07:54

好大的图

mathe

也许极限是$2/3$

KeyTo9_Fans

关于此游戏，我编了一个人机对战的平台，欢迎试玩。 e2.rar (258.5 KB, 下载次数: 7, 售价: 10 枚金币)

2009-10-10 22:34 上传

点击文件名下载附件

在e2.txt里可以设置参数。 ##### 其中第一个参数表示你选哪一方。（1:四连通的绿方 2:八连通的红方） 第二个参数表示正方形棋盘的规模。（15表示棋盘有15行15列） 最好不要超过25*25，因为棋盘太大电脑会跑得很辛苦。 第三个参数表示格子的大小。（40表示一个格子的大小为40像素*40像素） 第四个参数表示红色棋子出现的概率是32768分之几。（默认值13400表示红色棋子出现的概率是13400/32768） 关于游戏界面： 右方的方块表示轮到谁下。 下面的红绿条表示红绿棋子出现的比例。（游戏过程中不会改变） 右上角还有计分条。（计分条很细，不仔细看是看不清的） 这个游戏的输赢有很大的运气成分，所以要玩十几局乃至几十局才知道双方的大致实力。

shshsh_0510

扒头看看有啥有趣的题目，就看到这个 这个精确值很难地说，我想了个求近似的法子，不知差多远 首先，8的一方太优势了，所以策略上应该几乎不用顾虑自己的连通性，既然一定有一方会赢，那么阻断对方就是胜利；4的一方堵对方困难较大，老老实实向目标前进可能就是比较好的策略 考虑n较大时，各方可能会先散布一些中间点（有些像围棋那样），然后再将中间点连起来。 基于上面假设的策略，计算p: 设4的一方的两个联络点是一条直线上距离n的两点，计算两个点连上的概率 分别计算8方的1次干扰、2次干扰 ... k次干扰 对k次干扰还要区分干扰的连续情况（这需要考虑k的分划数），每r次连续干扰，将导致4方要多费2r步才能绕过。 总之，基于这样的假设求极限也是比较困难的，不过感觉可算了

KeyTo9_Fans

我感觉我已经在论坛里呆了快两年了。 可是翻出自己首次在本轮坛发的这篇贴子一看，日期是09年底，说明自己其实呆了一年也不到。 都怪郭兄把我晋升得太快，从“新生入学”->“小试牛刀”直接晋升到“版主”->“超级版主”， 让我高估了自己的资历。 按照正常的步伐，Fans现在应该只是个“实习记者”而已。 对于此问题，Fans的研究已经接近尾声。 从现在起，Fans将陆续把此题的详细解答过程整理好并发上来。 内容挺多的，所以每天有空的时候写一点，又有空的时候再写一点。 直到把所有的解答步骤都写清楚为止。 希望最后用不着Fans亲自来写了。 因为写到一半的时候，论坛里的大牛们可能会等不及了。 于是“啪”的一声把后面的结果全部贴上来，瞬间秒杀此题