与随机电脑玩搭桥游戏

KeyTo9_Fans

在$N$*$N$的棋盘上与随机电脑玩一个搭桥游戏。

我们每放一块木板，电脑就会随机地放$f(N)$块障碍。

木板不能放在障碍上，障碍也不会放在木板上。

如果我们用木板将棋盘的上边界与下边界连起来了(四连通)，我们就获胜了。

我们总是用最佳策略放木板。

求$f(N)$使得我们的胜率为$50%$。

KeyTo9_Fans

搭桥游戏的程序，自动判断输赢，大家可以试玩一下：

b4.rar (429.99 KB, 下载次数: 8)

2011-10-11 16:18 上传

点击文件名下载附件

点击空格子放木板，木板是四连通的，要求纵向搭桥。

#####

问题$2$：如果我们的木板是八连通的，那么$f(N)$又是多少？

大家可以试玩一下：

b8.rar (429.98 KB, 下载次数: 2)

2011-10-11 16:18 上传

点击文件名下载附件

玩法同上，但木板变成了八连通的，要求横向搭桥。

KeyTo9_Fans

考虑我方先行的情况：

当$N=1$时，我方必胜，不存在$f(N)$使得胜率为$50%$。

当$N=2$时，胜率为$f(N)/3$。所以当$f(N)=1.5$时，胜率为$50%$（此时电脑以$50%$的概率放$1$个障碍，以$50%$的概率放$2$个障碍）。

……

当$N$较小时，求得$f(N)$意义不大。

希望可以得到当$N->\infty$时，胜率为$50%$的$f(N)$的近似公式。