用模式识别实现围棋转接器的开源Java项目——一个类似GTool2.exe的工具

2057人浏览 / 1人评论

项目效果演示

(本项目目前实测可用的程序:银星围棋5、银星围棋14、MultiGo、Leela、CUSOMI围棋、……)

GitHub地址链接:https://github.com/zhmgczh/GoAutomation/

(内含Windows绿色版和其他平台基于JVM的jar发行版)

GoAutomation欢迎页面

作为一个狂热的围棋爱好者,除了闲暇之余去网上平台下下围棋,还有就是喜欢研究围棋算法、喜欢看各种围棋软件相互对弈了。原来,银星围棋14的安装目录下有一个自动转接围棋对弈软件的工具。详情参看CSDN的一篇文章——一个让围棋软件自动对弈的工具

然而,自从我换了Windows 10操作系统之后,原先能在Windows 7上“活蹦乱跳”的GTool2.exe就莫名其妙地“蔫了”。它在Windows 10上的“终极表现”是——无法准确识别定位原本可以快速识别的围棋盘,即使有时勉强识别,下棋时鼠标单击事件也不能有效执行。看着昔日可以“引领”各大围棋软件互相对弈的工具现在无法使用,我的内心真是有些欲哭无泪,少了观看软件自动对弈的乐趣,也让我对于围棋算法的研究增添了很大难度(实测困难)。

经过一番思考之后,我决定自己把这个工具复现出来。作为掌握C/C++、Java等多种语言的计算机系的学生,如果不能随时做出自己想要的小工具,那无疑是一种耻辱。自己动手,丰衣足食。所以我花了三天三夜,做出了一个名为GoAutomation的工具。本文实录整个开发流程,并注明开发中遇到的种种问题。

首先,为何选择Java进行开发?理由有两个:第一,Java运行库种类齐全调用方便,而C系列语言接近底层,库函数较少,调用难度也比较大,显然对于一个独立的开发者不利;第二,与Java模式相近的C系列语言是C#,而我的电脑因为硬盘空间限制,无法安装Visual Studio,给C#开发增添了困难。其实用其他语言例如Python也未尝不可,但是Python运行过于依赖虚拟机,速度较慢不适合围棋转接。

选定了语言,下面就是开始思考如何构建这个工具的框架了:

如果我们的工具作为围棋转接器,那么它是不需要一个前端界面的。前端界面不仅会阻挡两个围棋软件的正常对弈,还会有系统失去焦点等等一系列问题。所以首先想到的是用热键进行触发操作、鼠标配合定位棋盘。至于如何识别棋盘的问题,也有两种思路——第一,使用传统图像识别+统计规律模式识别;第二,使用卷积神经网络。因为我们的工具功能过于单一,卷积神经网络显然尾大不掉,故不予考虑。


一个离成功只有一步之遥而无法跨越的尝试

我花了两天两夜时间完成了这个失败思路的制作,其代码依然在Automation.java文件中予以保留。说它离成功只有一步之遥,是因为在绝大多数的棋局里,这个程序都是可以正常运行的。但是它是失败的,失败原因是因为一个特定情况会导致程序出错,而这个特殊情况总会发生,难以解决。这个具体在后面论述,首先阐述开发思想和流程。

首先考虑如何识别围棋棋盘的位置。要求用户将鼠标指针对准围棋盘网格线的任意一个位置,然后我们需要对围棋网格的整体进行采样。采样的方法十分简单——用搜索算法即可。需要注意的是,我们的采样不是单纯要求相同颜色,而是颜色相近。这里我用的是简单RGB距离(后来才了解到有更好的颜色距离定义,属于计算机视觉(CV)的一种定义)。我用的是一个BFS算法,假定用户鼠标指针当前位置的像素RGB为标准色,在RGB距离色差为100的范围内进行邻域搜索,主要确定棋盘的四个坐标——左上角x坐标(min_x)、左上角y坐标(min_y)、右下角x坐标(max_x)、右下角y坐标(max_y)。

BFS确定棋盘区域

识别完棋盘,我们只要将这个近似的正方形边长分为18等份,就可以得到每个交叉点的位置,鼠标点击事件需要在这些位置触发。

还有一个重要问题——热键如何实现?我们知道,系统钩子函数脱离Java程序时任何监听器都会失效,为了使我们的程序在失去焦点时也能运行,我们使用JIntellitype(其本质是用Java调用C程序完成系统热键注册)。

