AI算法玩转象棋

大家好 我是毕加锁 (锁!)

今天教大家 python 象棋AI算法

一，棋子的着法

com.bylaw ={}

(1)车：

com.bylaw.c = function (x,y,map,my){

var d=[];

//左侧检索 若存在棋子且颜色不同则push过去并结束循环，否则一步步push

for (var i=x-1; i>= 0; i--){

if (map[y][i]) {

if (com.mans[map[y][i]].my!=my) d.push([i,y]);

break

}else{

d.push([i,y])

}

}

//右侧检索

for (var i=x+1; i <= 8; i++){

if (map[y][i]) {

if (com.mans[map[y][i]].my!=my) d.push([i,y]);

break

}else{

d.push([i,y])

}

}

//上检索

for (var i = y-1 ; i >= 0; i--){

if (map[i][x]) {

if (com.mans[map[i][x]].my!=my) d.push([x,i]);

break

}else{

d.push([x,i])

}

}

//下检索

for (var i = y+1 ; i<= 9; i++){

if (map[i][x]) {

if (com.mans[map[i][x]].my!=my) d.push([x,i]);

break

}else{

d.push([x,i])

}

}

return d;

}

算法分析：

分别向上，下，左，右四个方向搜索，若找到一个点且颜色与该棋子不同(敌对棋子)，则将该点坐标记录在d数组中，若某一方向上没有其他棋子，将这一方向上所有坐标都记录在d数组中。简单来讲：就是将以车这个棋子为中心的十字上的坐标都记录在d数组中(你早这样说多好~,开始说那么多)

前提补充：

1，代码中的map：

com.initMap = [

['C0','M0','X0','S0','J0','S1','X1','M1','C1'],

[ , , , , , , , , ],

[ ,'P0', , , , , ,'P1', ],

['Z0', ,'Z1', ,'Z2', ,'Z3', ,'Z4'],

[ , , , , , , , , ],

[ , , , , , , , , ],

['z0', ,'z1', ,'z2', ,'z3', ,'z4'],

[ ,'p0', , , , , ,'p1', ],

[ , , , , , , , , ],

['c0','m0','x0','s0','j0','s1','x1','m1','c1']

];

这里的字符串代表每个棋子的key值：

com.keys = { //设定每类棋子的key值

"c0":"c","c1":"c",

"m0":"m","m1":"m",

"x0":"x","x1":"x",

"s0":"s","s1":"s",

"j0":"j",

"p0":"p","p1":"p",

"z0":"z","z1":"z","z2":"z","z3":"z","z4":"z","z5":"z",

"C0":"C","C1":"C",

"M0":"M","M1":"M",

"X0":"X","X1":"X",

"S0":"S","S1":"S",

"J0":"J",

"P0":"P","P1":"P",

"Z0":"Z","Z1":"Z","Z2":"Z","Z3":"Z","Z4":"Z","Z5":"Z",

}

2，my：

标记值：1代表红色方(这里指人。玩家永远操纵红色)   ；          -1代表AI

3，map[y][i]与d.push([i][y])

左方向上搜索，y坐标不变，x坐标遍历，而体现在map当中(向上翻第一点)，仔细看就会发现：第一个下标代表y值，第二个下标代表x值，其与坐标值正好相反

其他方向上以此类推。。。

(2)马

com.bylaw.m = function (x,y,map,my){

var d=[];

//1点钟方向 不绊马脚 1点不存在棋子或1点棋子颜色不同 push

if ( y-2>= 0 && x+1<= 8 && !play.map[y-1][x] &&(!com.mans[map[y-2][x+1]] || com.mans[map[y-2][x+1]].my!=my)) d.push([x+1,y-2]);

//2点

if ( y-1>= 0 && x+2<= 8 && !play.map[y][x+1] &&(!com.mans[map[y-1][x+2]] || com.mans[map[y-1][x+2]].my!=my)) d.push([x+2,y-1]);

//4点

if ( y+1<= 9 && x+2<= 8 && !play.map[y][x+1] &&(!com.mans[map[y+1][x+2]] || com.mans[map[y+1][x+2]].my!=my)) d.push([x+2,y+1]);

//5点

if ( y+2<= 9 && x+1<= 8 && !play.map[y+1][x] &&(!com.mans[map[y+2][x+1]] || com.mans[map[y+2][x+1]].my!=my)) d.push([x+1,y+2]);

//7点

if ( y+2<= 9 && x-1>= 0 && !play.map[y+1][x] &&(!com.mans[map[y+2][x-1]] || com.mans[map[y+2][x-1]].my!=my)) d.push([x-1,y+2]);

//8点

if ( y+1<= 9 && x-2>= 0 && !play.map[y][x-1] &&(!com.mans[map[y+1][x-2]] || com.mans[map[y+1][x-2]].my!=my)) d.push([x-2,y+1]);

//10点

if ( y-1>= 0 && x-2>= 0 && !play.map[y][x-1] &&(!com.mans[map[y-1][x-2]] || com.mans[map[y-1][x-2]].my!=my)) d.push([x-2,y-1]);

//11点

if ( y-2>= 0 && x-1>= 0 && !play.map[y-1][x] &&(!com.mans[map[y-2][x-1]] || com.mans[map[y-2][x-1]].my!=my)) d.push([x-1,y-2]);

return d;

}

