人机五子棋实现原理

人机五子棋

近期整理代码的时候，发现大二的时候（目前大三）做的几个课程设计还不错，所以把这部分的代码以及设计文档都开源出来，以供后者参考学习使用。

完整代码以及本文的word都在放在了Github上，你可以下载或使用它：人机五子棋项目地址，如果喜欢的话，就去点个Star吧

具体效果如下图，我是黑方（先手），机器是白方，本局机器胜。

从图中大概可以看出，它已经具备了一点点的智能，想了解它是如何被创造出来的吗？请继续…

任务设计书

本项目要实现的是五子棋人机版，通过制定棋型的评分表使机器能够对棋盘局势评估。五子棋玩家双方分别称为“人”、“机器” ，当人落子后，机器对棋盘扫描获取可行棋的位置集合，然后遍历该集合，利用评估函数对每个空位依次估分，得分最高的位置即为机器要落子的位置，在使用评估函数对空位打分时，为了避免机器只攻不守，需要使用“换位思考”的思想，也就是说打分时不仅考虑自身，还要考虑对方。

类与对象的设计

位置实体类Location
Location类封装棋盘上的一个位置，AI对局势分析时会对位置打分，所以位置实体类应该有个字段保存位置分数，Location类的设计如图1所示。

1）public Location(int x, int y)
构造函数。x：横坐标，y：纵坐标
2）public Location(int x, int y, int player)
构造函数。x：横坐标，y：纵坐标，player：位置所有者
3）public Location(int x, int y, int player, int score)
构造函数。x：横坐标，y：纵坐标，player：位置所有者，score：位置分数
4）public void setX(int x)
设置横坐标的值
5）public void setY(int y)
设置纵坐标的值
6）public void setScore(int score)
设置位置分数
7）public void setPlayer(int player)
设置该位置由玩家player落子，player可取：Chess.PLAYER、Chess.AI
8）public int getX()
获取对象的横坐标
9）public int getY()
获取对象的纵坐标
10）public int getPlayer()
获取该位置是由哪位玩家所有
11）public int getScore()
获取该位置的分数

自定义棋盘类ChessPanel
ChessPanel类负责视图上的事情，如棋盘以及棋子的绘制、棋盘状态的保存、落子、清空等事件，ChessPanel类的设计如图2所示。

1）public void paint(Graphics g1)
重写该方法，绘制棋盘、棋子
2）public void drawBoard(Graphics2D g)
绘制棋盘
3）public void drawChessman(Graphics2D g)
绘制棋子
4）public void clearBoard()
清空棋盘
5）public void doPlay(int row, int col, int player)
玩家在视图上落子

控制器类Chess
Chess类主要负责逻辑上的各个事件，如逻辑上落子、AI局势分析、胜负判定等，Chess类的设计如图3所示。

1）public void setFirst(int first)
设置先手的玩家
2）public Chess()
构造函数，进行棋局的初始化
3）public void restart()
棋局初始化
4）public Location start()
AI先手时调用，决策第一手棋位置
5）public boolean play(int x, int y, int player)
玩家落子。x，y是落子坐标，player的取值：Chess.AI、Chess.PLAYER，返回值表示是否落子成功
6）public void showToConsole()
显示棋盘信息到控制台
7）private void addToList(List allMayLocation, int x, int y)
添加位置到可行棋的位置集合，过滤重复的位置
8）public Location explore()
返回分数最高的位置
9）private List<Location> getAllMayLocation()
得到可行的位置集合
10）public boolean isWin(int x, int y, int cur)
判断胜负，x、y是落子位置，cur是Chess.AI、Chess.PLAYER
11）public int getScore(int x, int y)
局势评估函数，计算总得分
12）private int getScoreBySituation(int count1, int leftStatus, int rightStatus)
根据棋型计算空位得分，count1为相连棋子数，leftStatus、rightStatus为1或2，1代表为空，2为墙或者对方棋子
13）public int getXScore(int x, int y, int cur)
横向扫描计算得分
14）public int getYScore(int x, int y, int cur)
纵向扫描计算得分
15）public int getSkewScore1(int x, int y, int cur)
正斜向扫描计算得分
16）public int getSkewScore2(int x, int y, int cur)
反斜向扫描计算得分

视图类View
View类主要负责游戏窗口的显示以及对Chess、ChessPanel进行调度，通过调用控制器的方法来控制逻辑上的棋局，通过调用ChessPanel的方法来控制视图上的棋局，View类的设计如图4所示。