下面考虑如何实现鼠标移动和单击功能。

程序自己需要将鼠标移动到指定的位置并单击,以完成落子操作,保证两个棋盘的一致性。Java对于屏幕截图和鼠标键盘操作有一个专门的库——Robot类,使用Robot类方法可以轻松完成此项操作。但是还是有需要注意的地方的,Robot类的mouseMove方法在Windows 10系统上执行时,鼠标经常飘移不定,需要将其放在循环中重复执行10次或以上。还有一个问题是mousePress和mouseRelease方法经常在一些程序里失效,这时只需要关闭杀毒软件(如360安全卫士)。

鼠标操作失效的问题让我第一次跑偏方向,本来以为这个问题的根源在于Java的Robot类自身缺陷,看网上的方法用JNI写了一个Java调用C代码(用C++调用Windows系统库并用GCC编译为dll文件)实现。这个实现还保留在项目的CRobot类中和根目录下的cpp文件夹里,是我第一次JNI尝试。最后发现这个方法与Robot类没有任何行为上的区别,还是会在一些程序里失效。后来才发现是杀毒软件阻碍了鼠标操作。需要注意的是,JNI调用C代码会让程序丧失跨平台的优良特性,所以我后来又改为Java自带的Robot类实现。

JNI调用C函数

整个程序最核心的部分就是如何识别黑白棋盘刚刚落下的子是在什么位置。

最初的思想是这样的:指定屏幕的两个区域划分为黑棋盘和白棋盘,然后用程序监测这两个区域的图像。例如,现在轮到黑棋下,那么只检测黑棋盘上的图像变化,遇到有变化的地方所属的棋盘位置即为我们找的落子位置。以此识别两个棋盘上的落子情况。

乍一看上去是没有任何问题,但是其实问题很大。这个问题出现在了围棋的“吃子”操作上,当一个棋盘上某些棋子在对弈中被吃掉,这个棋盘上变化的图像就不止集中在落子的那个位置。

吃子前状态 = 》 在A点落子后的状态

(如上图所示,若黑棋在A点落子,则白棋一子被吃,棋盘上有两个位置具有颜色变化——A点和白子所在点。)

于是我们的最初想法出现了漏洞,可以另辟蹊径或者打补丁。很遗憾,一开始选择了打补丁这一条路,结果发现还是走弯了,但是这个补丁为之后的完美思路提供了技术准备。

打补丁的方法是——用一个19*19的数组模拟棋盘的整个状态,1代表黑棋,-1代表白棋,0代表空点。然后每走一手棋就在对应位置打上标记,维护数组与实际棋盘的一致性。然后,我们对于棋盘上已经有棋子的位置不予检测,只检测目前值为0的位置。这就产生一个新问题——如何模拟围棋的吃子操作?

我是一个打ACM/ICPC竞赛的选手,所以对于围棋这样的典型曼哈顿网络图有种不一样的直觉。下面给出围棋吃子操作的形式化定义:在19*19的矩阵上,相同颜色的棋子按照其联通性分为若干联通快(一个棋子与另一个棋子联通的定义:两个棋子的颜色相同,且其中一个棋子处在另一个棋子的上、下、左、右四个位置中的一个位置),若与一个联通快相邻的所有点中没有空点(未落子的点),则认为这个联通快“已死”。

如果当前黑棋刚刚落子,用搜索算法找出并检查所有“已死”的白棋联通快,将其移除(值改为0)即可,白棋同理。考虑到围棋判断联通块死活的特性,我使用BFS判断一个联通快是否“已死”,再使用DFS除去已死的联通快。为了减小复杂度,BFS判死活时应该剪枝,使用布尔数组标记已经访问的棋子,对于已经访问的棋子不再进入搜索。

吃子操作总函数判断联通快“已死”移除“已死”的联通快

可能你们已经注意到了代码中的一个细节,除了have数组作为剪枝标记、status数组作为棋盘状态,还有一个avoid_test数组。avoid_test数组的存在是因为屏幕截图的时间问题。

如果我们在鼠标点击之后立即截图,我们的截图很可能并未包含我们刚刚落下的棋子;如果我们等待一会儿再截图,很可能对方棋盘已经落下新的棋子。所以,鼠标点击后截图让整个程序变得不稳定,需要鼠标点击之前截图作为参照图。那么,我们就需要在参照图和新图之间承受两步的差异,如此“吃子”操作的影响就也扩展到了两步之后,对于刚刚吃掉的棋子,我们需要同样回避。

