Alpha-Beta剪枝极大极小博弈算法-五子棋AI实现

写在最前

蹭着AI 的热度,让我慢慢对 AI 算法有了兴趣,刚刚好因为实训,有机会完成了这个五子棋的 AI 程序,算法基于极大极小博弈树,实现语言为 Java ,如果有兴趣,可访问开源地址: https://github.com/rockzhai/AI-Wuziqi ,如果喜欢,欢迎star或者提出宝贵意见。

另:对于AI算法的这次尝试,很多地方未作深入研究,有些问题尚未顾及到,因而任重道远,这块领域神秘并且富有乐趣,孜孜不倦才是进步之道。

算法核心

关于五子棋玩法不做赘述,相信各位小伙伴都或多或少玩过这个简单的游戏。
对于游戏AI设计,我们引进了一个“权重”想法,通过对上下左右等一个点位的八个方向进行分析,通过各个方向的权重求和的方式获得该点最终的权重值。

当用户和AI进行对弈时:首先我们先建立起博弈树,继而通过估值函数算法计算落棋点的权重值,然后用Alpha-Beta剪枝加快搜索效率,最终取得最终的落棋点。

估值函数设计

  • 首先遍历整个棋盘,如果该点非空,进入该点权重计算
  • 该点向左遍历,出现连续同色的棋子,进行加1,cnt++
  • 向右遍历,出现连续同色的棋子,进行加1,cnt++
  • 若两边无封堵、则权重= cntcnt颜色的值(白:1,黑-1)
  • 若一边出现封堵,则权重= cntcnt颜色的值/4
  • 若两边封堵,则权重=0;
  • 若 cnt 大于等与5,权重为最大值*颜色的值(白:1,黑-1)
  • 总权重是每个点四个方向(行、列、左右对角线)的权重之和

