一种基于改进权重的黑白棋AI的设计与实现

徐刚 翟梦姣

摘要：本文基于改进权重设计并实现了一个黑白棋的人工智能程序，系统可以设置计算层数，经测试，程序效果较好。

关键词：黑白棋;AI;设计与实现

中图分类号：TP18   文献标识码：A   文章编号：1672-9129（2020）04-0054-02

Abstract： In this paper， based on the improved weight design and implementation of a black and white ai program， the system can be set to calculate the number of layers， through testing， the program effect is better.

Key words：Black and white; AI; Design and Implementation

前言：黑白棋，又叫翻转棋（Reversi）、奥赛罗棋（Othello）等。近年来，人工智能是重要的研究领域之一。研究黑白棋的AI有助于了解人类只能行为。网上已有较多黑白棋的AI程序。经过测试，笔者发现网上常见的黑白棋棋盘每个格子的权重如果做一定程度的调整，比如，适当降低四个角的格子的权重，且适当增加四条边每个格子的权重，那么有助于提升黑白棋AI的水平。接下来的部分笔者将详述该系统的需求，设计和实现。

1 系统需求和设计目标

系统可以自动画出黑白棋的棋盘，供双方落子，并实时显示双方的棋子数量，是否分出胜负和胜负关系，以及接下来该哪一方落子。当用鼠标点击棋盘某个格子时，需要做判断。如果棋盘已满，或者接下来双方都没有可以下子的格子，则根据双方的棋子数量自动判断胜负关系并显示出来;如果上个条件不满足且某一方落子后，并不能导致另一方的任何棋子被吃掉，则落子无效，仍有该方走棋;如果上述两个条件均不满足且某一方落子后，另一方没有可以落子的格子，则由某一方继续走棋;如果上述几个条件均不满足且某一方落子后可以导致另一份某些棋子被吃掉，则换另一方走棋。系统AI需要根据棋盘每个格子的权重，自动计算当时系统方的权重值和玩家方的权重值。首先，遍历接下来若干步双方所有可能的落子顺序;然后，计算每一种可能后系统方的权重值;之后，选出权重值最大的一种然后落子并等待玩家方的下一步走棋;最后依次类推，直到分出胜负。系统AI需要根据棋盘每个格子的权重，自动计算当时系统方的权重值和玩家方的权重值。首先，遍历接下来若干步双方所有可能的落子顺序;然后，计算每一种可能后系统方的权重值;之后，选出权重值最大的一种然后落子并等待玩家方的下一步走棋;最后依次类推，直到分出胜负。此外，系统还要允许用户设置计算层数，并根据计算层数计算胜率最高的点。同时，允许用户在游戏进行中随时改变系统AI控制哪一方的棋子，并作出对应的操作。

2 系统主要功能实现

本系统使用C#程序设计语言，在Visual Studio 2010软件下编译运行通过。系统为该软件下的Windows窗体应用程序。程序要需要若干个Label控件用于显示黑方棋子数量、白方棋子数量、接下来该何方走棋;使用一个GroupBox控件和三个RadioButton控件来设置玩家为黑棋，或白棋，或两方都是玩家;使用一个TextBox控件来设置AI搜索层数，层数越多，AI越智能，但是消耗系统资源较大。使用Panel控件当作棋盘，并使用Graphic类的Pen子类画出棋盘和棋子。具体方法是，首先画出一个边框较粗的正方形作为棋盘外框，并占据整个Panel控件，然后在里面画出等距的7条竖线和7条横线，之后在中心的四个格子里以某对角两格作为一种颜色画出黑色棋子，另一个对角两格画出白色棋子，最后等待玩家用鼠标点击棋盘某格，根据情况画出棋子。接下来以玩家为黑棋为例，详述整个系统AI的实现;当玩家为白棋时则反之;如果两方都是玩家只需判断落子是否已经分出胜负和是否落子有效即可[1-2]。