随后我做出了一个有史以来最稳定的版本——“离成功只差一步”的版本。这个版本的所有代码保存在Automation.java中,实测时初看没什么问题,大多数棋局顺利终局,但是经过大量测试,发现一个“不可逾越”的问题——围棋的“打N还一”问题。

初始状态 = 》 白棋下A点后的状态 = 》 紧随其后,黑棋下B点的状态

这是一个简单的“打二还一”典例。因为我们前面的avoid_test机制,最后黑棋下B点的这一手被程序avoid_test,所以这时程序会停止或走到错误的地方。

这个思路到这里宣告彻底失败,再打补丁不是不可以,例如再截一张棋盘最初的图进行永久保存,把avoid_test的点和最初图比较,但是如此一来,第一手棋被吃的问题又无法解决。再想其他方法只会让程序变得越来越复杂,失去其可读性和拓展性,为debug增加难度。


转换思路走向完美

有没有一种非常易于理解、实现简单拓展性又很高的方法呢?

为此我查阅了一篇计算机视觉色差计算方面的CSDN文章,找到一个可行的方案,点击此处查看原文。为什么需要色差的计算?根本原因在于我们人眼识别出来的“相似”并非简单的计算机RGB值欧氏距离(原文写得很好,引用过来)。

RGB颜色空间的缺陷

有没有一个色彩空间基于人眼对于颜色的感知呢?是有的,就是LAB颜色空间。

LAB颜色空间色差计算方法

这个转换的思路其实就是对原有思路的偏离进行一些修正,首先,将颜色相似的判断方法改为LAB色差近似。

有了这个先进的相似颜色判断方法,我们接下来的模式识别就可以改进很多了。这个思路就是——直接提取一个棋盘的当前状态,而不是将其与之前的截图比较得出当前状态。得到当前棋盘的状态需要使用统计方法,也就是模式识别。

获得棋盘区域的方法和上面是相同的,只是用LAB色差取代RGB色差作为近似判断条件。得到之后,我们要做的就是将棋盘分区,分成大小近似相等的19*19=361个交叉点区域。这个过程的计算建议使用double数据类型而非整型像素点,否则识别区域会有明显偏差导致无法识别。

我使用Java对于COSUMI围棋网页游戏进行分区,结果如下(将横纵坐标和为奇数的点对应的区域标为白色):

将横纵坐标和为奇数的点对应的区域标为白色原始棋盘图识别处理出的棋盘图

可以看到我们完成了棋盘区域的划分,接下来的一步就是识别其中的黑白棋子。如何识别黑白棋子呢?我们只能采用统计的方法,基于一般性规律进行识别。目前采取的方法是——统计每个区域内近似于白色的像素点个数和近似于黑色的像素点个数,如果其大于等于整个区域像素点数量的某一比例数,即可判定为黑棋点/白棋点。

例如使用Java识别棋盘,将所有黑色像素标为蓝色、白色像素标为绿色:

原始图识别后修改的示意图

可以发现,我们想要的颜色基本都被准确地识别出来了,也基本在指定的区域内。下面就是最艰巨的一项任务——调参。

需要调的参数有两个——第一,色差在多少之内认为是“相似”;第二,近似黑色点和近似白色点在多少以上认为是满足条件的黑棋点/白棋点。这一步骤单调且复杂,为了使程序更好地兼容各个当前的各个围棋软件,我花了很长时间去确定这两个参数。(具体参数值在开源的代码中)

然后的事情就简单了很多,我们只要不断检测棋盘区域获得棋盘状态,并与当前状态进行比较,如果有一个点原来状态为0(空点),现在状态为1/-1(看当前轮到谁落子),就可以确定当前落子的是哪一手。注意还是要移除死子,执行“吃子”操作。这个逻辑的一个好处在于,可以随时读取一个正在下棋的棋盘状态(因为识别是不需要参照之前状态的),断点继续转换而不需要代价。

其实还有一个问题,突然出现两个落子该怎么办?如果突然出现两个落子,不是调参问题的话,大概率就是屏幕突然出现广告弹窗之类的错误,我们只需要当做什么都没发生,静待操作者关闭弹窗即可。

至此,这个项目就全部做完了。过程非常艰辛,但是得到的成品程序功能强大,完全满足了我的需求,是一个比较成功的项目。

当然,因为能力非常有限,所以难免有不足或需要改进之处,请大家不吝赐教。

全部评论