算法分析：

当马处于一点时，可以走的最多情况有8种方向，分别讨论每个方向：如果不绊马脚，且该方向上那着点没有棋子或棋子颜色不同，则记录该着点

图例分析：

有点丑，用画图做的，不要在意这些细节

(三)相

com.bylaw.x = function (x,y,map,my){

var d=[];

if (my===1){ //红方 颜色不同，y的取值范围不同，且不能过河

//4点半 不绊象脚 4.5位置没子或棋子颜色不同 push

if ( y+2<= 9 && x+2<= 8 && !play.map[y+1][x+1] && (!com.mans[map[y+2][x+2]] || com.mans[map[y+2][x+2]].my!=my)) d.push([x+2,y+2]);

//7点半

if ( y+2<= 9 && x-2>= 0 && !play.map[y+1][x-1] && (!com.mans[map[y+2][x-2]] || com.mans[map[y+2][x-2]].my!=my)) d.push([x-2,y+2]);

//1点半

if ( y-2>= 5 && x+2<= 8 && !play.map[y-1][x+1] && (!com.mans[map[y-2][x+2]] || com.mans[map[y-2][x+2]].my!=my)) d.push([x+2,y-2]);

//10点半

if ( y-2>= 5 && x-2>= 0 && !play.map[y-1][x-1] && (!com.mans[map[y-2][x-2]] || com.mans[map[y-2][x-2]].my!=my)) d.push([x-2,y-2]);

}else{

//4点半

if ( y+2<= 4 && x+2<= 8 && !play.map[y+1][x+1] && (!com.mans[map[y+2][x+2]] || com.mans[map[y+2][x+2]].my!=my)) d.push([x+2,y+2]);

//7点半

if ( y+2<= 4 && x-2>= 0 && !play.map[y+1][x-1] && (!com.mans[map[y+2][x-2]] || com.mans[map[y+2][x-2]].my!=my)) d.push([x-2,y+2]);

//1点半

if ( y-2>= 0 && x+2<= 8 && !play.map[y-1][x+1] && (!com.mans[map[y-2][x+2]] || com.mans[map[y-2][x+2]].my!=my)) d.push([x+2,y-2]);

//10点半

if ( y-2>= 0 && x-2>= 0 && !play.map[y-1][x-1] && (!com.mans[map[y-2][x-2]] || com.mans[map[y-2][x-2]].my!=my)) d.push([x-2,y-2]);

}

return d;

}

算法分析：

因为相不能过河，所以要按颜色分情况讨论(不同颜色，y坐标不同)

而每种颜色的相都有四种可能着法，与马类似：如果不绊象脚， 着点没有棋子或棋子颜色不同，记录

图例分析：

(四)士

com.bylaw.s = function (x,y,map,my){

var d=[];

if (my===1){ //红方

//4点半

if ( y+1<= 9 && x+1<= 5 && (!com.mans[map[y+1][x+1]] || com.mans[map[y+1][x+1]].my!=my)) d.push([x+1,y+1]);

//7点半

if ( y+1<= 9 && x-1>= 3 && (!com.mans[map[y+1][x-1]] || com.mans[map[y+1][x-1]].my!=my)) d.push([x-1,y+1]);

//1点半

if ( y-1>= 7 && x+1<= 5 && (!com.mans[map[y-1][x+1]] || com.mans[map[y-1][x+1]].my!=my)) d.push([x+1,y-1]);

//10点半

if ( y-1>= 7 && x-1>= 3 && (!com.mans[map[y-1][x-1]] || com.mans[map[y-1][x-1]].my!=my)) d.push([x-1,y-1]);

}else{

//4点半

if ( y+1<= 2 && x+1<= 5 && (!com.mans[map[y+1][x+1]] || com.mans[map[y+1][x+1]].my!=my)) d.push([x+1,y+1]);

//7点半

if ( y+1<= 2 && x-1>= 3 && (!com.mans[map[y+1][x-1]] || com.mans[map[y+1][x-1]].my!=my)) d.push([x-1,y+1]);

//1点半

if ( y-1>= 0 && x+1<= 5 && (!com.mans[map[y-1][x+1]] || com.mans[map[y-1][x+1]].my!=my)) d.push([x+1,y-1]);

//10点半

if ( y-1>= 0 && x-1>= 3 && (!com.mans[map[y-1][x-1]] || com.mans[map[y-1][x-1]].my!=my)) d.push([x-1,y-1]);

}

return d;

}

