我喜欢逻辑游戏,同时也喜欢计算机视觉和人工智能算法。为了把这两样结合起来,开发了一个软件来检测、分析和解决一些逻辑难题,比如数独和摩天大楼。本文主要解释“LogicGamesSolver”项目,你可以在这个github存储库中找到源代码以及运行它的说明。
该项目结合了三个研究领域:
计算机视觉：在图像问题检测中的应用
深度学习：对问题中的数字进行分类
人工智能：玩游戏该软件使用Python编写,使用opencv4．01和Tensoflow 2．3．0库。它能解决三种游戏:数独、星际大战和摩天大楼。
第一步:检测第一步是检测输入图像中的谜题。其思想是找到最大的轮廓,即图像中最大的多边形。如果场景是干净的,有尽可能少的噪音和物体,则此步骤对于软件来说更容易。使用参数cv2．RETR_EXTERNAL的findContours方法找到轮廓?,仅考虑极端的外部轮廓;然后,我们根据轮廓的面积对轮廓进行排序,并取第一个元素。一旦发现了这个谜题,我们就取四个顶点进行透视变换,并使用warpeperspective对多边形的图像进行变换。
在继续之前,我们必须从网格中提取单元格的图像来分析已经写入的数字。请注意,网格长度由用户给定。方法*get_digit()*分析单元格图像以检查其是否包含数字(否则返回None),并对其进行预处理,使其成为数字分类器的合适输入图像。
第二步:谜题分析一旦我们有了谜题的平面图像,是时候对其进行分析,以获得已经提供的信息来解决游戏了。数独和摩天大楼的谜题需要考虑数字;相反,对于星战游戏,我们需要了解内部结构,以定位模式中定位的区域。数字分类器为了了解图中有哪些数字,该软件利用卷积神经网络对手写体数字进行分类,并用著名的MNIST数据集?:60000个元素,28×28像素的0-9之间的手写体单个数字灰度图像进行训练。我不想深入讨论细节,因为它是一个非常基本的CNN,而且数据集几乎在每一本深度学习书籍中都有使用。本文我只向你展示神经网络的体系结构,但是你可以在项目源代码的DigitClassifier．py类中看到实现 。
软件只在第一次执行时训练模型,然后使用保存在文件中的权重来预测数字。可以使用我的权重:提供了一种将图像转换成适合CNN的阵列的方法,同时提供一个exclude_classes数组,即不考虑该游戏的类(例如Sudoku的“ 0”,其数字在[1,9]范围内)。使用*preds．argmax(axis = 1)[0]时,*我们以最大概率将值取为正确的数字。MNIST数据集是由手写数字组成的,模型训练结束后,CNN给出了99%的准确率。但是,由于字体的原因,我在使用时遇到了一些错误:书写的数字可能与手写的数字有很大的不同,例如,“4”通常被预测为“9”,而“3”则被预测为“8”。为了解决这个问题,我决定不仅考虑图像,还要考虑最后7个数字,并考虑同一单元格的7位预测中最频繁出现的数字预测。
连接成分分析对于星际大战,没有数字可以识别,但是网格区域可以定位,为此,我们需要首先删除内部网格线,然后提取连接的组件。在前4行中,我们应用腐蚀过滤器去除较浅的行,然后应用阈值仅高亮显示区域的边缘,最后我们寻找连接的组件,用不同的颜色给区域着色。
这是一个实时过程,以便用户可以确认(按空格键)何时区域定位良好,一旦用户确认,网格中的单元格将按其中心像素的颜色分组,从而定义问题区域。
第三步:解谜现在我们已经有了解决游戏的所有要素。和其他许多逻辑益智游戏一样,数独、星战和摩天大楼都可以描述为约束满足问题。CSP包含三个元素:一组我们想要找到正确值的变量每个变量可能值的域定义问题的一组约束例如我们的数独游戏:变量:网格的81个单元格域:范围{1,9}(不包括已填充的单元格)约束:游戏规则类似的表示法可以用于许多问题和游戏,也可以用于摩天大楼和星战,但其中有一个特点:单元的域是{0,1},表示星体的存在(1)或不存在(0)。一个解决方案是一个特定的变量分配,使每个约束都得到满足。源代码有点长,但我想向你解释用于在软件中解决csp的递归回溯搜索的思想,显示算法的核心部分。我知道,这很复杂,但它背后的思想非常简单:算法通过单变量赋值(技术上是深度优先搜索)来搜索解,直到找到一个完整的赋值(由is_complete方法控制)。在每一步中,算法获取一个没有赋值的变量(select_unassigned_variablee),选择其域中一个未经验证的值,并查看发生了什么。如果对于赋值,当前状态尊重所有约束(is_consistent方法),我们再次调用算法来检查赋值是否完成,否则我们删除当前变量并返回到前一状态以尝试使用不同的值。如果你阅读了全部代码,你会发现使用了一些启发式方法来加速求解过程。一种是简单推理,我尝试通过检查是否可以执行一些简单的推理来分配一些变量:例如,对于数独来说,如果一行、一列或一个正方形包含8个明显的值,则很明显这是缺失值;另一种启发式方法用于给定变量的值选择。在启发式方法中,如果选择某个变量的值违反了某些游戏规则,则从该变量的域中删除该值。从计算的角度来看,该算法将搜索空间从O(d ^ n!)减少到O(d ^ n),但值得注意的是,如果没有启发式算法,算法可能会非常慢。
最后考虑我们生活在一个不再让我们感到惊讶的时代:人工智能对我们生活的社会影响如此之大,以至于我们对新技术变得冷漠,也许有时候我们应该停下来反思一下,生活在这个革命时代,我们是多么幸运。让我们以这个简单的项目为例,该软件(约50KB的内存,分布在4个文件上)使用计算机视觉算法进行图像分析和透视变换,使用卷积神经网络进行数字分类,并且该算法在几秒钟内解决了一个逻辑问题,这至少需要我们几分钟的时间。每一种算法都是世界各地几十年来研究和实验的成果,它是整整一代科学家的遗产。
