一、基本思想:五子棋存在多種連接方式,這也就決定了每一個(gè)空位的權(quán)值有所不同,我們對(duì)五子棋的不同連接方式設(shè)置權(quán)值,然后遍歷棋盤(pán),算出每一個(gè)空位上的權(quán)值,選擇權(quán)值最大的空位下棋,所以這個(gè)算法的關(guān)鍵就在于:1.設(shè)置并且存儲(chǔ)不同連接方式及其對(duì)應(yīng)的權(quán)值 2.計(jì)算棋盤(pán)空位上的權(quán)值。
二、設(shè)置不同連接方式的權(quán)值并進(jìn)行存儲(chǔ)
棋子的連接分為活連與死連,假設(shè)0代表空位,1代表黑棋,2代表白旗,如010為活連,01(遇到邊界)為死連為不同連接方式設(shè)置對(duì)應(yīng)權(quán)值:
假設(shè)0代表空位,1代表黑棋,2代表白旗
權(quán)值表(還可以細(xì)分)
連接方式 權(quán)值 010 50 0110 150 01110 500 011110 3000 020 50 0220 150 02220 500 022220 3000 01 30 011 90 0111 300 01111 3000 02 30 022 90 0222 300 02222 3000?
設(shè)置好權(quán)值表后,就要考慮如何存儲(chǔ)權(quán)值表,因?yàn)闄?quán)值表中的數(shù)據(jù)是用來(lái)后續(xù)計(jì)算空位總權(quán)值所需的。這里我們考慮用哈希表進(jìn)行存儲(chǔ)“連接方式——權(quán)值”這樣子的鍵值對(duì)
Key-Value : 鍵值對(duì)?
HashMap:
-
將鍵值對(duì)一起存入 ,可以通過(guò)鍵來(lái)查詢(xún)對(duì)應(yīng)的值
-
將連子情況作為Key ,權(quán)值分作為Value
-
1: 鍵不能重復(fù),值可以重復(fù)
-
2: HashMap 存儲(chǔ)優(yōu)勢(shì)是 查詢(xún)時(shí)是O1的時(shí)間復(fù)雜度
-
3: HashMap 存儲(chǔ)原理:
- 1: 用key來(lái)計(jì)算一個(gè)hash值 (當(dāng)作唯一標(biāo)識(shí)),hash值然后作為下標(biāo) ,然后將k-v存儲(chǔ)在數(shù)組中對(duì)應(yīng)下標(biāo)位置
-
操作:
- 實(shí)例化: HashMap<String,Integer> codeMap = new HashMap();
- 方法: code.put(key,value);/ value = code.get(key);
static HashMap<String, Integer> codeMap = new HashMap<> ();
static int[][] codeArrray = new int[16][16]; //創(chuàng)建用來(lái)存儲(chǔ)權(quán)值的二維數(shù)組
// 靜態(tài)代碼塊
static{
codeMap.put ("010", 50);
codeMap.put ("0110", 150);
codeMap.put ("01110", 500);
codeMap.put ("011110", 3000);
codeMap.put ("020", 50);
codeMap.put ("0220", 150);
codeMap.put ("02220", 500);
codeMap.put ("022220", 3000);
codeMap.put ("01", 30);
codeMap.put ("011", 90);
codeMap.put ("0111", 300);
codeMap.put ("01111", 3000);
codeMap.put ("02", 30);
codeMap.put ("022", 90);
codeMap.put ("0222", 300);
codeMap.put ("02222", 3000);
Integer integer = codeMap.get ("010");
System.out.println (integer);
}
三、遍歷表格計(jì)算權(quán)值
如圖一個(gè)五子棋盤(pán):
?
嘗試計(jì)算a、b兩個(gè)空位處的權(quán)值大小,我們可以發(fā)現(xiàn)空位處的連接可以往上、下、左、右、左上、右上、左下、右下一共8個(gè)方向進(jìn)行搜索,同時(shí)我們?cè)僖?guī)定一個(gè)空位的權(quán)值由八個(gè)方向的連接帶來(lái)的權(quán)值簡(jiǎn)單相加得到(規(guī)則不唯一)。
對(duì)于a,往左的連接為01,權(quán)值30;往下的連接為01,權(quán)值30;往右下的連接010,權(quán)值50,故a處的權(quán)值為30+30+50=110
對(duì)于b,往左的連接為022,權(quán)值90;往上的連接為01,權(quán)值30;往左上的連接為011,權(quán)值90,故b處的權(quán)值為90+30+90=210
有了上面的舉例,下面通過(guò)遍歷計(jì)算每一個(gè)空位的權(quán)值
private static void getCodeArray(int[][] arr){
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < arr[i].length; j++){
int chessNum = arr[i][j];
// 遍歷所有的空格
if(chessNum == 0){
toRight (i, j, arr); //往右走的權(quán)值
toLeft(i,j,arr);
toUp(i,j,arr);
toDown(i,j,arr);
toLeftUp(i,j,arr); //往左上走的權(quán)值
toRightup(i,j,arr);
toLeftDown(i,j,arr);
toRightDown(i,j,arr);
}
}
}
}
上面的代碼中往8個(gè)方向計(jì)算權(quán)值,但是方法還未定義,下面以往右和往左上為例
往右:
private static void toRight(int i, int j, int[][] chessArray){
// 等于0
int chessNum = chessArray[i][j];
// 右邊是0/墻 return
if(j + 1 >= chessArray[i].length || chessArray[i][j + 1] == 0){
return;
}
// 右邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i][j + 1];
String codeStr = "" + chessNum + chessNumR1;
// 右邊第二顆 0/與第一顆相同的/不同的/墻
for(int m = j + 2; m < chessArray[i].length; m++){
int chessNumRn = chessArray[i][m];
if(chessNumRn != 0){
if(chessNumR1 == chessNumRn){
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if(chessNumR1 != chessNumRn){
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else{
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
往左上:
private static void toLeftUp(int i, int j, int[][] chessArray) {
// 等于0
int chessNum = chessArray[i][j];
// 左上邊是0/墻 return
if(i - 1 <= -1||j - 1<= -1|| chessArray[i - 1][j - 1] == 0){
return;
}
// 左上邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i - 1][j - 1];
String codeStr = "" + chessNum + chessNumR1;
// 左上邊第二顆 0/與第一顆相同的/不同的/墻
for(int k = i - 2; k > -1; k--) {
for (int m = j - 2; m > -1; m--) {
int chessNumRn = chessArray[k][m];
if (chessNumRn != 0) {
if (chessNumR1 == chessNumRn) {
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if (chessNumR1 != chessNumRn) {
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else {
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
這里無(wú)論是往哪個(gè)方向,計(jì)算出來(lái)的權(quán)值都需要累加到codeArray對(duì)應(yīng)位置,codeArray是已經(jīng)定義的存儲(chǔ)權(quán)值的二維數(shù)組文章來(lái)源:http://www.zghlxwxcb.cn/news/detail-715009.html
完整代碼:文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-715009.html
package com.zsj0929;
import java.util.HashMap;
public class AI {// 會(huì)在類(lèi)使用的時(shí)候初始化
static HashMap<String, Integer> codeMap = new HashMap<> ();
static int[][] codeArrray = new int[16][16];
// 靜態(tài)代碼塊
static{
codeMap.put ("010", 50);
codeMap.put ("0110", 150);
codeMap.put ("01110", 500);
codeMap.put ("011110", 3000);
codeMap.put ("020", 50);
codeMap.put ("0220", 150);
codeMap.put ("02220", 500);
codeMap.put ("022220", 3000);
codeMap.put ("01", 30);
codeMap.put ("011", 90);
codeMap.put ("0111", 300);
codeMap.put ("01111", 3000);
codeMap.put ("02", 30);
codeMap.put ("022", 90);
codeMap.put ("0222", 300);
codeMap.put ("02222", 3000);
Integer integer = codeMap.get ("010");
System.out.println (integer);
}
public static void main(String[] args){
int[][] arr = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
// 遍歷計(jì)算所有可以下棋的地方的權(quán)值
getCodeArray (arr);
// 獲取矩陣中權(quán)值最大的位置
for(int i = 0; i < codeArrray.length; i++){
for(int j = 0; j < codeArrray[i].length; j++){
System.out.print (codeArrray[i][j] + " ");
}
System.out.println ();
}
}
private static void getCodeArray(int[][] arr){
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < arr[i].length; j++){
int chessNum = arr[i][j];
// 遍歷所有的空格
if(chessNum == 0){
toRight (i, j, arr); //往右走的權(quán)值
toLeft(i,j,arr);
toUp(i,j,arr);
toDown(i,j,arr);
toLeftUp(i,j,arr); //往左上走的權(quán)值
toRightup(i,j,arr);
toLeftDown(i,j,arr);
toRightDown(i,j,arr);
}
}
}
}
private static void toRightDown(int i, int j, int[][] chessArray) {
// 等于0
int chessNum = chessArray[i][j];
// 右下邊是0/墻 return
if(i + 1 >= chessArray.length||j + 1>=chessArray.length || chessArray[i + 1][j + 1] == 0){
return;
}
// 右下邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i + 1][j + 1];
String codeStr = "" + chessNum + chessNumR1;
// 右下邊第二顆 0/與第一顆相同的/不同的/墻
for(int k = i + 2; k < chessArray.length; k++) {
for (int m = j + 2; m < chessArray[i].length; m++) {
int chessNumRn = chessArray[k][m];
if (chessNumRn != 0) {
if (chessNumR1 == chessNumRn) {
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if (chessNumR1 != chessNumRn) {
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else {
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
private static void toLeftDown(int i, int j, int[][] chessArray) {
// 等于0
int chessNum = chessArray[i][j];
// 左下邊是0/墻 return
if(i + 1 >= chessArray.length||j - 1 <= -1 || chessArray[i + 1][j - 1] == 0){
return;
}
// 左下邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i + 1][j - 1];
String codeStr = "" + chessNum + chessNumR1;
// 左下邊第二顆 0/與第一顆相同的/不同的/墻
for(int k = i + 2; k < chessArray.length; k++) {
for (int m = j - 2; m >= -1; m--) {
int chessNumRn = chessArray[k][m];
if (chessNumRn != 0) {
if (chessNumR1 == chessNumRn) {
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if (chessNumR1 != chessNumRn) {
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else {
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
private static void toRightup(int i, int j, int[][] chessArray) {
// 等于0
int chessNum = chessArray[i][j];
// 右上邊是0/墻 return
if(i - 1 <= -1||j + 1>=chessArray.length || chessArray[i - 1][j + 1] == 0){
return;
}
// 右上邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i - 1][j + 1];
String codeStr = "" + chessNum + chessNumR1;
// 右上邊第二顆 0/與第一顆相同的/不同的/墻
for(int k = i - 2; k > -1; k--) {
for (int m = j + 2; m < chessArray[i].length; m++) {
int chessNumRn = chessArray[k][m];
if (chessNumRn != 0) {
if (chessNumR1 == chessNumRn) {
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if (chessNumR1 != chessNumRn) {
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else {
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
private static void toLeftUp(int i, int j, int[][] chessArray) {
// 等于0
int chessNum = chessArray[i][j];
// 左上邊是0/墻 return
if(i - 1 <= -1||j - 1<= -1|| chessArray[i - 1][j - 1] == 0){
return;
}
// 左上邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i - 1][j - 1];
String codeStr = "" + chessNum + chessNumR1;
// 左上邊第二顆 0/與第一顆相同的/不同的/墻
for(int k = i - 2; k > -1; k--) {
for (int m = j - 2; m > -1; m--) {
int chessNumRn = chessArray[k][m];
if (chessNumRn != 0) {
if (chessNumR1 == chessNumRn) {
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if (chessNumR1 != chessNumRn) {
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else {
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
private static void toDown(int i, int j, int[][] chessArray) {
// 等于0
int chessNum = chessArray[i][j];
// 下邊是0/墻 return
if(i + 1 >= chessArray.length || chessArray[i + 1][j] == 0){
return;
}
// 下邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i + 1][j];
String codeStr = "" + chessNum + chessNumR1;
// 下邊第二顆 0/與第一顆相同的/不同的/墻
for(int k = i + 2; k < chessArray.length; k++){
int chessNumRn = chessArray[k][j];
if(chessNumRn != 0){
if(chessNumR1 == chessNumRn){
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if(chessNumR1 != chessNumRn){
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else{
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
private static void toUp(int i, int j, int[][] chessArray) {
// 等于0
int chessNum = chessArray[i][j];
// 上邊是0/墻 return
if(i - 1 <= -1 || chessArray[i - 1][j] == 0){
return;
}
// 上邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i - 1][j];
String codeStr = "" + chessNum + chessNumR1;
// 上邊第二顆 0/與第一顆相同的/不同的/墻
for(int k = i - 2; k > -1; k--){
int chessNumRn = chessArray[k][j];
if(chessNumRn != 0){
if(chessNumR1 == chessNumRn){
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if(chessNumR1 != chessNumRn){
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else{
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
private static void toLeft(int i, int j, int[][] chessArray) {
// 等于0
int chessNum = chessArray[i][j];
// 左邊是0/墻 return
if(j - 1 <= -1 || chessArray[i][j - 1] == 0){
return;
}
// 左邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i][j - 1];
String codeStr = "" + chessNum + chessNumR1;
// 左邊第二顆 0/與第一顆相同的/不同的/墻
for(int m = j - 2; m > -1; m--){
int chessNumRn = chessArray[i][m];
if(chessNumRn != 0){
if(chessNumR1 == chessNumRn){
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if(chessNumR1 != chessNumRn){
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else{
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
private static void toRight(int i, int j, int[][] chessArray){
// 等于0
int chessNum = chessArray[i][j];
// 右邊是0/墻 return
if(j + 1 >= chessArray[i].length || chessArray[i][j + 1] == 0){
return;
}
// 右邊第一個(gè)顆是1/2 記錄下來(lái)
int chessNumR1 = chessArray[i][j + 1];
String codeStr = "" + chessNum + chessNumR1;
// 右邊第二顆 0/與第一顆相同的/不同的/墻
for(int m = j + 2; m < chessArray[i].length; m++){
int chessNumRn = chessArray[i][m];
if(chessNumRn != 0){
if(chessNumR1 == chessNumRn){
// 找到相同的就拼接一個(gè)棋子標(biāo)識(shí)
codeStr += chessNumR1;
} else if(chessNumR1 != chessNumRn){
// 找到不相同的就結(jié)束循環(huán)
break;
}
} else{
// 活連的結(jié)尾 就結(jié)束循環(huán)
codeStr += "0";
break;
}
}
Integer codeValue = codeMap.get (codeStr);
if(codeValue == null){
return;
}
// 將權(quán)值分存入 一個(gè) 新的權(quán)值二維數(shù)組
codeArrray[i][j] += codeValue;
}
}
到了這里,關(guān)于五子棋簡(jiǎn)易AI算法的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!