算法分析：

士不能出九宫格，x，y值都有限制。按颜色分情况讨论。每种颜色各有4中可能着法：如果该着点没棋子或棋子颜色不同，记录

图例分析：

这个简单了，就不画图了~ ~ ~ ~

(五)将

com.bylaw.j = function (x,y,map,my){

var d=[];

var isNull=(function (y1,y2){

var y1=com.mans["j0"].y; //红帅的y

var x1=com.mans["J0"].x; //黑将的x

var y2=com.mans["J0"].y; //黑将的y

for (var i=y1-1; i>y2; i--){

if (map[i][x1]) return false; //将与将之间非空，有子

}

return true;

})();

if (my===1){ //红方

//下

if ( y+1<= 9 && (!com.mans[map[y+1][x]] || com.mans[map[y+1][x]].my!=my)) d.push([x,y+1]);

//上

if ( y-1>= 7 && (!com.mans[map[y-1][x]] || com.mans[map[y-1][x]].my!=my)) d.push([x,y-1]);

//老将对老将的情况

if ( com.mans["j0"].x == com.mans["J0"].x &&isNull) d.push([com.mans["J0"].x,com.mans["J0"].y]); //x相等，且中间为空，push黑将的坐标

}else{

//下

if ( y+1<= 2 && (!com.mans[map[y+1][x]] || com.mans[map[y+1][x]].my!=my)) d.push([x,y+1]);

//上

if ( y-1>= 0 && (!com.mans[map[y-1][x]] || com.mans[map[y-1][x]].my!=my)) d.push([x,y-1]);

//老将对老将的情况

if ( com.mans["j0"].x == com.mans["J0"].x &&isNull) d.push([com.mans["j0"].x,com.mans["j0"].y]); //push红帅的坐标

}

//右

if ( x+1<= 5 && (!com.mans[map[y][x+1]] || com.mans[map[y][x+1]].my!=my)) d.push([x+1,y]);

//左

if ( x-1>= 3 && (!com.mans[map[y][x-1]] || com.mans[map[y][x-1]].my!=my))d.push([x-1,y]);

return d;

}

算法分析：

将除了颜色不同导致y值不同外，还有种特殊情况：即老将见面。所以开始先写个函数，判断将与帅之间是否有其他棋子

接下来按颜色不同分情况讨论上下两种着法：重点 是y值的界定。以帅为例：帅在棋盘下方，y坐标只能取7,8,9.如果向下走，则取7,8，所以y值最大为8.上与其类似。而判断完着法之后还要判断是否老将见面的特殊情况：如果两者x坐标相等且中间没其他棋子，之间闪现过去抢人头~ ~ ~然后victory

(六)，炮

com.bylaw.p = function (x,y,map,my){

var d=[];

//左侧检索

var n=0;

for (var i=x-1; i>= 0; i--){

if (map[y][i]) { //碰到子

if (n==0){ //若是第一个子，不用管，跳出本次循环，标记位加1

n++;

continue;

}else{ //若不是第一个子，判断颜色若不同，push过去并结束循环

if (com.mans[map[y][i]].my!=my) d.push([i,y]);

break

}

}else{ //若一直碰不到子，将子走到最左

if(n==0) d.push([i,y])

}

}

//右侧检索

var n=0;

for (var i=x+1; i <= 8; i++){

if (map[y][i]) {

if (n==0){

n++;

continue;

}else{

if (com.mans[map[y][i]].my!=my) d.push([i,y]);

break

}

}else{

if(n==0) d.push([i,y])

}

}

//上检索

var n=0;

for (var i = y-1 ; i >= 0; i--){

if (map[i][x]) {

if (n==0){

n++;

continue;

}else{

if (com.mans[map[i][x]].my!=my) d.push([x,i]);

break

}

}else{

if(n==0) d.push([x,i])

}

}

//下检索

var n=0;

for (var i = y+1 ; i<= 9; i++){

if (map[i][x]) {

if (n==0){

n++;

continue;

}else{

if (com.mans[map[i][x]].my!=my) d.push([x,i]);

break

}

}else{

if(n==0) d.push([x,i])

}

}

return d;

}

算法分析：

跟车一样，需要向4个方向上搜索

若该方向上没棋子，则记录该方向所有点坐标

若走着走着发现一个棋子，先冷静一下(跳出本次循环)，偷偷地看接下来该方向上有没有敌方棋子，有，就可以越塔gank了。然后把敌方死的位置记录下来留作纪念~ ~ ~

(七)卒