估值函数代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public static int getMark(){
int res=0;
for(int i=1;i<=size;++i){
for(int j=1;j<=size;++j){
if(chessBoard[i][j]!=0){
// 行
boolean flag1=false,flag2=false;
int x=j,y=i;
int cnt=1;
int col=x,row=y;
while(--col>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;
if(col>0 && chessBoard[row][col]==0) flag1=true;
col=x;row=y;
while(++col<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;
if(col<=size && chessBoard[row][col]==0) flag2=true;
if(flag1 && flag2)
res+=chessBoard[i][j]*cnt*cnt;
else if(flag1 || flag2) res+=chessBoard[i][j]*cnt*cnt/4;
if(cnt>=5) res=MAXN*chessBoard[i][j];
// 列
col=x;row=y;
cnt=1;flag1=false;flag2=false;
while(--row>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;
if(row>0 && chessBoard[row][col]==0) flag1=true;
col=x;row=y;
while(++row<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;
if(row<=size && chessBoard[row][col]==0) flag2=true;
if(flag1 && flag2)
res+=chessBoard[i][j]*cnt*cnt;
else if(flag1 || flag2)
res+=chessBoard[i][j]*cnt*cnt/4;
if(cnt>=5) res=MAXN*chessBoard[i][j];
// 左对角线
col=x;row=y;
cnt=1;flag1=false;flag2=false;
while(--col>0 && --row>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;
if(col>0 && row>0 && chessBoard[row][col]==0) flag1=true;
col=x;row=y;
while(++col<=size && ++row<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;
if(col<=size && row<=size && chessBoard[row][col]==0) flag2=true;
if(flag1 && flag2)
res+=chessBoard[i][j]*cnt*cnt;
else if(flag1 || flag2) res+=chessBoard[i][j]*cnt*cnt/4;
if(cnt>=5) res=MAXN*chessBoard[i][j];
// 右对角线
col=x;row=y;
cnt=1;flag1=false;flag2=false;
while(++row<=size && --col>0 && chessBoard[row][col]==chessBoard[y][x]) ++cnt;
if(row<=size && col>0 && chessBoard[row][col]==0) flag1=true;
col=x;row=y;
while(--row>0 && ++col<=size && chessBoard[row][col]==chessBoard[y][x]) ++cnt;
if(row>0 && col<=size && chessBoard[i][j]==0) flag2=true;
if(flag1 && flag2)
res+=chessBoard[i][j]*cnt*cnt;
else if(flag1 || flag2) res+=chessBoard[i][j]*cnt*cnt/4;
if(cnt>=5) res=MAXN*chessBoard[i][j];
}
}
}
return res;
}

Alpha-Beta剪枝+博弈树

极大极小博弈算法:

该算法是考虑双方博弈若干步之后,从可能的选择中选择一个相对好的选择,即在有限的搜索深度范围内进行求解。
规定如下:

  1. MAX 和 MIN 代表博弈双
  2. f(p)表示状态评估得分
  3. 有利于MAX: f(p) > 0;有利于MIN: f(p) < 0;
  4. 零和博弈

基本思想:

  • MIN走步时,MAX要考虑最坏的情况 ( f(p)最小 )
  • MAX走步时,MAX要考虑最好的情况( f(p)最大 )

程序中我们设置为 AI 先手,则博弈树的第一层便是电脑所有的可能走法,第二层就是玩家的可能走法,根据上述的原则,我们设计的博弈树将每一个结点展开,通过递归遍历,这时候问题便来了,我们如果才能知道哪一个分支才是最优的,这时候我们就用到了上述的估值函数,根据分数的正负和大小确定对玩家和 AI 的利弊程度。此时我们便用到了上述算法的基本思想,在电脑走棋时,在 MAX 层选出高分,玩家奏起,在 MIN 层选出低分。故而完成了极大极小博弈树的逻辑设定。

采用 Alpha-Beta 剪枝

由于在上述的博弈树中,很多结点其实是“没有价值”的,所以无论是否遍历这些结点的数据,对最终的结果都毫无影响,进而我们选择 Alpha-Beta 剪枝剪掉那些没用的分支,当然,你也可以计算,如果不剪枝,那么一个简单的五子棋 AI 算法将会耗费多大的电脑资源,在此不做赘述,

剪枝原理

剪枝算法的基本依据是:棋手不会做出对自己不利的选择。
依据这个前提,如果一个节点明显是不利于自己的节点,那么就可以直接剪掉这个节点。

前面说到,AI会在MAX层分数最大的结点,而玩家会在MIN层选择最小结点,那么便可分析如下:

在MAX层,假设当前层已经搜索到一个最大值 X, 如果发现下一个节点的下一层MIN会产生一个比X还小的值,那么就直接剪掉此节点。

简单来说,就是AI发现这一步是对玩家更有利的,所以不会走这一步。

在MIN层,假设当前层已经搜索到一个最小值 Y, 如果发现下一个节点的下一层MIN层会产生一个比Y还大的值,那么就直接剪掉此节点。

其实MAX和MIN层道理相似。

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// alpha beta dfs
private static void dfs(int deep,Node root,int alpha,int beta,Point p){
if(deep==searchDeep){
root.mark=getMark();
// System.out.printf("%d\t%d\t%d\n",p.x,p.y,root.mark);
return;
}
ArrayList<Point> judgeSet=new ArrayList<Point>();
Iterator it=toJudge.iterator();
while(it.hasNext()){
Point now=new Point((Point)it.next());
judgeSet.add(now);
}
it=judgeSet.iterator();
while(it.hasNext()){
Point now=new Point((Point)it.next());
Node node=new Node();
node.setPoint(now);
root.addChild(node);
boolean flag=toJudge.contains(now);
chessBoard[now.y][now.x]=((deep&1)==1)?-1:1;
if(isEnd(now.x,now.y)){
root.bestChild=node;
root.mark=MAXN*chessBoard[now.y][now.x];
chessBoard[now.y][now.x]=0;
return;
}
boolean flags[]=new boolean[8]; //标记回溯时要不要删掉
Arrays.fill(flags,true);
for(int i=0;i<8;++i){
Point next=new Point(now.x+dc[i],now.y+dr[i]);
if(1<=now.x+dc[i] && now.x+dc[i]<=size && 1<=now.y+dr[i] && now.y+dr[i]<=size && chessBoard[next.y][next.x]==0){
if(!toJudge.contains(next)){
toJudge.add(next);
}
else flags[i]=false;
}
}
if(flag)
toJudge.remove(now);
dfs(deep+1,root.getLastChild(),alpha,beta,now);
chessBoard[now.y][now.x]=0;
if(flag)
toJudge.add(now);
for(int i=0;i<8;++i)
if(flags[i])
toJudge.remove(new Point(now.x+dc[i],now.y+dr[i]));
// alpha beta剪枝
// min层
if((deep&1)==1){
if(root.bestChild==null || root.getLastChild().mark<root.bestChild.mark){
root.bestChild=root.getLastChild();
root.mark=root.bestChild.mark;
if(root.mark<=MINN)
root.mark+=deep;
beta=Math.min(root.mark,beta);
}
if(root.mark<=alpha)
return;
}
// max层
else{
if(root.bestChild==null || root.getLastChild().mark>root.bestChild.mark){
root.bestChild=root.getLastChild();
root.mark=root.bestChild.mark;
if(root.mark==MAXN)
root.mark-=deep;
alpha=Math.max(root.mark,alpha);
}
if(root.mark>=beta)
return;
}
}
// if(deep==0) System.out.printf("******************************************\n");
}

小功能

保存游戏截图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 保存文件image
public void save(String filename) throws IOException {
BufferedImage image2 = getImage();
// 如果缩放了,恢复再保存
if (SAVE_SCALED_IMAGES && currentZoom != 1) {
BufferedImage zoomedImage = new BufferedImage(width * currentZoom, height * currentZoom, image.getType());
Graphics2D g = (Graphics2D) zoomedImage.getGraphics();
g.setColor(Color.BLACK);
if (PRETTY) {
g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
}
g.scale(currentZoom, currentZoom);
g.drawImage(image2, 0, 0, imagePanel);
image2 = zoomedImage;
}
int lastDot = filename.lastIndexOf(".");
String extension = filename.substring(lastDot + 1);
ImageIO.write(image2, extension, new File(filename));
}

获取鼠标实时坐标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 实现鼠标事件接口
class MyMouseEvent implements MouseListener{
public void mouseClicked(MouseEvent e){
int x=round(e.getX()),y=round(e.getY());
if(x>=45 && x<=675 && y>=45 && y<=675 && Ai.chessBoard[y/45][x/45]==0 && Ai.isBlack==false){
Ai.putChess(x,y);
if(!Ai.isFinished){
Ai.isBlack=true;
Ai.myAI();
}
Ai.isFinished=false;
}
}
// 得到鼠标点击点附近的棋盘精准点
public static int round(int x){
return (x%45<22)?x/45*45:x/45*45+45;
}
public void mouseExited(MouseEvent e){}
public void mouseEntered(MouseEvent e){}
public void mouseReleased(MouseEvent e){}
public void mousePressed(MouseEvent e){}
}

棋盘的放大缩小

……
欢迎访问开源链接https://github.com/rockzhai/AI-Wuziqi ,代码都在里面。

参考文章及开源项目

一个国际象棋AI的实现
五子棋AI算法系列
开发过程中在网上发现一开源项目,程序中有多处参考其程序,时间过去略久,设备更换,未能找到对的链接,在此特别感谢其开源精神,作为感谢,会在开源的路上越走越远,致敬。

如果后续发现会附在文章的最后,谢谢阅读。

分享总是美好的。

坚持原创技术分享,您的支持将鼓励我继续创作!
0%