实际上现在的棋类AI都是采用了效率更高的算法（如蒙特卡洛树搜索）+Deep Learning实现。今天我们只探讨较简单的五子棋AI，大致有两种算法：五元组和博弈树。
Java学习笔记
第一节 Java 类与对象以及继承
第二节 Java 对象的保存和传递
第三节 Java 数组和列表的使用
第四节 Java 五子棋AI博弈树算法
目录
Java学习笔记前言一、HashMap的使用二、获取落子状态三、构建权值表并获取分数四、AI遍历与递归总结前言
五子棋UI界面设计和博弈树的概念在这里不做介绍（参考博客：五子棋人机对战（Java项目）），博主的UI具体效果如下：
我们先来梳理一下五子棋AI的设计流程：二者博弈，就是一场利益争夺战，那么最终结果就看博弈双方谁能够获得最大的价值。那么下棋前计算机需要遍历能够落子的点，然后找到价值最大的落子点。
那么现在又诞生一个问题：如何定义价值最大？
实际上不管是五元组还是博弈树，都需要有一个相应的“价值最大”的评分制度，我们把这个叫做权值表。
例如（只列举部分情况）：
实际上，这就是建立了一种棋子状态与得分的映射关系，我们当然可以用 if - else if 语句来进行加分，也可以利用HashMap来建立这种映射关系。
一、HashMap的使用
HashMap是Java中最常用的集合类框架，也是Java语言中非常典型的数据结构。它的底层实现逻辑以及其特点我们不在本文介绍，现在我们只介绍一下HashMap的使用方法：
首先我们需要创建一个HashMap对象：
HashMap<K, V> hm = new HashMap<>();
显然HashMap创建时有使用到我们上一节介绍的“泛型”。（第三节 Java 数组和列表的使用）
显然，五子棋的权指表需要将其中的 K 定为String，V 定为Integer：
HashMap<String, Integer> hm = new HashMap<>();
之后就是添加权值对。与ArrayList类似，我们只需要用put方法即可添加需要的权值对：
public static void main(String[] args) {HashMap<String, Integer> hm = new HashMap<>();hm.put("yes",1);hm.put("no",0);}
之后使用get方法便可调取到映射：
public static void main(String[] args) {HashMap<String, Integer> hm = new HashMap<>();hm.put("yes",1);hm.put("no",0);String s = "no";int a = hm.get("yes");int b = hm.get(s);System.out.println("a "+a);System.out.println("b "+b);}
a 1
b 0
得益于自动拆箱机制，a和b成功提取到对应Integer值。
二、获取落子状态
学会使用HashMap后，现在我们可以着手获取落子状态了。首先我们可以把棋盘看做是15*15的二维数组，其中每个位置上黑棋为1，白棋为2，无棋为0。
对于博弈树算法，我们只需要计算每次落子时带来的收益，我们可以先假设计算机在一处落子，五子棋的规则表明，一个子可以在四个方向上影响周围子：上——下、左——右、左上——右下、右上——左下。因此我们需要获取的落子状态为落子后在四个方向上棋子的顺序。
这里介绍博主的思路：以水平方向（左——右）为例
public String[] search(String[] SearchArr, byte[][] seat, int X, int Y) {String Evel = "";//保存水平方向排序String Vertical = "";//保存竖直方向排序String LeftCross = "";//保存正斜向排序String RightCross = "";//保存反斜向排序String Evel = "";byte color = 0;int i,j;color = seat[X][Y];//seat数组保存当前棋局状态，类型为byteEvel += seat[X][Y];//保存当前位置棋子颜色//水平方向//向左遍历for(i=X-1,j=Y;i>=0;i--) {if(0 == seat[i][j]) {//判断相邻是否落子break;}else if(seat[i][j] != color) {//判断相邻是否异色Evel = seat[i][j] + Evel;//int、byte等类型会自动转为String类型保存break;}else if(seat[i][j] == color) {Evel = seat[i][j] + Evel;}}//向右遍历for(i=X+1,j=Y;i<NUM;i++) {if(0 == seat[i][j]) {//判断相邻是否落子break;}else if(seat[i][j] != color) {//判断相邻是否落子Evel += seat[i][j];break;}else if(seat[i][j] == color) {Evel += seat[i][j];}//竖直方向 略//左上——右下方向 略//右上——左下方向 略SearchArr[0] = Evel;SearchArr[1] = Vertical;SearchArr[2] = LeftCross;SearchArr[3] = RightCross;return SearchArr;}
之后按照相同的思路，把四个方向的String全部保存即可。
博主的思路比较简单，没有考虑将“0”也保存进棋局，因为这样会使得棋子排序种类特别繁多，构建权值对将成为难题，当然如果考虑更多更全面的情况，AI的水平也会更高。
三、构建权值表并获取分数
public void setHashMap() {hm.put("1", 0);hm.put("2", 0);hm.put("12",2);hm.put("21", 2);hm.put("212",1);hm.put("121", 5);hm.put("11",20);hm.put("22", 20);hm.put("112", 10);hm.put("211", 10);hm.put("122", 10);hm.put("221", 10);hm.put("2112", 5);hm.put("1221", 5);hm.put("111",200);hm.put("222", 200);hm.put("1112",12);hm.put("2221", 12);hm.put("2111",12);hm.put("1222", 12);hm.put("21112",5);hm.put("12221", 5);hm.put("1111",15000);hm.put("2222", 15000);hm.put("21111",120);hm.put("12222", 120);hm.put("11112",120);hm.put("22221", 120);hm.put("211112",5);hm.put("122221", 5);hm.put("11111",50000);hm.put("22222",50000);hm.put("211111",50000);hm.put("122222",50000);hm.put("111112",50000);hm.put("222221",50000);hm.put("2111112",50000);hm.put("1222221",50000);}
权值的设置博主没有仔细研究，权值设定仅供参考。
之后便是撰写getValue函数获取落子价值。
private int getValue(int x, int y) {int value = 0;String[] SearchArr = new String[4];SearchArr = search(SearchArr, seat, x, y);//如果有五连则直接加50000（防止六连或更多连等极端情况）if(SearchArr[0].contains("11111") || SearchArr[0].contains("22222"))value += 50000;else if(SearchArr[1].contains("11111") || SearchArr[1].contains("22222"))value += 50000;else if(SearchArr[2].contains("11111") || SearchArr[2].contains("22222"))value += 50000;else if(SearchArr[3].contains("11111") || SearchArr[3].contains("22222"))value += 50000;else {value += hm.get(SearchArr[0]);value += hm.get(SearchArr[1]);value += hm.get(SearchArr[2]);value += hm.get(SearchArr[3]);}return value;}
四、AI遍历与递归
public int[] doAI(int AIcolor) {int seatValue[][] = new int[NUM][NUM];for(int n=0; n<NUM; n++) {for(int m=0; m<NUM; m++) {if(seat[m][n] != 0) {//检测是否有棋子continue;}seat[m][n] = (byte)AIcolor;//如果没有棋子，假设下棋，并获取价值seatValue[m][n] = getValue(m, n);seat[m][n] = 0;//还原假设的落子}}int maxValue = 0;int X=0,Y=0;for(int n=0;n<NUM;n++) {for(int m=0;m<NUM;m++) {if(maxValue<seatValue[m][n]) {maxValue = seatValue[m][n];X = m;Y = n;}}}int[] bestSeat = {X,Y};return bestSeat;}
显然，这里AI只进行了1步预测，因此获得的落子得分只是估值，可能在几步之内有更大价值的落子点，我们可以在落子之后继续预测对方落子点，以此来获得更加精确的落子估值。这就需要通过递归算法实现，理论上，只要遍历深度足够，我们便能够得到所以落子的准确得分。但实际上遍历次数是随着深度成指数性增长的，我们必须优化算法来舍弃那些一眼就无需遍历的点：
public int[] doAI(int AIcolor, int deep) {int[][] seatValue = new int[NUM][NUM];for(int n=0; n<NUM; n++) {for(int m=0; m<NUM; m++) {if(seat[m][n] != 0) {//检测是否有棋子continue;}int num = 0;//检测周围2格内是否有棋子，若没有则不考虑该落子情况for(int i = (n-2>0? n-2:0);i<NUM && i<n+2;i++)for(int j= (m-2>0? m-2:0);j<NUM && j<m+2;j++)num += seat[i][j];if(0==num) {continue;}seat[m][n] = (byte)AIcolor;//如果没有棋子，假设下棋seatValue[m][n] += getValue(m,n);//获取假设落子后的分数int[] fore = new int[2];if(BLACK==AIcolor) {if(deep>=0)fore = doAI(WHITE, deep-1);//deep不为负则继续预测else fore = doAI(WHITE);//deep为负便不再预测seat[fore[0]][fore[1]] = (byte)WHITE;seatValue[fore[0]][fore[1]] += getValue(fore[0], fore[1]);seat[fore[0]][fore[1]] = 0;}else if(WHITE==AIcolor) {if(deep>=0)fore = doAI(BLACK, deep-1);else fore = doAI(BLACK);seat[fore[0]][fore[1]] = (byte)BLACK;seatValue[fore[0]][fore[1]] += getValue(fore[0], fore[1]);seat[fore[0]][fore[1]] = 0;}seat[m][n] = 0;//还原假设的落子}}int Value = 0;int X=0,Y=0;for(int n=0;n<NUM;n++) {for(int m=0;m<NUM;m++) {if(Value<seatValue[m][n]) {Value = seatValue[m][n];X = m;Y = n;}}}int[] bestSeat = {X,Y};return bestSeat;}
到这里，我们基于博弈树的五子棋AI算法基本完成。
总结
以上就是今天要讲的内容。
实际上，当deep=1时（往后思考3步），每一步计算的时间已经有好几秒了，甚至复杂的情况需要十几秒，这时电脑已经具备了和常人下棋的能力。
当deep=2 时需要的时间已经长得离谱了。读者可以在此基础上继续优化，提高电脑的计算效率。
最后放上源代码以及打包完的exe文件（复盘功能无效）：读者可以自行游玩。
链接：/s/1yxRKxMCmaLhXZ7P0MEAQOg
提取码：fqwu