系统首先等待玩家落子，并建立两个8行8列的二维整型数组代表棋盘落子情况，其中1代表黑棋，-1代表白棋，0代表该位置没有棋子，第一个数组代表棋盘的实时状态，第二个数组作代表临时棋盘以作判断落子是否有效使用。如果鼠标点击了Panel控件，则触发其MouseDown事件，如果鼠标点击了棋盘的横线、竖线或已有的落子点时，则其为无效落子，系统什么都不做并继续等待玩家落子;如果点击到了其他部分，则根据规则判断是否可以导致系统方丢子，具体方法是：（1）把新的落子赋值到第二个数组中;（2）判断该子上、下、左、右、左上、左下、右上和右下八个方向行进一格是否有对方棋子，如果都没有对方棋子则落子无效，系统继续等待玩家落子，并把第二个数组恢复到之前状态;（3）如果有对方棋子，则继续向该方向搜索，直到找到本方棋子为止，如果八个方向都没有本方棋子，则该落子仍为无效落子，系统继续等待玩家落子，并把第二个数组恢复到之前状态;（4）如果有方向能找到本方落子，则其为有效落子。之后把此方向落子点和找到的本方棋子间的所有对方棋子的值-1赋值为本方棋子的值1，并根据第二个数组在棋盘中重新画出每个格子新的棋子，并把第二个数组的值赋值到第一个数组，最后重新计算其中1和-1的数量，并赋值给相应的Label控件的Text值。然后判断是否分出胜负。具体方法是：（1）先判断棋盘是否全是某方棋子，即判断第一个数组是否全是0和1，或者全是0和-1，如果是，则分出了胜负，并把相应Label控件的Text值改为某方胜;（2）判断棋盘是否走满，即判断第一个数组是否有0值，如果没有即为走满，并统计双方棋子数量，即计算其中1和-1的数量，并赋值给相应的Label控件的Text值，然后判断哪一方的数量更多，并把哪方胜出或平手的信息赋值给相应的Label控件的Text值。（3）如果没有分出胜负，则继续落子。之后判断是否仍该本方走棋。方法是：（1）当一方落子后，为有效落子，未分出胜负时，按照之前的方法，用另一方的棋子遍历棋盘剩余所有空位，即找出第一個数组中，值为0的格。并将其赋值为另一方的棋子对应的值，然后判断其是否为有效落子;（2）如果没有有效落子，则还由之前一方继续落子;（3）重复上一步，直到另一方有有效落子为止。

对于电脑AI的算法使用递归算法。具体方法为：（1）如果计算层数为一层时的胜率最高的点，即遍历所有可落子的点，然后计算之后AI的总权重值，求助让AI权重值最大的点。在程序中，可以跟据第一个二维数组，遍历其中数组为0的点，并按照上文方法判断有效点和求出落子后的棋盘对应的二维数组，将每种情况的最大权重值和对应的索引值存入临时变量，然后用冒泡法求出权重最大的点，并使用Graphic类的子类Pen根据索引值画出权重值最大的点和新的棋盘的棋子情况，最后仍要对是否分出胜负和是否仍由之前一方继续落子做出判断并进行相应操作;（2）如果计算层数不为一层。比如为N层，则先找出所有落子方和对手方各落一个子的情况。在程序中，可以按照上文方法找寻落子方的落一字的所有有效点，然后在找到的所有情况下，按照同样方法找出另一方接下来的所有有效点，期间可能要不断申请多个二维数组。之后的问题即求出计算层数为N-1层时，总权重值最大的点和对应的索引，此时可由递归函数求得。得出胜率最高点后也需要判断是否分出胜负和是否仍由之前一方继续落子做出判断并进行相应操作。考虑到目前计算机的内存足够大，足够存储多个二维数组，则该算法不用考虑内存溢出问题。经过测试，笔者给出的各个格子的权重值数组，左上角16位依次为50，25，20，15，25，25，15，10，20，15，15，5，15，10，05，0。其余48位与此角各值呈中心对称。考虑到玩家可能在游戏过程中，可能会临时改变AI和玩家的棋子，即在游戏中，玩家点击了相应RadioButton控件，此时根据该控件的CheckedChanged事件是否触发相应的来判断是否改变用AI计算另一方接下来的胜率最高的点并作出相应操作。在测试中，还需要两个TextBox控件和两个Label控件，其中两个TextBox控件用于存放目前棋盘对应的二维数组和接下来计算层数为一层时，落子到最优点后的棋盘对应情况，两个Label控件用于实时显示黑白双方的权重值[3]。

3 系统测试

测试计算机的CPU为AMD FX-8350，内存为16GB，操作系统为Windows 7 x64 SP1。系统运行良好，当计算层数达到12层或以上时，一般玩家难以胜过系统AI。当计算层数达到20层或以上时，计算机运行有明显的延迟。

4 小结

本文根据改进权重的AI，设计并实现了一个黑白棋人工智能程序。系统效果较好。但是还系统还有很多需要改进和完善的地方。比如：程序界面的美观性，棋盘和棋子的颜色、样式，落子的效果等。下一步的重点是对该系统做出优化，减少系统资源占用，比如根据之前的计算创造出棋谱，以及创新出新的占用资源少，并且胜率更高的算法。

参考文献：

[1]美兰多夫，等著.VisualStudio2010高级编程[M].北京：清华大学出版社.2012.

[2]本杰明·帕金斯，等著.C#入门经典[M].北京：清华大学出版社.2019.

[3]王喆.深度学习推荐系统[M].北京：电子工业出版社.2020.

作者簡介：徐刚（1985-），硕士，研究方向：计算机技术和经济分析。