1) public void create()
创建视图
2) public void restartBoard()
棋局重开
3) public void showChess(ChessPanel chessPanel, MouseEvent e)
鼠标点击落子事件处理，chessPanel是已实例化的棋盘面板对象，e是鼠标事件

测试类Test
Test类是程序的入口，提供了主函数，其主要负责实例化视图类View对象，Test类的设计如图5所示。

对象
以四个对象为例，画出对象图，每个图中第一格是对象名：类名，第二格是对象拥有的属性，对象的设计如图6所示。

对象之间的关系
view对象是视图类的实例，chessPanel是棋盘类的实例，pos是位置实体类的实例，chess是控制器类的实例。可以说view是游戏的控制中枢，负责调度chessPanel和chess；chessPanel负责游戏视图；chess是负责游戏逻辑；pos表示一个位置，可以使用Location的集合来保存棋盘的状态。

主要方法的实现

实现原理
我们时常会想，五子棋AI是怎么确定下在哪个位置上的，以下分析一下实现的原理。玩家落子后会形成一个局势，在该局势下AI依次为每个空位打分，得分最高的位置就是AI落子的位置。
问题一：空位那么多，遍历加上计算的开销可不小，那么怎么提高效率？
问题二：怎么为空位打分？

问题一解决：按照原理，每当玩家落子后AI需要遍历所有空位为其打分，其实有很多空位是可以直接排除掉的，每次都要计算一些无用的空位，所以在时间上就造成了浪费。玩过五子棋的人都知道，除第一手棋外，我们的棋子一般下到其他棋子的附近，也就是说那些远离棋子的空位是不需要考虑的，只有那些在非空位附近的位置才是需要考虑的，那么怎么定义“附近”这个概念呢?

设有某非空位置pos1，以pos1为中心呈米字型所能覆盖到的每一个空位pos2都可以称为是pos1附近的位置，整个棋盘所有非空位附近的位置构成一个无重复的集合称为可行位置集合。

从图中可以看到，AI只需要搜索与非空位附近的位置，减少了很多不必要的搜索、计算，虽然随着棋局的深入这种方法依然需要搜索非常多的位置，但是在这个过程中已经排除掉了不少的位置，运算效率已经有了提升。

问题二解决：为空位打分我们需要定义一张评分表作为评分的标准，假设为某空位pos打分，首先AI在这个位置试探性的放一枚己方棋子，AI为白方。

评分表

五子棋中有连、长连、五连、成五、四、活四、冲四、死四等诸多概念，可以看到在评分表中有几种没有进行考虑，比如跳活三之类的情况暂时不进行判定。至此，我们有了评分表，接下来我们需要定义评估空位的方法。

评估函数
评估函数是一个对单个可行位置评分的方法，比如它对某个可行位置pos进行评估，评估步骤如下：
1）横向扫描
A.以可行位置pos的左侧为中心，向左扫描
如果遇到空格，记录下左侧为空格，停止向左扫描
如果遇到己方棋子，棋子个数加1，继续向左扫描
如果遇到对方棋子，记录下左侧为对方棋子，停止向左扫描
如果已到达最左侧，记录下左侧为墙，停止向左扫描
B.以可行位置pos为中心，向右扫描
如果遇到空格，记录下右侧为空格，停止向右扫描
如果遇到己方棋子，棋子个数加1，继续向右扫描
如果遇到对方棋子，记录下右侧为对方棋子，停止向右扫描
如果已到达最右侧，记录下右侧为墙，停止向右扫描
C.根据棋子个数、评分表为该位置打分，该空位得分score1
2）纵向扫描
扫描纵向上的相连己方棋子个数，根据棋子个数、评分表为该位置打分，该空位得分score2
3）正斜向扫描
扫描正斜向上的相连己方棋子个数，根据棋子个数、评分表为该位置打分，该空位得分score3
4）反斜向扫描
扫描反斜向上的相连己方棋子个数，根据棋子个数、评分表为该位置打分，该空位得分score4
5）对以上四个方位之后可以得到score=score1+score2+score3+score4，我们将总得分作为该空位的评分，这样就能使AI考虑到周围四个方向。
算法效果
AI下的位置就是在所有可行位置中评分结果最高的位置，评分结果最高意味着AI觉得这个位置对自己是最有利的，这个算法效果怎么样呢？ AI是白棋，玩家先手，由图，AI的第6手是个败笔，AI第6手应该封堵黑棋，但是它并没有这个意识，可知此时的AI太脆弱，不具备”防”的意识，只有“攻”的意识。原始算法的效果如图7所示。

