正方形棋盘上的连通博弈
本帖最后由 KeyTo9_Fans 于 2011-9-29 13:31 编辑KeyTo9_Fans和KeyTo9在$N$*$N$的棋盘上玩一个连通博弈游戏。
两人轮流走，每次占领$1$个空格子，直到整个棋盘都占满为止。
下图是一个$N=3$的例子，KeyTo9_Fans用绿色，KeyTo9用红色，落子顺序用数字表示。
在这局游戏中，KeyTo9_Fans制造出了一个面积为$4$的连通块。
现在假设棋盘足够大，并且双方都足够聪明。
问KeyTo9_Fans能否制造出一个面积为$25$的连通块？
如果能，需要多大的棋盘？
如果不能，最大面积是多少？ 参考围棋杀气
长一子增加3气，理论上连通块可以无限大 楼主研究连通博弈蛮多的。:)
不知这题与围困小猫游戏是否有关联？ 蛮有意思的一个游戏，建议楼主先编一个人和电脑随机数进行的游戏，棋盘格子不要太大（最大设为13）。游戏结束后，由程序自动计算最大连通块。 然后各位贴图看谁的连通块最大。 这段时间，晚饭后儿子要缠着我下盘围棋，
不知道是否有这样的软件，可以自动统计围棋成绩的？不至于非得要人工去数棋子。 一般的单机围棋软件都有。 我说的是在真正的棋盘（不是电脑上的虚拟棋盘），下完后拍个照，
然后能有个软件自动统计出棋子数目。 本帖最后由 KeyTo9_Fans 于 2011-9-29 13:30 编辑
20太容易突破，改成25了。
#####
郭兄提出的问题是数字图像处理的一个特殊的案例。
关于用数字图像处理方法统计围棋棋子目数这个具体的问题，我想肯定已经有人做过了。
只是能用到的该软件的场合非常少，所以我估计该软件不会在网上发布。
该程序首先要读入一张格式为24位bmp的图片（或者将别的格式转换成24位bmp格式）。
这样就可以根据24位bmp文件的二进制码直接得到图片的高度和宽度，以及每个象素的红、绿、蓝参数。
然后要在图中找符合下述特征的梯形区域（正方形棋盘拍下来会变成梯形）：
1.该区域有很多椭圆形的黑块和椭圆形的白块；
2.没有被椭圆黑块或椭圆白块覆盖的地方，有两个不同方向的线条相交。
然后要把该区域的4个顶点找出来：
1.该点的线条有L型的拐弯。
2.或者该点是黑块或白块，并且只有2个方向有线条、黑块、或白块。
然后连接4个顶点，得到4条边。
然后根据黑块、白块和线条的位置把每条边成18份（构造19条线）。
19条横线和19条竖线一共有361个交点，逐个检查该交点是普通线条、黑块、还是白块。
361个交点的状态都得到以后，调用单机围棋软件的数子算法即可。
上述方法要求棋盘周围没有类似的黑块、白块、或线条干扰。
如果你的地砖本来就有很多像围棋一样的黑块或白块，或者像棋盘上的线条，上述处理方法就会出错。（这时需要更精确更严格的辨别实物和干扰物的方法） 我想这个软件还是有点用处的：比如说业余棋手晋级比赛等。 难得 KeyTo9_Fans将算法的难点也分析了下。
其实，可以在拍照前先仍工将空白填满。
虽然可以通过智能识别的方式数空白，
对于计算机很难判定是否为残局，
即有大量公共气。
页:
[1]
2