com.bylaw.z = function (x,y,map,my){

var d=[];

if (my===1){ //红方

//上

if ( y-1>= 0 && (!com.mans[map[y-1][x]] || com.mans[map[y-1][x]].my!=my)) d.push([x,y-1]);

//右

if ( x+1<= 8 && y<=4 && (!com.mans[map[y][x+1]] || com.mans[map[y][x+1]].my!=my)) d.push([x+1,y]); //y<4，即过河之后，才能左右移动

//左

if ( x-1>= 0 && y<=4 && (!com.mans[map[y][x-1]] || com.mans[map[y][x-1]].my!=my))d.push([x-1,y]);

}else{

//下

if ( y+1<= 9 && (!com.mans[map[y+1][x]] || com.mans[map[y+1][x]].my!=my)) d.push([x,y+1]);

//右

if ( x+1<= 8 && y>=6 && (!com.mans[map[y][x+1]] || com.mans[map[y][x+1]].my!=my)) d.push([x+1,y]);

//左

if ( x-1>= 0 && y>=6 && (!com.mans[map[y][x-1]] || com.mans[map[y][x-1]].my!=my))d.push([x-1,y]);

}

return d;

}

算法分析：

同样分情况讨论。且由于卒不能后退所以只用判断上，左，右三种情况。而卒由于过河后才能左右移动，所以左右的判断除了x的界定还有y值的界定。最后跟车一样如果该着点没有棋子或该棋子颜色不同，记录该点

二 ，使用alpha-beta在所有着法当中搜索最佳着法

AI.getAlphaBeta = function (A, B, depth, map ,my) {
if (depth == 0) {
return {"value":AI.evaluate(map , my)}; //当搜索深度为0是时调用局面评价函数;
}
var moves = AI.getMoves(map , my ); //生成全部走法;
//这里排序以后会增加效率
for (var i=0; i < moves.length; i++) {
//走这个走法;
var move= moves[i];
var key = move[4];
var oldX= move[0];
var oldY= move[1];
var newX= move[2];
var newY= move[3];
var clearKey = map[ newY ][ newX ]||"";
map[ newY ][ newX ] = key; //走，赋新值，删除旧值
delete map[ oldY ][ oldX ];
play.mans[key].x = newX;
play.mans[key].y = newY;
if (clearKey=="j0"||clearKey=="J0") { //被吃老将
play.mans[key].x = oldX;
play.mans[key].y = oldY;
map[ oldY ][ oldX ] = key;
delete map[ newY ][ newX ]; //并不是真的走，所以这里要撤销
if (clearKey){
map[ newY ][ newX ] = clearKey;
}
return {"key":key,"x":newX,"y":newY,"value":8888};
}else {
var val = -AI.getAlphaBeta(-B, -A, depth - 1, map , -my).value; //上面代表AI，这里倒置，-my，代表人的着法，然后再从上面开始执行
//val = val || val.value;
//撤消这个走法;
play.mans[key].x = oldX;
play.mans[key].y = oldY;
map[ oldY ][ oldX ] = key;
delete map[ newY ][ newX ];
if (clearKey){
map[ newY ][ newX ] = clearKey;
//play.mans[ clearKey ].isShow = true;
}
if (val >= B) {
//将这个走法记录到历史表中;
//AI.setHistoryTable(txtMap,AI.treeDepth-depth+1,B,my);
return {"key":key,"x":newX,"y":newY,"value":B};
}
if (val > A) {
A = val; //设置最佳走法，
if (AI.treeDepth == depth) var rootKey={"key":key,"x":newX,"y":newY,"value":A};
}
}
}
if (AI.treeDepth == depth) {//已经递归回根了
if (!rootKey){
//AI没有最佳走法，说明AI被将死了，返回false
return false;
}else{
//这个就是最佳走法;
return rootKey;
}
}
return {"key":key,"x":newX,"y":newY,"value":A};
}

简化后的伪代码(与上面代码一一对应)：

int AlphaBeta(int vlAlpha, int vlBeta, int nDepth) {

if (nDepth == 0) {

return 局面评价函数;

}

生成全部走法;

按历史表排序全部走法;

for (每个生成的走法) {

走这个走法;

if (被将军) {

撤消这个走法;

} else {

int vl = -AlphaBeta(-vlBeta, -vlAlpha, nDepth - 1);

撤消这个走法;

if (vl >= vlBeta) {

将这个走法记录到历史表中;

return vlBeta;

}

if (vl > vlAlpha) {

设置最佳走法;

vlAlpha = vl;

}

}

}

if (没有走过任何走法) { //AI被将死

return 杀棋的分数;

}

将最佳走法记录到历史表中;

if (根节点) {

最佳走法就是电脑要走的棋;

}

return vlAlpha;

}

最后设置坐标就可以实现AI自动走棋或吃子了
以上就是利用AI算法玩象棋的全部内容了

感谢大家支持 我是毕加锁 期待你的关注