Java 五子棋AI
前言
根据之前查询的资料我了解到,要想写出无可匹敌的五子棋AI,要用到博弈树、AlphaBeta减枝法、机器学习等知识,但是因为个人水平的原因,这些都无法实现,不过我的算法起码能保证玩家稍不留神,就会被打败,这和五子棋新手博弈、OJ霸榜,都足够了。等到日后自己的知识量增加了,再来对这个程序进行完善吧。
五子棋棋型介绍
最常见的基本棋型大体有以下几种:连五,活四,冲四,活三,眠三,活二,眠二。
①连五:顾名思义,五颗同色棋子连在一起,不需要多讲。
②活四:有两个连五点(即有两个点可以形成五),图中白点即为连五点。
稍微思考一下就能发现活四出现的时候,如果对方单纯过来防守的话,是已经无法阻止自己连五了。
③冲四:有一个连五点,如下面三图,均为冲四棋型。图中白点为连五点。
相对比活四来说,冲四的威胁性就小了很多,因为这个时候,对方只要跟着防守在那个唯一的连五点上,冲四就没法形成连五。
④活三:可以形成活四的三,如下图,代表两种最基本的活三棋型。图中白点为活四点。
活三棋型是我们进攻中最常见的一种,因为活三之后,如果对方不以理会,将可以下一手将活三变成活四,而我们知道活四是已经无法单纯防守住了。所以,当我们面对活三的时候,需要非常谨慎对待。在自己没有更好的进攻手段的情况下,需要对其进行防守,以防止其形成可怕的活四棋型。
⑤眠三:只能够形成冲四的三,如下各图,分别代表最基础的六种眠三形状。图中白点代表冲四点。眠三的棋型与活三的棋型相比,危险系数下降不少,因为眠三棋型即使不去防守,下一手它也只能形成冲四,而对于单纯的冲四棋型,我们知道,是可以防守住的。
如上所示,眠三的形状是很丰富的。对于初学者,在下棋过程中,很容易忽略不常见的眠三形状,例如图5-6所示的眠三。
有新手学了活三眠三后,会提出疑问,说活三也可以形成冲四啊,那岂不是也可以叫眠三?
会提出这个问题,说明对眠三定义看得不够仔细:眠三的的定义是,只能够形成冲四的三。而活三可以形成眠三,但也能够形成活四。
此外,在五子棋中,活四棋型比冲四棋型具有更大的优势,所以,我们在既能够形成活四又能够形成冲四时,会选择形成活四。
温馨提示:学会判断一个三到底是活三还是眠三是非常重要的。所以,需要好好体会。
后边禁手判断的时候也会有所应用。
⑥活二:能够形成活三的二,如下图,是三种基本的活二棋型。图中白点为活三点。
活二棋型看起来似乎很无害,因为他下一手棋才能形成活三,等形成活三,我们再防守也不迟。但其实活二棋型是非常重要的,尤其是在开局阶段,我们形成较多的活二棋型的话,当我们将活二变成活三时,才能够令自己的活三绵绵不绝微风里,让对手防不胜防。
⑦眠二:能够形成眠三的二。图中四个为最基本的眠二棋型,细心且喜欢思考的同学会根据眠三介绍中的图2-13找到与下列四个基本眠二棋型都不一样的眠二。图中白点为眠三点。
一、基本思想:五子棋存在多种连接方式,这也就决定了每一个空位的权值有所不同,我们对五子棋的不同连接方式设置权值,然后遍历棋盘,算出每一个空位上的权值,选择权值最大的空位下棋,所以这个算法的关键就在于:1.设置并且存储不同连接方式及其对应的权值 2.计算棋盘空位上的权值。
二、设置不同连接方式的权值并进行存储
首先我们得选择拿什么来储存棋链和权值,这里我们考虑用哈希表进行存储“连接方式——权值”这样子的键值对
Key-Value : 键值对
HashMap:
将键值对一起存入 ,可以通过键来查询对应的值
将棋链作为Key ,权值分作为Value
1: 键不能重复,值可以重复
2: HashMap 存储优势是 查询时是O1的时间复杂度
3: HashMap 存储原理:
1: 用key来计算一个hash值 (当作唯一标识),hash值然后作为下标 ,然后将k-v存储在数组中对应下标位置
操作:
实例化: private static Map<String, Integer> AttackMap = new HashMap<>();
private static Map<String, Integer> DefendMap = new HashMap<>();
这里我们需要创建两个HashMap,一个作为进攻的权值储存一个是防守的权值储存,然后Ai将会结合两者的权值来选择最好的落棋位置。
-:表示空棋 *:表示黑棋 o:表示白棋
然后将棋链与他所对应的权值加入两个HashMap中。
static {
// 还要重新设计赋分策略,才能保证五子棋机器人的准确判断
// 因为已经固定了 *为黑子,且默认将机器人设为黑方,所以机器人只能是黑方
// 还要设置防守方的数值,防止被gank掉
// 右边put的map值,是防守分数,这样Ai就不会一味的猛冲
// 左边:进攻棋链,权值越大说明该棋链越接近胜利 右边:防御棋链,权值越大说明该棋链约值得防御
AttackMap.put("*****", 100000);
// 连五
/* */DefendMap.put("ooooo", 30000);
AttackMap.put("-****-", 5000);
// 活四
/* */DefendMap.put("-oooo-", 3000);
AttackMap.put("*-***", 700);
// 冲四 1
/* */DefendMap.put("o-ooo", 150);
AttackMap.put("***-*", 700);
// 冲四 1 反向
/* */DefendMap.put("ooo-o", 150);
AttackMap.put("-****o", 1000);
// 冲四 2
/* */DefendMap.put("-oooo*", 200);
AttackMap.put("o****-", 1000);
// 冲四 2 反向
/* */DefendMap.put("*oooo-", 200);
AttackMap.put("**-**", 700);
// 冲四 3
/* */DefendMap.put("oo-oo", 200);
AttackMap.put("-***-", 500);
// 活三 1
/* */DefendMap.put("-ooo-", 100);
AttackMap.put("*-**", 150);
// 活三 2
/* */DefendMap.put("o-oo", 50);
AttackMap.put("**-*", 150);
// 活三 2 反向
/* */DefendMap.put("oo-o", 50);
AttackMap.put("--***o", 100);
// 眠三 1
/* */DefendMap.put("--ooo*", 20);
AttackMap.put("o***--", 100);
// 眠三 1 反向
/* */DefendMap.put("*ooo--", 20);
AttackMap.put("-*-**o", 80);
// 眠三 2
/* */DefendMap.put("-o-oo*", 15);
AttackMap.put("o**-*-", 80);
// 眠三 2 反向
/* */DefendMap.put("*oo-o-", 15);
AttackMap.put("-**-*o", 60);
// 眠三 3
/* */DefendMap.put("-oo-o*", 10);
AttackMap.put("o*-**-", 60);
// 眠三 3 反向
/* */DefendMap.put("*o-oo-", 10);
AttackMap.put("*--**", 60);
// 眠三 4
/* */DefendMap.put("o--oo", 10);
AttackMap.put("**--*", 60);
// 眠三 4 反向
/* */DefendMap.put("oo--o", 10);
AttackMap.put("*-*-*", 60);
// 眠三 5
/* */DefendMap.put("o-o-o", 10);
AttackMap.put("o-***-o", 60);
// 眠三 6
/* */DefendMap.put("*-ooo-*", 2);
AttackMap.put("--**--", 50);
// 活二 1
/* */DefendMap.put("--oo--", 2);
AttackMap.put("-*-*-", 20);
// 活二 2
/* */DefendMap.put("-o-o-", 2);
AttackMap.put("*--*", 20);
// 活二 3
/* */DefendMap.put("o--o", 2);
AttackMap.put("---**o", 10);
// 眠二 1
/* */DefendMap.put("---oo*", 1);
AttackMap.put("o**---", 10);
// 眠二 1 反向
/* */DefendMap.put("*oo---", 1);
AttackMap.put("--*-*o", 10);
// 眠二 2
/* */DefendMap.put("--o-o*", 1);
AttackMap.put("o*-*--", 10);
// 眠二 2 反向
/* */DefendMap.put("*o-o--", 1);
AttackMap.put("-*--*o", 10);
// 眠二 3
/* */DefendMap.put("-o--o*", 1);
AttackMap.put("o*--*-", 10);
// 眠二 3 反向
/* */DefendMap.put("*o--o-", 1);
AttackMap.put("*---*", 10);
// 眠二 4
/* */DefendMap.put("o---o", 1);
三、遍历表格计算权值
public static int CalculateValue(Position p) {
// 调用方法,返回该点的棋链
List<String> attackList = getPositionChessLink(p, "attack");
List<String> defendList = getPositionChessLink(p, "defend");
// 计算权值
int attackValue = 0;
int defendValue = 0;
for (String s : attackList) {
if (AttackMap.containsKey(s)) {
attackValue += AttackMap.get(s);
}
}
for (String s : defendList) {
if (DefendMap.containsKey(s)) {
defendValue += DefendMap.get(s);
}
}
return Math.abs(attackValue - defendValue); // 值越大说明该点即适合防御又适合进攻
}
四、获取点的所有棋链
竖直方向上的棋链:
for (int i = 4; i <= 7; i++) { // 棋链长度最短4 最长不超过7
for (int j = 0; j < i; j++) { // 判断传入的棋子在棋链上的位置(即第几个棋子,从左向右数)
String s = "";
int startRow = p.getX() - j; // 计算方向的开始坐标,从该点为原点遍历
int endRow = startRow + i - 1; // 计算方向的结束坐标,减去本身,决定4-7的长度
// 此处需要判断开始的点和结束的点是否超出了棋盘
if (startRow < 0 || endRow >= size) {
// 该点超过了棋盘的范围
continue;
}
for (; startRow <= endRow; startRow++) {
if (colorPad[startRow][p.getY()] == ChessColor.Blank) {
s = s + "-";
} else if (colorPad[startRow][p.getY()] == ChessColor.White) {
s = s + "o";
} else {
s = s + "*";
}
}
resultList.add(s); // 将该棋链加入结果列表
}
}
水平方向上:
for (int i = 4; i <= 7; i++) { // 棋链长度,最短4,最长7
for (int j = 0; j < i; j++) { // 棋在棋链上的位置,(从上往下)
String s = "";
// 由于是横方向,故只需要计算开始的y和结束的y坐标
int startCol = p.getY() - j;
int endCol = startCol + i - 1;
// 判断开始位置和结束位置是否在棋盘范围内
if (startCol < 0 || endCol >= size) {
continue;
}
for (; startCol <= endCol; startCol++) {
if (colorPad[p.getX()][startCol] == ChessColor.Blank) {
s = s + "-";
} else if (colorPad[p.getX()][startCol] == ChessColor.White) {
s = s + "o";
} else {
s = s + "*";
}
}
// System.out.println(s);
resultList.add(s);
}
}
斜方向上:
for (int i = 4; i <= 7; i++) {
for (int j = 0; j < i; j++) {
// 此处为斜方向,改变棋在棋链上的位置,涉及 x 和 y 两个方向的改变,从左下往右上的方向来计算 两个坐标的变化为
int startRow = p.getX() + j;
int startCol = p.getY() - j;
int endRow = startRow - i + 1;
int endCol = startCol + i - 1;
// 判断开始点和结束点是否在棋盘内
if (!((startRow >= 0 && startRow < size && startCol >= 0 && startCol < size)
&& (endRow >= 0 && endRow < size && endCol >= 0 && endCol < size))) {
continue;
}
String s = "";
for (int row = startRow, col = startCol; row >= endRow && col <= endCol; row--, col++) {
if (colorPad[row][col] == ChessColor.Blank) {
s = s + "-";
} else if (colorPad[row][col] == ChessColor.White) {
s = s + "o";
} else {
s = s + "*";
}
}
resultList.add(s);
}
}
反斜方向上:
for (int i = 4; i <= 7; i++) {
for (int j = 0; j < i; j++) {
// 计算开始的点
int startRow = p.getX() - j;
int startCol = p.getY() - j;
int endRow = startRow + i - 1;
int endCol = startCol + i - 1;
String s = "";
if (!((startRow >= 0 && startRow < size && startCol >= 0 && startCol < size)
&& (endRow >= 0 && endRow < size && endCol >= 0 && endCol < size))) {
continue;
}
for (int row = startRow, col = startCol; row <= endRow && col <= endCol; row++, col++) {
if (colorPad[row][col] == ChessColor.Blank) {
s = s + "-";
} else if (colorPad[row][col] == ChessColor.White) {
s = s + "o";
} else {
s = s + "*";
}
}
// System.out.println(s);
resultList.add(s);
}
}
五、判断棋局
最后还要判断棋局的情况,将所有点的棋链找出然后判断是否有获胜的一方,或者是否还有空格来决定平局。
public static void Judge(){
//获取所有的棋链
List<String> allChessLink = getAllChessLink();
for (String s : allChessLink) {
if(s.equals("ooooo")){
JOptionPane.showMessageDialog(MainPanel.getInstance(),"白方获胜","游戏结束",JOptionPane.INFORMATION_MESSAGE);
new StopListener().actionPerformed(null); //完成重置工作
return;
}
else if(s.equals("*****")){
JOptionPane.showMessageDialog(MainPanel.getInstance(),"黑方获胜","游戏结束",JOptionPane.INFORMATION_MESSAGE);
new StopListener().actionPerformed(null); //完成重置工作
return;
}
}
//判断是否为平局
boolean flag=true;
int count = 0;
for (int i=0;i<15;i++){
for (int j=0;j<15;j++){
flag=ChessPad.colorPad[i][j]==ChessColor.Blank;
if(flag==true)
{
count++;
}
}
}
if(count>=1)
{
flag=true;
}
if(!flag){
JOptionPane.showMessageDialog(MainPanel.getInstance(),"平局","游戏结束",JOptionPane.INFORMATION_MESSAGE);
new StopListener().actionPerformed(null); //完成重置工作
return;
}
}
文章出处登录后可见!