AI落子过程分析
以下通过模拟AI分析棋局的方式分析AI第6手为什么不封堵黑棋，并找到改善的方案。
1）玩家执黑，AI执白，首先根据局势找出AI所有可行棋位置

单元格中的分数代表该空位的评分，第五行第三列的空位评分最高，所以AI应该将棋子下到该位置处。通过模拟这个过程可以知道，评估函数在为空位打分时只考虑到了己方的棋子，在比对评分表时并没有考虑对方的局势，所以AI决策出的棋子位置只注重了“攻”，而忽视了“防”。

那么怎么才能平衡两者呢？我想到的方法是“换位思考”，所谓“换位思考”，就是当评估函数对空位打分时，不仅要考虑自己，还要站在对方的角度来看待局势。原算法对空位评分时是以AI白棋的角度评定该空位四个方向上形成的棋型，根据相应棋型给出相应得分aiScore，改进的算法还要以玩家黑棋的角度对空位评分，计算出得分playerScore，该空位的得分为score=aiScore+playerScore。

算法改进后效果
假设刚才的棋局进行到了第6手，轮到AI执棋，我们用改进的算法分析一下AI应该落子的位置

可知，此时第3行3列和3行7列的单元格评分最高，所以AI会在两个位置上随机选取一个，不管AI选择哪个位置，都将有效的阻止黑棋的进攻，所以说，目前AI已经具备了攻击和防守的能力。

关键功能实现

窗口布局
窗口布局由View类来控制，主要分为两部分：顶部的工具条、*的棋盘面板。工具条有两个Action：重开一局、玩家先手，分别设置棋盘初始化以及哪位玩家先手，窗口布局如图8所示。

1）添加工具条以及棋盘

//初始化棋盘面板以及添加
chessPanel = new ChessPanel();
frame.add(chessPanel);
// 顶部工具栏
JToolBar bar = new JToolBar();//创建工具栏
frame.add(bar, BorderLayout.NORTH);//添加
bar.setBorderPainted(false);//设置工具栏不画边框

2）添加Action至工具条

Icon icon = new ImageIcon(View.class.getResource("/image/restart.png"));//Icon
JButton restartAction = new JButton("重开一局", icon);//Action
restartAction.addActionListener(new ActionListener() {
    @Override
    public void actionPerformed(ActionEvent e) {
        restartBoard();//重开棋局
    }
});
bar.add(restartAction);//添加Action

3）鼠标事件

//为棋盘面板设置鼠标监听事件
        chessPanel.addMouseListener(new MouseAdapter() {
            @Override
            public void mouseClicked(MouseEvent e) {
                showChess(chessPanel, e);
            }
        });

