前言:
本文只提供AI算法,不提供棋盘,因为棋盘不是我写的,不好拿出来分享,望谅解。
AI水平说明:
当前AI只能计算当前局面下最优的一步,没有深度,水平一般的普通人很轻易就会被其击败,但是有很大的升级空间,可以以此为基础再行添加算法添加深度,以及剪枝等算法。
程序运行图片:黑方为AI,我是白色(我是不是太菜了。。)
AI得分说明:
当前AI为黑色时水平较高,为白色时需要修改得分表,得分表会影响AI的决策,得分可以自行修改,此得分表并非最佳得分表,但是经过我的测试貌似还可以。ps:这是AI的核心非常重要
得分表如下:
using System;using System.Collections;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace 五子棋{public static class ChessValueUtil{public static Hashtable blackTable = new Hashtable(); //创建一个HashTable实例public static Hashtable whiteTable = new Hashtable(); //五子棋棋形,最长为7,最短为4(有些棋形必须将空位包含进去)public static Hashtable getBlackTable(){return blackTable;}public static Hashtable getWhiteTable(){return whiteTable;}/** * *:表示黑子 * -:表示空位 * o:表示白子 */static ChessValueUtil(){//还要设置防守方的数值,防止被gank掉//右边Add的whiteTable值,是防守分数,这样Ai就不会一味的猛冲//左边:黑方Ai的棋子判断右边:Ai结束后,玩家可能的棋子判断blackTable.Add("*****",100000);//连五/* */whiteTable.Add("ooooo",90000);blackTable.Add("-****-",5000);//活四/* */whiteTable.Add("-oooo-",4500);blackTable.Add("*-***",700);//冲四1/* */whiteTable.Add("o-ooo",200);blackTable.Add("***-*",700);//冲四1反向/* */whiteTable.Add("ooo-o",200);blackTable.Add("-****o",900);//冲四2/* */whiteTable.Add("-oooo*",250);blackTable.Add("o****-",900);//冲四2反向/* */whiteTable.Add("*oooo-",250);blackTable.Add("**-**",700);//冲四 3/* */whiteTable.Add("oo-oo", 200);blackTable.Add("-***-",600);//活三 1/* */whiteTable.Add("-ooo-",150);blackTable.Add("-*-**-",150);//活三2/* */whiteTable.Add("-o-oo-",50);blackTable.Add("-**-*-",150);//活三2 反向/* */whiteTable.Add("-oo-o-",50);blackTable.Add("--***o",120);//眠三1/* */whiteTable.Add("--ooo*",30);blackTable.Add("o***--",120);//眠三1反向/* */whiteTable.Add("*ooo--",30);blackTable.Add("-*-**o",80);//眠三 2/* */whiteTable.Add("-o-oo*",15);blackTable.Add("o**-*-",80);//眠三 2反向/* */whiteTable.Add("*oo-o-",15);blackTable.Add("-**-*o",60);//眠三 3/* */whiteTable.Add("-oo-o*",10);blackTable.Add("o*-**-",60);//眠三 3 反向/* */whiteTable.Add("*o-oo-",10);blackTable.Add("*--**",60);//眠三 4/* */whiteTable.Add("o--oo",10);blackTable.Add("**--*",60);//眠三 4 反向/* */whiteTable.Add("oo--o",10);blackTable.Add("*-*-*",60);//眠三 5/* */whiteTable.Add("o-o-o",10);blackTable.Add("o-***-o",60);//眠三 6/* */whiteTable.Add("*-ooo-*",2);blackTable.Add("--**--",50);//活二1/* */whiteTable.Add("--oo--",2);blackTable.Add("-*-*-",20);//活二 2/* */whiteTable.Add("-o-o-",2);blackTable.Add("*--*",20);//活二 3/* */whiteTable.Add("o--o",2);blackTable.Add("---**o",10);//眠二1/* */whiteTable.Add("---oo*",1);blackTable.Add("o**---",10);//眠二1 反向/* */whiteTable.Add("*oo---",1);blackTable.Add("--*-*o",10);//眠二2/* */whiteTable.Add("--o-o*",1 );blackTable.Add("o*-*--",10);//眠二2 反向/* */whiteTable.Add("*o-o--",1);blackTable.Add("-*--*o",10);//眠二3/* */whiteTable.Add("-o--o*",1);blackTable.Add("o*--*-",10);//眠二3 反向/* */whiteTable.Add("*o--o-",1);blackTable.Add("*---*",10);//眠二4/* */whiteTable.Add("o---o",1);}}}
AI算法思路讲解:
首先我们需要知道输入和输出,给输入当前棋盘的二维数组,从而让他返回落点坐标。落点坐标有x,y两个值,我们可以先创建一个点的结构体,包括点信息,和当前点的分值:
public struct Point
{
public int value;
public int x;
public int y;}
二维数组中存储的是数字,而我们得分表中用的字符串,所以我们需要一个转换的方法,传入棋盘中某一条链,返回该链字符串形式:
public static string ChessChainTostring(int[] CheckChain)
{
string pool = “”;
foreach (int chessColor in CheckChain)
{
if (chessColor == 0)
{
pool += “-“;
}
else if (chessColor == 1)
{
pool += “*”;
}
else if (chessColor == 2)
{
pool += “o”;
}
else
{
//放入一个hash表中不存在的字符
//这样后面算权值的时候就不会把它加进去了
pool += “#”;
}
}
return pool;
}
核心思想:
此处为我自己的思考方式,因为我实在是搞懂别人是怎么算的,思路很可能不一样,但是我的思路很简单,代码也少,但是运算量很大,如果你很有兴趣可以自己试着优化。
最后一步肯定是依次计算棋盘中每一个点的分值,并从中选取得分最高的点返回(如果得分相同按理来说应该写个方法随机返回,我这里没写,默认返回第一个)
int[,] map = new int[len, len];
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
if (ChessBoard[i, j] == 0)
{
map[i,j]=getScore(ChessBoard, i, j);
if (map[i, j] > max)
{
max = map[i, j];
point.value = max;
point.x = i;
point.y = j;
}
}
}
}
计算分值思路:
假设在当前点下棋,拿到当前点位置横竖撇奈四条线上所有链条,转化为字符串并与得分表中的字符串进行比对,如果包含得分表中字符串就加上相应的分数,四条链每一条都要进行判断,最后得到在当前点落点的分值。
假设当前点不下棋,通过同样方式计算得到原本该点四条链上的分值。
落点的分值-不落点的分值=当前点的得分
当前点得分有两种,因为我们有两个得分表(一黑一白),一种是进攻分,一种是防守分,都要进行计算,算出当前点的进攻分和防守分的总和,在减去两种原始得分,才能得出走该点真实分值。
算完后不要忘记将棋盘还原。
public static int getScore(int[,] ChessBoard, int x, int y)
{
int oldBlackValue=getValue(ChessBoard, x, y,1);
int oldWhiteValue = getValue(ChessBoard, x, y, 2);
ChessBoard[x, y] = 1;
int atkValue=getValue(ChessBoard, x, y,1);
ChessBoard[x, y] = 2;
int defValue= getValue(ChessBoard, x, y,2);
int score = atkValue + defValue – oldBlackValue- oldWhiteValue;//复原棋盘
ChessBoard[x, y] = 0;
return score;
}
public static int getValue(int[,] ChessBoard,int x,int y,int color)
{
int value = 0;
ArrayList Chains=getChains(ChessBoard, x, y);
foreach (int[] chain in Chains)
{
string str=ChessChainTostring(chain);
Hashtable table;
if (color == 1)
{
table = ChessValueUtil.getBlackTable();
}
else
{
table = ChessValueUtil.getWhiteTable();
}
ICollection keys = table.Keys;
foreach (string key in keys)
{
for (int i = 0; i < str.Length – key.Length+1; i++)
{
if (str.Substring(i, key.Length) == key)
{
value += (int)table[key];
}
}
}
}
return value;
}
public static ArrayList getChains(int[,] ChessBoard,int x,int y)
{
int len = 15;
ArrayList Chains = new ArrayList();
//横
int[] heng = new int[len];
for (int i = 0; i < len; i++)
{
heng[i]=ChessBoard[i, y];
}
Chains.Add(heng);
//竖
int[] shu = new int[len];
for (int i = 0; i < len; i++)
{
shu[i] = ChessBoard[x, i];
}
Chains.Add(shu);
//撇,x+,y-
int[] pie = new int[len];
int tmpX = x;
int tmpY = y;
while (tmpX > 0 && tmpY < len – 1)
{
tmpX–;
tmpY++;
}
int k = 0;
while (tmpX = 0)
{
pie[k++] = ChessBoard[tmpX, tmpY];
tmpX++;
tmpY–;
}
if (k < len)
{
pie[k] = -1;
}
Chains.Add(pie);
//捺
int[] nai= new int[len];
tmpX = x;
tmpY = y;
while (tmpX > 0 && tmpY>0)
{
tmpX–;
tmpY–;
}
k = 0;
while (tmpX <= len – 1 && tmpY <= len – 1)
{
nai[k++] = ChessBoard[tmpX, tmpY];
tmpX++;
tmpY++;
}
if (k < len)
{
nai[k] = -1;
}
Chains.Add(nai);
return Chains;
}
这段代码判断当前棋盘为空时直接返回中间点坐标,其实最好还是不要写在AI里,因为每次都要循环一遍棋盘,最好是写在外面:
int flag = 0;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
if (ChessBoard[i, j] != 0)
{
flag = 1;
break;}
if (flag == 1)
{
break;
}
}
}
if (flag == 0)
{
point.value = 0;
point.x = 7;
point.y = 7;
return point;
}
完整代码(代码写的很垃圾,见谅):
using System;using System.Collections;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Windows.Forms;namespace 五子棋{static class ChessUtil{public struct Point{public int value;public int x;public int y;}/*** 将棋子的颜色序列转换为字符序列* 这样才能放入hashtable中进行比较*//** * *:表示黑子 * -:表示空位 * o:表示白子 */public static string ChessChainTostring(int[] CheckChain){string pool = "";foreach (int chessColor in CheckChain){if (chessColor == 0){pool += "-";}else if (chessColor == 1){pool += "*";}else if (chessColor == 2){pool += "o";}else{//放入一个hash表中不存在的字符//这样后面算权值的时候就不会把它加进去了pool += "#";}}return pool;}public static ArrayList getChains(int[,] ChessBoard,int x,int y){int len = 15;ArrayList Chains = new ArrayList();//横int[] heng = new int[len];for (int i = 0; i < len; i++){heng[i]=ChessBoard[i, y];}Chains.Add(heng);//竖int[] shu = new int[len];for (int i = 0; i 0 && tmpY < len - 1){tmpX--;tmpY++;}int k = 0;while (tmpX = 0){pie[k++] = ChessBoard[tmpX, tmpY];tmpX++;tmpY--;}if (k 0 && tmpY>0){tmpX--;tmpY--;}k = 0;while (tmpX <= len - 1 && tmpY <= len - 1){nai[k++] = ChessBoard[tmpX, tmpY];tmpX++;tmpY++;}if (k < len){nai[k] = -1;}Chains.Add(nai);return Chains;}public static int getValue(int[,] ChessBoard,int x,int y,int color){int value = 0;ArrayList Chains=getChains(ChessBoard, x, y);foreach (int[] chain in Chains){string str=ChessChainTostring(chain);Hashtable table;if (color == 1){table = ChessValueUtil.getBlackTable();}else{table = ChessValueUtil.getWhiteTable();}ICollection keys = table.Keys;foreach (string key in keys){for (int i = 0; i < str.Length - key.Length+1; i++){if (str.Substring(i, key.Length) == key){value += (int)table[key];}}}}return value;}public static int getScore(int[,] ChessBoard, int x, int y){int oldBlackValue=getValue(ChessBoard, x, y,1);int oldWhiteValue = getValue(ChessBoard, x, y, 2);ChessBoard[x, y] = 1;int atkValue=getValue(ChessBoard, x, y,1);ChessBoard[x, y] = 2;int defValue= getValue(ChessBoard, x, y,2);int score = atkValue + defValue - oldBlackValue- oldWhiteValue;ChessBoard[x, y] = 0;return score;}public static Point getScoreMap(int[,] ChessBoard){Point point;int max = 0;point.value = 0;point.x = 0;point.y = 0;int len = 15;int flag = 0;for (int i = 0; i < len; i++){for (int j = 0; j < len; j++){if (ChessBoard[i, j] != 0){flag = 1;break;}if (flag == 1){break;}}}if (flag == 0){point.value = 0;point.x = 7;point.y = 7;return point;}int[,] map = new int[len, len];for (int i = 0; i < len; i++){for (int j = 0; j max){max = map[i, j];point.value = max;point.x = i;point.y = j;}}}}return point;}}}
最后一个方法本来是计算当所有点坐标的分值图,从而进行二次甚至是三次递归的,但是因为是简单AI,所以算一次就返回吧,其实有些运算都是可以避免的,比如如果某点附近5步之内没有点,其实可以直接跳过的,但是我没进行优化,所以运算量是相当大了,大家自己试着优化吧。
如果是白棋的话,翻转一下棋盘传进去,就能获得一个偏向进攻的白棋,但是可能会出现某些问题,还有就是传入的棋盘最好是备份的,尽量不要把原本的棋盘传进去,就这样吧。
如果你找到了更好的计算当前点分数的方法,请务必给我留言,感激不尽!