正方形棋盘上的连通博弈

KeyTo9_Fans

KeyTo9_Fans和KeyTo9在$N$*$N$的棋盘上玩一个连通博弈游戏。 两人轮流走，每次占领$1$个空格子，直到整个棋盘都占满为止。 下图是一个$N=3$的例子，KeyTo9_Fans用绿色，KeyTo9用红色，落子顺序用数字表示。 在这局游戏中，KeyTo9_Fans制造出了一个面积为$4$的连通块。 现在假设棋盘足够大，并且双方都足够聪明。 问KeyTo9_Fans能否制造出一个面积为$25$的连通块？ 如果能，需要多大的棋盘？ 如果不能，最大面积是多少？

zeroieme

参考围棋杀气 长一子增加3气，理论上连通块可以无限大

gxqcn

楼主研究连通博弈蛮多的。 不知这题与围困小猫游戏是否有关联？

wsc810

蛮有意思的一个游戏，建议楼主先编一个人和电脑随机数进行的游戏，棋盘格子不要太大（最大设为13）。游戏结束后，由程序自动计算最大连通块。 然后各位贴图看谁的连通块最大。

gxqcn

这段时间，晚饭后儿子要缠着我下盘围棋， 不知道是否有这样的软件，可以自动统计围棋成绩的？不至于非得要人工去数棋子。

zeroieme

一般的单机围棋软件都有。

gxqcn

我说的是在真正的棋盘（不是电脑上的虚拟棋盘），下完后拍个照， 然后能有个软件自动统计出棋子数目。

KeyTo9_Fans

20太容易突破，改成25了。 ##### 郭兄提出的问题是数字图像处理的一个特殊的案例。 关于用数字图像处理方法统计围棋棋子目数这个具体的问题，我想肯定已经有人做过了。 只是能用到的该软件的场合非常少，所以我估计该软件不会在网上发布。 该程序首先要读入一张格式为24位bmp的图片（或者将别的格式转换成24位bmp格式）。 这样就可以根据24位bmp文件的二进制码直接得到图片的高度和宽度，以及每个象素的红、绿、蓝参数。 然后要在图中找符合下述特征的梯形区域（正方形棋盘拍下来会变成梯形）： 1.该区域有很多椭圆形的黑块和椭圆形的白块； 2.没有被椭圆黑块或椭圆白块覆盖的地方，有两个不同方向的线条相交。 然后要把该区域的4个顶点找出来： 1.该点的线条有L型的拐弯。 2.或者该点是黑块或白块，并且只有2个方向有线条、黑块、或白块。 然后连接4个顶点，得到4条边。 然后根据黑块、白块和线条的位置把每条边成18份（构造19条线）。 19条横线和19条竖线一共有361个交点，逐个检查该交点是普通线条、黑块、还是白块。 361个交点的状态都得到以后，调用单机围棋软件的数子算法即可。 上述方法要求棋盘周围没有类似的黑块、白块、或线条干扰。 如果你的地砖本来就有很多像围棋一样的黑块或白块，或者像棋盘上的线条，上述处理方法就会出错。（这时需要更精确更严格的辨别实物和干扰物的方法）

gxqcn

我想这个软件还是有点用处的：比如说业余棋手晋级比赛等。

gxqcn

难得 KeyTo9_Fans 将算法的难点也分析了下。 其实，可以在拍照前先仍工将空白填满。 虽然可以通过智能识别的方式数空白， 对于计算机很难判定是否为残局， 即有大量公共气。