四连通与八连通的较量
我设计了一个游戏。两人在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的极限是多少？ 欢迎KeyTo9のFans的到来.
对于较大的n,计算p应该很难.但是我估计极限为1 上面考虑的不对.如果p大于7/8,那么四连通方基本可以考虑将八连通方的所有棋子给围起来了.所以极限应该小于7/8. 试贴一张n=3的博弈树、方程和求解结果的图片，以便核对数据。
http://hiphotos.baidu.com/keyto9_fans/pic/item/aee7294e38d3c324b2de0508.jpg
图片来自百度空间的相册。
如果不允许将图片贴在百度以外的论坛，则尝试用此链接查看：
http://hiphotos.baidu.com/keyto9_fans/pic/item/aee7294e38d3c324b2de0508.jpg 也非常欢迎KeyTo9のFans的到来。:handshake
可以将图片做为附件直接上传到论坛的，
然后将它插入到适当的位置即可（形成图文混排效果）。 也非常欢迎KeyTo9のFans的到来。:handshake
可以将图片做为附件直接上传到论坛的，
然后将它插入到适当的位置即可（形成图文混排效果）。
gxqcn 发表于 2009-10-9 07:54 http://bbs.emath.ac.cn/images/common/back.gif
好大的图 也许极限是$2/3$ 关于此游戏，我编了一个人机对战的平台，欢迎试玩。
在e2.txt里可以设置参数。
#####
其中第一个参数表示你选哪一方。（1:四连通的绿方 2:八连通的红方）
第二个参数表示正方形棋盘的规模。（15表示棋盘有15行15列）
最好不要超过25*25，因为棋盘太大电脑会跑得很辛苦。
第三个参数表示格子的大小。（40表示一个格子的大小为40像素*40像素）
第四个参数表示红色棋子出现的概率是32768分之几。（默认值13400表示红色棋子出现的概率是13400/32768）
关于游戏界面：
右方的方块表示轮到谁下。
下面的红绿条表示红绿棋子出现的比例。（游戏过程中不会改变）
右上角还有计分条。（计分条很细，不仔细看是看不清的）
这个游戏的输赢有很大的运气成分，所以要玩十几局乃至几十局才知道双方的大致实力。 扒头看看有啥有趣的题目，就看到这个 :)
这个精确值很难地说，我想了个求近似的法子，不知差多远
首先，8的一方太优势了，所以策略上应该几乎不用顾虑自己的连通性，既然一定有一方会赢，那么阻断对方就是胜利；4的一方堵对方困难较大，老老实实向目标前进可能就是比较好的策略
考虑n较大时，各方可能会先散布一些中间点（有些像围棋那样），然后再将中间点连起来。
基于上面假设的策略，计算p:
设4的一方的两个联络点是一条直线上距离n的两点，计算两个点连上的概率
分别计算8方的1次干扰、2次干扰 ... k次干扰
对k次干扰还要区分干扰的连续情况（这需要考虑k的分划数），每r次连续干扰，将导致4方要多费2r步才能绕过。
总之，基于这样的假设求极限也是比较困难的，不过感觉可算了 我感觉我已经在论坛里呆了快两年了。
可是翻出自己首次在本轮坛发的这篇贴子一看，日期是09年底，说明自己其实呆了一年也不到。
都怪郭兄把我晋升得太快，从“新生入学”->“小试牛刀”直接晋升到“版主”->“超级版主”，
让我高估了自己的资历。
按照正常的步伐，Fans现在应该只是个“实习记者”而已。
对于此问题，Fans的研究已经接近尾声。
从现在起，Fans将陆续把此题的详细解答过程整理好并发上来。
内容挺多的，所以每天有空的时候写一点，又有空的时候再写一点。
直到把所有的解答步骤都写清楚为止。
希望最后用不着Fans亲自来写了。
因为写到一半的时候，论坛里的大牛们可能会等不及了。
于是“啪”的一声把后面的结果全部贴上来，瞬间秒杀此题:lol