人工智能五子棋实现原理

这两天Alpha go 和李世石的围棋大战被炒的沸沸扬扬,今天李世石终于为人类扳回了挽回脸面的一局,不管是不是Alpha go故意放水,也不管是不是李世石找到了Alpha go的bug,总之这次围棋大战,是深度学习领域的一个影响深远的重大事件,更多的行业将开始更深入的关注人工智能深度学习领域了。个人认为,人工智能领域必定会成为即移动互联网之后的又一个更大的趋势。

好了,废话不多说,今天主要是展示一个这两天实现的一个五子棋AI,实现方式很简陋,完全不能和阿法狗相提并论,和大家分享的同时也当作自己练手,写的不好请多多包含。

项目地址见文章末尾。


关于棋盘棋子的实现逻辑我就不多说了,大家可以看源码,并不复杂,说说AI部分的实现吧:

我的实现思路是:

当玩家走下一步棋的时候,AI要考虑两个因素:

1.走对自己获得胜利最有利的点(说白了就是最接近5子连线的点)

2.堵对对方获得胜利最有利的点(说白了就是堵对方的棋子)

做到这两步就能实现一个初级阶段的人工智能了。

那么接下来就讲讲关于计算获得胜利最有利的点是如何计算出来的:

其实原理也比较简单:

在棋盘上计算每个空白位置的点的4个方向(横向,纵向,左上角到右下角方向,右上角到左下角方向)每个有可能获胜的方向所连成的以当前棋子为出发点的长度为获胜棋子数量的(五子棋为5)中途没有被敌方棋子阻挡的所覆盖的己方棋子数。(是不是很绕,反正如果是我看到会被绕晕,没看懂不要紧,下面有栗子,对是栗子)得出每个方向上最大棋子数之后,然后取出每个棋子四个值里最大的值作为获胜权重(win_weight)。

以下图为例:

这是一个6x6的棋盘,现在我们来计算一下白子获胜的权重:

那么权重是如何计算的呢?举个栗子来说明吧:

首先定义这个棋盘坐标系x方向是向右的,y方向是向下的,左上角的位置是(0,0),(x,y)可以定义一个棋子的坐标。定义xy方向为左上角到右下角方向,yx方向为右上角到左下角方向。

(0,0)点的权重计算:首先判断这一点没有连成5子的可能性,权重为0。

(0,2)点的权重计算:首先判断这一点没有连成5子的可能性,权重为0。

(0,3)点的权重计算:首先判断这一点有连成5子的可能性,接下来x轴方向上经过当前位置可连成五子的棋子有0个,y轴方向上经过当前位置可连成五子的棋子有1个,xy方向不存在连成5子的可能性,yx方向上不存在连成5子的可能性,四个方向中,取最大值,结果为1,那么当前点的获胜权重为1。

以此类推,可以得出所有空白点的白字获胜权重。

那么我们下一步让AI直接走获胜权重最大的点是不是就可以了呢?

非也非也。我们不能只考虑自己获胜,也要考虑防止对手获胜。那么如何防止对手获胜呢?我的方式就是走对手获胜权重最高的位置就可以了,就素堵住对方的棋子(传说中的走别人的路,让别人无路可走)。

同样的方式,我们可以求得黑子的获胜权重(win_weight)分布:

可以看出在(0,0),(0,2),(0,4),(0,5)这几个点是黑子获胜概率最大的点。白子走在这些点就可以堵住黑棋。

好的我们得到了白子赢得胜利最有利的点,以及白子阻止黑子获得胜利最有利的点,那么问题来了:我们到底该如何选择具体走哪个点呢?

有个比较粗劣的实现方式,就是将这两个权重相加,相当于将这两个条件同等来对待,认为对白子获得胜利的影响重要性是相同的,然后取加起来权重最高的点。

但实际情况是这两个条件对获得胜利的影响是不等价的,我们要想办法来得到描述这两者之间关系的公式。这里的实现方式有:

  • 1.通过试探法(就是瞎猜)

尝试去将这两个参数相乘,取得的结果作为最终权重,来进行取值。

或者 白子的获胜权重 + R * 黑子的获胜权重, R是一个系数,我们需要通过不断的调整来接近最好的结果。

通过不断的尝试,来将最接近答案的公式猜出来。

  • 2.通过条件分情况来判断

比如下过五子棋的人都知道一个常识:当对手有三子相连,是一个很危险的情况,如果自己目前没有三子相连,那么你应该去堵住对方的连在一起的三子。那么就可以判断,当对手的win_weight >= 3 的时候,加入对手权重的判断,其余情况不考虑对手获胜权重。

  • 3.通过机器学习来让机器理解人类走棋的逻辑

构建机器学习算法,通过大量的训练数据来训练机器,从而让机器通过历史数据来算出下一步该怎么走

我认为第三种方式是最理想的实现,因为前面两种无法覆盖到所有的情况。不过目前我只是做了第一种的简单的实现,接下来会考虑逐渐完善机器学习算法。

好了,这就是我实现五子棋AI的一个大致思路,有很多人问我什么是机器学习,我觉得在这里可以用一个简单的比喻告诉大家:

人生会经历很多事情,当你年幼无知的时候,可能会由于涉世未深而犯很多次错误,当你渐渐长大了,成熟了,经历的事情多了起来,尤其是当你犯错的时候,有人对你指出这样做是错的,你犯错误的次数就会慢慢减少,这个过程就像是一个机器学习的过程。

机器积累训练数据之前,很容易出错,经过大量的训练数据训练之后,就会做的越来越好,这就是机器学习。

好了,今天就写到这里,文笔不好,请多多见谅。

欢迎交流,互相学习,互相进步,转载请表明出处。

项目地址:https://github.com/DannyLee1991/AI_wuziqi