在showChess方法中我们要执行的是以下几件事情：
根据鼠标点击位置计算出棋盘上的行列值
调用chess对象使玩家在逻辑上落子，调用chessPanel使玩家在视图上落子
chess对棋盘扫描判定玩家是否获胜，如果获胜则提示并重开棋局，如果未获胜，继续执行
chess对棋盘扫描并对每个可行的空位评分，选取一个得分最高的位置，调用chess对象使AI在逻辑上落子，调用chessPanel使AI在视图上落子
ches`对棋盘扫描判定AI是否获胜，如果获胜则提示并重开棋局，如果未获胜，继续执行
之后继续由玩家点击鼠标，回到第一步。

控制器的实现
控制器是整个程序最为核心的一个类，它有多达15个方法，实现了对整个棋局逻辑的控制以及分析。

以3.1的实现原理为依据，AI分析局势先调用getAllMayLocation()方法获取可行的位置集合，然后对每个空位调用getScore(int x, int y)方法打分，打分的时候需要考虑四个方向以及自己、对方两个角色，打分的步骤是先模拟落子，然后以该点为中心进行四个方向上的扫描，获取每个方向上的棋型，然后调用
getScoreBySituation(int count1, int leftStatus, int rightStatus)方法打分，这个方法就是评分表，它对应着3.1中实现原理的评分表。评分表的好与坏直接关系着AI的智能性，这里我只是大概给了评分表的值，细节没有再调。
以下给出一个局势评估的函数，更多的代码见附录。

//局势评估函数，评估该点的得分
public int getScore(int x, int y) {
    //使用换位思考思想
    //以己方棋子和对方棋子模拟落子计算分数和
    int xScore = getXScore(x, y, 1) + getXScore(x, y, 2);
    int yScore = getYScore(x, y, 1) + getYScore(x, y, 2);
    int skewScore1 = getSkewScore1(x, y, 1) + getSkewScore1(x, y, 2);
    int skewScore2 = getSkewScore2(x, y, 1) + getSkewScore2(x, y, 2);
    return xScore + yScore + skewScore1 + skewScore2;
}

棋盘的实现
棋盘的绘制与棋子的绘制都比较简单，为了实现落子操作，我们需要使用一个集合保存棋盘的状态，用Loction保存每个位置的信息，重绘时遍历集合绘制棋子。比较麻烦的一点是绘制棋子上边的数字，这个数字是用来记录棋子是第几手下的，棋盘上有黑棋、白棋，那么棋子上的数字颜色也应该是两种，以下代码中string就是要画的字符串，核心代码如下：

FontMetrics metrics=g.getFontMetrics();
int ascent = metrics.getAscent();
int descent = metrics.getDescent();
if(location.getPlayer()==Chess.first) g.setColor(Color.white);
else g.setColor(Color.black); //设置棋子颜色
g.drawString(string,margin + location.getY() * row-metrics.stringWidth(string)/2,margin + location.getX() * row-(ascent+descent)/2+ascent);

位置实体类实现
这个类是个实体类，只有四个属性以及setter、getter方法以及两参、三参、四参构造方法，封装的是一个位置实体类。

运行结果
人获胜如图9所示

机器获胜如图10所示

问题分析
出现的问题主要有三个：
问题一：评分表的值怎么设定
问题二：机器先手这个功能怎么实现
问题三：棋子上的数字字符串怎么居中

对于问题一：我觉得这个是靠经验吧，我先根据各个棋型的重要性给一个大致的分数，然后再慢慢调试，这样的结果可能不是最优的，但是基本可以用了。

对于问题二：机器先手是指机器需要先决策第一手棋的位置，所以Chess需要提供一个start()方法返回第一个位置，因为此时棋盘上没有棋子，所以AI分析后也不会有结果，我就直接把中心的点给返回了作为AI第一步棋的位置。

对于问题三：首先在绘制棋子的时候我们可以知道棋子要绘制在第几行第几列，然后根据这个行列值计算出棋子所在的圆心位置，字符串的横坐标=圆心的横坐标-字符串的宽度/2，字符串的高度=圆心的纵坐标-字符串的高度/2。
横坐标=圆心横坐标-metrics.stringWidth(string)/2
纵坐标=圆心纵坐标-(ascent+descent)/2+ascent

总结与致谢

到目前，课程设计彻底实现完成，在论文中，因为篇幅原因并没有写清楚功能的实现代码，但是原理都说清楚了，全部的代码见附录。上一年就想实现这个五子棋，但是尝试了一段时间不知道怎么让机器能够分析，以前我是通过一种情况一种情况的判断，最后写了六七百行连封堵的能力都没达到，这次使用的是评分的方法，比较简单并且棋力还算可以。

网上关于五子棋AI的资料我也看的不少，基本都是生成一棵固定深度的博弈树，博弈树的偶数层代表先手的玩家的决策行为，奇数层代表另一方玩家的决策行为，使用极大极小搜索算法对几步之内的局势遍历，每条路径都是一个局势，每个结点都会有一个评分，不管对手怎么下棋，AI只需要尽可能的往得分高的那条路径上就可以了，但是棋盘上有225个交叉点，仅仅第二层就会有225个分叉，第三层有225*2个分叉，不得不说计算量太大了，对AI来说，仅仅预测三步的计算量都是非常大的。所以要用到alpha-β剪枝提高搜索效率。

我用到的不是这个方法，本论文提到的方式只是对空位评分，仅仅思考一步，并且因为在分析局势的时候并没有对哪一方有偏袒（双方的权值都为1），所以AI挑选的位置可能对自己来说不是最优的，但对双方来说都是最优的。如果想让AI棋力增加，可以让它多思考一会，当AI决策出的位置有多个时，不要随机选择一个，可以让AI模拟对手落子，然后AI再模拟落子，最后计算几步之后的总得分，得分高者说明几步之后这个位置还是有优势的。