五子棋AI算法
前言：
坐标西安，写于疫情封城期间。改进了之前写的基于极大极小值策略AI五子棋游戏，是用java实现的，采用了java老旧的jframe窗体和绘图类。写好之后整理成了这篇博客。
游戏采用了春物二次元风格，内置彩羽语音，强度的话还不错，不好下赢，防守为主。
文章中的代码部分并不完整，只是摘出了主要部分说明思路，完整代码可以到文末链接处下载。悔棋和认输功能没有去写
目录：
1.五子棋下棋功能的实现
1.1五子棋棋盘的绘制：
五子棋的绘制采用的是java古老的JFrame窗体及其绘图类实现的。
首先棋盘，图片背景等一些列元素都要绘制到JFrame窗体当中，在网上搜集合适的背景图片，和棋盘图片，并将图片进行编辑组合成我们想要的游戏界面。
利用java的绘图类将图片绘制到窗体中，利用二维数组存储棋盘的每一个落子点的位置。这个需要通过一些计算来获取对应的棋盘上的坐标点x，y和二维数组元素i，j之间的函数关系。计算中需要通过使用java中的鼠标监听器来辅助获取棋盘上像素坐标的位置。
绘制棋盘的代码：
public void paint(Graphics g) {
int i,j,k;
int x,y;
//采用双缓冲技术防止屏幕闪烁
BufferedImage bi= new BufferedImage(height,width,BufferedImage.TYPE_INT_ARGB);
Graphics g2=bi.createGraphics();//g2是bi缓冲层的画笔
//先把背景绘制出来
g.drawImage(ChessBackground,10,10,this);
//绘制棋盘图片到缓冲层
g2.drawImage(ChessBoard,10,15,this);
//设置样式
g.setFont(new Font("宋体",0,25));
g.setColor(Color.RED);
//设定round==0的时候是黑方的回合，round==1的时候是白方的回合
if(round==0) g.drawString("黑方回合",676,60);
else g.drawString("白方回合",676,60);
//在棋盘上把所有棋子都绘制出来，先绘制到缓冲层的棋盘上，全部绘制好之后再一起绘制到背景
for(i=0;i<19;i++)
for(j=0;j<19;j++)
{
if(chess[i][j]==1)//绘制黑子
{
x= (int) (35+(float)i*(float)((float)610/(float)18));
y= (int) (44+(float)j*(float)((float)586/(float)18));
g2.setColor(Color.BLACK);
g2.fillOval(x-14,y-14,28,28);
}
if(chess[i][j]==2)//绘制白子
{
x= (int) (35+(float)i*(float)((float)610/(float)18));
y= (int) (44+(float)j*(float)((float)586/(float)18));
g2.setColor(Color.WHITE);
g2.fillOval(x-14,y-14,28,28);
g2.setColor(Color.BLACK);
g2.drawOval(x-14,y-14,28,28);
}
}
//绘制缓冲层到窗体
g.drawImage(bi,0,0,this);
}
1.2落子功能的实现
利用鼠标监听器的点击监听功能来获得落子的坐标位置，并换算成在二维数组中的位置，将落子的位置记录在二维数组中，黑棋用1表示，白棋用2表示。
paint()绘图函数中，每次绘图时遍历二维数组，如果在一个位置上值是1就在棋盘上的对应位置绘制黑棋，如果值是2就在对应位置绘制白棋。
来展示一下绘制的棋盘：
1.3棋局输赢的判断
最原始的想法： 我们遍历真个棋盘，查找每行每列以及斜线上有没有连成五子的情况。
这样的想法虽然简单，但是效率却太慢，假如棋盘的长度是n，那么每次遍历整个棋盘的时间复杂度是O(n^2)，在实际下棋的过程中可能会存在一定延迟。
改进的思路： 每次改变输赢情况的其实都是最新下的这一步棋，因为如果别的棋子不在新下的这一步棋的影响范围内，即同行同列同斜线处，那么这些别的棋子是不用去被遍历的，因为这些棋子的状态不会被改变，没有连成五子的可能。所以只要遍历刚才以落子的点为中心的所有行列和对角线，判断有没有黑棋或者白起连成五个子，如果判断是，则宣布黑棋或白旗胜利。
下面是落子功能和输赢判断功能的核心代码：
if(x>=28&&x<=649&&y>=38&&y<=635)//判断点击位置在棋盘范围内
{
//计算落子点在二维数组中的位置
int i=(int)((x-30)*(18.00/610.00)+0.3);
int j=(int)((y-40)*(18.00/586.00)+0.5);
//如果这个点已经有棋子了就返回
if(chess[i][j]!=0) return;
//在该点存入玩家的黑棋，1代表黑棋，2代表白棋
chess[i][j]=1;
//把玩家下的这步棋的位置传给AI
aiPlayer.setTempx(i);
aiPlayer.setTempy(j);
//this.repaint();//重新绘制棋盘
pc.paintImmediately(pc.getBounds());
System.out.println((round+1)+"打分情况为："+ aiPlayer.Evaluate(1));
//更新回合
round+=1;
round%=2;
//根据这一步棋的位置判断输赢的结果
int judgeResult=judgeWin(i,j);
if(judgeResult==0) //0表示任何一方都没有胜利
{
//AI方下棋
p = aiPlayer.play();
chess[p.getX()][p.getY()] = 2;
System.out.println((round+1)+"打分情况为："+ aiPlayer.Evaluate(1));
MusicPlayer mp = new MusicPlayer("music/xianbei.wav", false);
Thread t2 = new Thread(mp);
t2.start();
try {
Thread.currentThread().sleep(600);
} catch (InterruptedException ex) {
ex.printStackTrace();
}
pc.paintImmediately(pc.getBounds());
judgeResult = judgeWin(i, j);
round+=1;
round%=2;
}
if(judgeResult==1)//1表示玩家黑棋胜利
{
MusicPlayer mp2=new MusicPlayer("music/yabai.wav",false);
Thread t=new Thread(mp2);
t.start();
JOptionPane.showMessageDialog(this,"黑棋胜利");
try {
Win(1);//表示玩家获胜
} catch (LineUnavailableException lineUnavailableException) {
lineUnavailableException.printStackTrace();
} catch (UnsupportedAudioFileException unsupportedAudioFileException) {
unsupportedAudioFileException.printStackTrace();
} catch (IOException ioException) {
ioException.printStackTrace();
}
}
if (p!=null&&judgeWin(p.getX(),p.getY())==2)//如果判断AI获胜
{
JOptionPane.showMessageDialog(this,"白棋胜利");
try {
Win(2);//表示AI白棋获胜
} catch (LineUnavailableException lineUnavailableException) {
lineUnavailableException.printStackTrace();
} catch (UnsupportedAudioFileException unsupportedAudioFileException) {
unsupportedAudioFileException.printStackTrace();
} catch (IOException ioException) {
ioException.printStackTrace();
}
}
}
输赢的判断部分调用的judgeWin()方法没有给出，因为实现起来比较简单
2.AI下棋算法的实现
2.1博弈树
博弈树：
博弈树不是一种数据结构，它只用于刻画下棋的选择策略和选择情形。并没有算法会真是构建出这样的树，可以将其理解为一种搜索的过程。
树的根节点表示最终选择的决定，而与根节点所直接相连的儿子节点是下一步可以出现的情况，这些每一个儿子节点又继续向下搜索接下来可能出现的情况或者局面。依次类推展开一棵尽可能包含所有情况的树。这样的过程其实很像一个广度或者深度搜索的过程。
这样的树在下棋的过程中意义是什么？
下棋的过程是双方交替进行的，所以每一层树的搜索展开都应该分别是白棋和黑棋交替进行的：
假如第一层的所有情况是白棋落子位置的所有可能位置
那么第二层的所有情况就是基于上一步白棋落子以后，黑棋的所有可能的落子位置。
第三层则是基于上面两步完成之后，再对白棋下一步所有落子位置的展开。
展开的深度往往是给出限制的，因为展开搜索本身就是一个非常耗时的过程，
假定我们的博弈树有一个限定深度，那么在完成限定深度的搜索之后，我们得到了在搜索深度，也就是规定步数之内的棋盘上所有可能出现的情况了。没错其实规定深度也就是接下来白棋和黑棋加在一起将要走的步数。
下面我们通过一张图来说明这一个过程：
对图稍加解释：从最上面的根节点开始表示该AI下棋，AI走了某一步棋之后会得到根节点的一个儿子节点，AI把可以尝试搜索的位置都试探后就得到了所有儿子节点，而这些每一个儿子节点又表示该玩家进行试探性搜索了，玩家的棋也会重复上面的过程，然后交替到AI进行，直到深度耗尽，则不再交替进行搜索。
当博弈树被完全展开时，我们使用评估函数给每一种叶子节点对应的最终情形打分，并使用极大极小值策略从叶子到树根向上进行选择。
2.2评估函数和打分策略
对任意时刻任意情形下的棋局针对于让AI获胜的角度进行打分的一个函数。
扫描棋局，对出现的不同棋形按照事先规定好的评分标准进行打分。
通过简单的分析，得出局面上出现的棋子有下面这几种情形：
- 五子：给最高分
- 四子活棋 四子单活 四子死棋 ：分数递减
- 三子活棋 三子单活 三子死棋 ：分数递减
- 双子活棋 双子单活 双子死棋： 分数递减
- 单子：不给分
对于这些不同的情形，我们人为地给每一种棋形设置不同地分数作为评估标准。
然后按一定地算法扫描棋盘，根据棋形的打分规则给每一步落子后形成的棋局打分。
如何扫描整个棋局中出现的所有棋形？这是一个很关键的问题
最朴素的算法： 直接遍历整个棋盘，扫描每一个横行竖行，以及所有对角线来确定所有出现的棋形。这样简单的想法会造成O(N^N)的时间代价，显然是不可行的。
改进的算法：以一个棋子为中心，去寻找以它为中心的横向，纵向以及两条对角线上的棋子情况。以下图来进行说明：
假设我们要扫描获得黑棋的所有棋形，那么我们这样来做：
- 首先扫描棋盘，代价是O(N^2)，对于每一给点，如果不是黑棋，那么我们就不去管这个位置了。
- 如果是黑棋，那么我们进行搜索：从横，纵，左对角，右对角四个方向分别去进行扫描。不过这里注意上图画出的搜范围，即每一个方向的扫描，我们只需要在以目标位置为中心，总长度为9的范围内扫描就可以了。因为我们的扫描的棋形最长是5个连在一起的情况，所以无论以中心位置向哪个方向延申，只需要扫描4个长度的位置就可以了。这样一来对每一个位置的扫描时间代价为常数C而已，对所有位置的扫描时间复杂度似乎也只是一个线性递增的过程而已。
- 避免重复扫描的情况：因为上述扫描过程中，同一方向的连续棋子在各自扫描的过程中会重复计算这一方向的棋形。为了避免这一情况，我们考虑：假如该目标棋子不是某一扫描方向上的第一个棋子，那么不需要再以它为中心扫描这一方向的棋形了，因为这一方向上的棋形已经被它前面的棋子扫描过了。
下面是判断棋子形状并根据形状打分的功能函数：
//判断棋形函数，返回当前棋局的打分情况
public long JudgeChessFrom(int flag,int x,int y)
{
int i,j,k1 = 0,k2=0;
long value=0;
int count=1;
int status;
//判断横向棋子个数
if(y==0||chess[x][y-1]!=flag) {
for (j = (y + 1 <= 18 ? y + 1 : 18); j <= ((y + 4 < 19) ? y + 4 : 18); j++) {
if (chess[x][j] == flag) count++;
else break;
}
if (j <= 18 && chess[x][j] == 0) k1 = 0;//k为0表示活棋
else k1 = 1;
for (j = (y - 1 >= 0 ? y - 1 : 0); j >= (y - 4 >= 0 ? y - 4 : 0); j--) {
if (chess[x][j] == flag) count++;
else break;
}
if (j >= 0 && chess[x][j] == 0) k2 = 0;
else k2 = 1;
//扫描完毕，判定棋子状态并获取分数
if (count >= 5) return 100000000000000000l;
if (k1 == 0 && k2 == 0) status = 0;// status 0 表示双活
else if (k1 == 0 || k2 == 0) status = 1;// status 1表示单活
else status = 2;// status 2表示死棋
value += GetScore(count, status);//根据连在一起的棋子数量和状态获取评分
}
//判断纵向
count=1;
if(x==0||chess[x-1][y]!=flag)
{
for (i = (x + 1 <= 18 ? x + 1 : 18); i <= ((x + 4 < 19) ? x + 4 : 18); i++) {
if (chess[i][y] == flag) count++;
else break;
}
if (i <= 18 && chess[i][y] == 0) k1 = 0;//k为0表示活棋
else k1 = 1;
for (i = (x - 1 >= 0 ? x - 1 : 0); i >= (x - 4 >= 0 ? x - 4 : 0); i--) {
if (chess[i][y] == flag) count++;
else break;
}
if (i >= 0 && chess[i][y] == 0) k2 = 0;//k为0表示活棋
else k2 = 1;
//扫描完毕，判定棋子状态并获取分数
if (count >= 5) return 100000000000000000l;
if (k1 == 0 && k2 == 0) status = 0;
else if (k1 == 0 || k2 == 0) status = 1;
else status = 2;
value += GetScore(count, status);
}
//判断斜向'/'
count =1;
if(x==0||y==18||chess[x-1][y+1]!=flag) {
for (i = (x - 1 >= 0 ? x - 1 : 0), j = (y + 1 <= 18 ? y + 1 : 18); i >= (x - 4 >= 0 ? x - 4 : 0) && j <= ((y + 4 < 19) ? y + 4 : 18); i--, j++) {
if (chess[i][j] == flag) count++;
else break;
}
if (i >= 0 && j <= 18 && chess[i][j] == 0) k1 = 0;
else k1 = 1;
for (i = (x + 1 <= 18 ? x + 1 : 18), j = (y - 1 >= 0 ? y - 1 : 0); i <= ((x + 4 < 19) ? x + 4 : 18) && j >= (y - 4 >= 0 ? y - 4 : 0); i++, j--) {
if (chess[i][j] == flag) count++;
else break;
}
if (i <= 18 && j >= 0 && chess[i][j] == 0) k2 = 0;
else k2 = 1;
if (count >= 5) return 100000000000000000l;
if (k1 == 0 && k2 == 0) status = 0;
else if (k1 == 0 || k2 == 0) status = 1;
else status = 2;
value += GetScore(count, status);
}
//判断斜向'\'
count =1;
if(x==0||y==0||chess[x-1][y-1]!=flag) {
for (i = (x - 1 >= 0 ? x - 1 : 0), j = (y - 1 >= 0 ? y - 1 : 0); i >= (x - 4 >= 0 ? x - 4 : 0) && j >= ((y - 4 >= 0) ? y - 4 : 0); i--, j--) {
if (chess[i][j] == flag) count++;
else break;
}
if (i >= 0 && j >= 0 && chess[i][j] == 0) k1 = 0;
else k1 = 1;
for (i = (x + 1 <= 18 ? x + 1 : 18), j = (y + 1 <= 18 ? y + 1 : 18); i <= ((x + 4 < 19) ? x + 4 : 18) && j <= ((y + 4 < 19) ? y + 4 : 18); i++, j++) {
if (chess[i][j] == flag) count++;
else break;
}
if (i <= 18 && j <= 18 && chess[i][j] == 0) k2 = 0;
else k2 = 1;
if (count >= 5) return 100000000000000000l;
if (k1 == 0 && k2 == 0) status = 0;
else if (k1 == 0 || k2 == 0) status = 1;
else status = 2;
value += GetScore(count, status);
}
return value;
}
至此我们获得了扫描整个棋盘中某一方的棋形的算法，下面我们要根据这些棋形给局面打分，来代表棋局在朝有利于谁的局面进行，我们假设棋局给出的分数越大，则玩家越有可能胜利，而分数越小，则AI越有可能胜利。
如何给这些不同的棋形设置较为合理的分数
不同棋形之间的分数，我们要依据自己的判断人为给出，我给出的评分标准并不一定很合理，但是我认为越接近胜利的棋形，例如5子连棋，4子活棋，4子单活，3子活棋等这些很有利的棋应该与别的棋拉开数量级差距的分数，而他们之间的分数也应该尽量大而不容易产生误判的情况。例如不能因为一步棋可以产生多个四子而舍弃了产生五子的情况。下面是我给出的打分标准：
public long GetScore(int count,int status)
{
if(count>=5) return 100000000000000000l;
else if(count==4)
{
if(status==0)
return 1000000000000l;
else if(status==1)
return 100000l;
else return 80000l;
}
else if(count==3)
{
if(status==0)
return 100000l;
else
if(status==1)
return 20l;
else return 10l;
}
else if(count==2)
{
if(status==0)
return 8l;
else if(status==1)
return 1l;
else return 1l;
}
else if(count==1)
return 0l;
else return 0l;
}
2.3极大极小值策略
极大极小值策略：
- 评估函数是针对有利于玩家方获胜的角度打分的，分数越大代表玩家越可能胜利。
- 当电脑进行选择时，一定会选择在所有可走的位置中，会使棋局分数变成最小的那一位置。因为使局面分数越小，玩家就越难胜利。
- 而当玩家在进行选择时，一定会选择在所有可走的位置中，会使棋局分数变成最大的那一位置。因为使局面分数越大，玩家就越容易胜利。
- 极大极小值策略选择位置的过程是在博弈树构建完成后，从叶子向上递归的过程中进行的。
建议再来看一下上面那张图：我们针对极大极小值的决策过程进一步解释这张图：
我们上面说明了，图中这个博弈树的限定深度为3，叶子节点是经过AI下棋，玩家下棋，AI下棋，这样交替三步棋之后出现的所有可能的棋局情况，并且根据情况打出的分数。
极大极小值的决策是要基于叶子节点给出的分数，向上选择，那么首先是AI选择，也就是第三步棋，AI肯定会选择其中分数最小的一步棋，也就是对人类最不利，对自己最有利的。这样一来就确定了每种情况下的第三步棋，并且把分数传递给上一步：现在每种第二步棋下的第三步棋被确定了，我们要继续确定第二步棋：
第二步棋是人类走的，所以我们推断人类最想走哪一步棋：一定是造成局面分数最大的一步棋。上图截出来的分数就是每种第二步棋下完之后可能出现的。那么对于每一个分支下的三步棋，我们只选择其中最大的情况来作为第二步棋的选择。这样一来每种第一步棋下的第二步棋也被确定了。
最后我们来确定第一步棋，也就是AI目前需要决定下的棋根据人类会给出的对于人类最有利的决策中，AI需要从中选出最有利于它的一步，其实这有点像矮子里面挑将军的意思。最终AI会从这三步棋中跳出分数最小的一步，来作为AI的最终决策。
极大极小值总结：
由于是下棋，谁都不希望对方胜利，所以从最终局面往后推的过程中，双方在选择时都会选择最利于自己的一步，然后另一方只能从对方的这些选择中再选出利于自己的一步。这样交替进行的过程就是极大极小值决策的过程，最好的情况往往会被对方抹去，我们只能从剩下的情形里选比较好的。
2.4启发式搜索和剪枝
关于启发式搜索：
我们已经知道，博弈树的展开会是一个接近于O(M^N)这样一个时间消耗，M表示每一层探索的位置，而N表示深度。我们希望去减小M来优化这样的时间消耗，所以采用启发式搜索。
也就是说我们每一次尝试探索的位置肯定没有必要是整个棋盘，而是一个有意义的范围。我们去设想一下这个范围，假如对方下了一步棋，那么这步棋只能影响到一定的范围，这个范围我们称作上一步棋的作用域，也就是以它为中心，9*9的正方形范围。那么我们只要在这个范围内针对它进行防守就可以了。防守的同时在这个区域内壮大自己的力量。所以每一次搜素试探的位置只在上一步棋的作用域内进行，这就是启发式搜索的思想。
关于博弈树的剪枝：
博弈树的剪枝要想讲明白可能得大量画图，我不太会画图，，，
所以可能讲不好这个东西
这里先偷个懒，找来了几个别的博主大佬的文章链接：
https://blog.csdn.net/qq_36336522/article/details/79410913
https://blog.csdn.net/tangchenyi/article/details/22925957
后面如果自己写好了Alpha-Beta剪枝的内容再补到下面
最终版极大极小值博弈策略的代码（加入了剪枝和启发式搜索）：
//AI方判断下一步(极小值)
public Point FindAIMove(int depth,long alpha,long beta)
{
long MinValue=999999,value=0;
int i,j,x = 0,y=0;
Point p=null,BestPoint=null;
for(i=(tempx-4>=0?tempx-4:0);i<=(tempx+4<=18?tempx+4:18);i++)
for(j=(tempy-4>=0?tempy-4:0);j<=(tempy+4<=18?tempy+4:18);j++)
{
if(alpha<=beta)
{
return new Point(x,y,alpha);
}
if(chess[i][j]==0)
{
chess[i][j]=2;
if(depth>1)
{
p=FindHumanMove(depth-1,alpha,beta);
value=p.getValue();
if(value<alpha)
{
alpha=value;
x=i;
y=j;
}
}
else value=5*Evaluate(1)-Evaluate(2);//这个地方的值不一定最合理
if(value<MinValue||BestPoint==null)
{
MinValue=value;
BestPoint=new Point(i,j,MinValue);
}
chess[i][j]=0;
}
}
return BestPoint;
}
//人类方判断下一步(极大值)
public Point FindHumanMove(int depth,long alpha,long beta)
{
long MaxValue=-99999,value=0;
int i,j,x = 0,y=0;
Point p=null,BestPoint=null;
for(i=(tempx-4>=0?tempx-4:0);i<=(tempx+4<=18?tempx+4:18);i++)
for(j=(tempy-4>=0?tempy-4:0);j<=(tempy+4<=18?tempy+4:18);j++)
{
if(alpha<=beta)
{
return new Point(x,y,beta);
}
if(chess[i][j]==0)
{
chess[i][j]=1;
if(depth>1)
{
p=FindAIMove(depth-1,alpha,beta);
value=p.getValue();
if(value>beta)
{
beta=value;
x=i;
y=j;
}
}
else value=5*Evaluate(1)-Evaluate(2);
if(value>MaxValue||BestPoint==null)
{
MaxValue=value;
BestPoint=new Point(i,j,value);
}
chess[i][j]=0;
}
}
return BestPoint;
}
源码下载地址：https://download.csdn.net/download/weixin_45863060/75075053
点击下载
文章到这里基本上就结束了，下面附上几张图：