中国象棋AI实现 |
您所在的位置：网站首页 › 单机中国象棋人机对战下载 › 中国象棋AI实现 |
中国象棋AI实现
|
中国象棋AI实现——alpha-beta剪枝
一、简介
这是基于alpha-bata剪枝算法实现的一个中国象棋博弈程序，可以实现人机交互，AI具有初级的智能，可以应对一般的象棋新手。 界面用最基本的html+css+js实现，参考自中国象棋界面素材 AI逻辑同样用js实现，项目地址。
在让AI自动做出落子决定前，必须提供一个方法让其判断哪种走法较优，也即需要一个局面评估函数，能够返回一个表示局面好坏的分数，对于AI方，这个分数越大越好。 //有一点需要强调：alpha-beta剪枝过程中走棋的双方可能会变化，但估分的标准一直是以黑方即AI方为准，黑方希望估值最大，红方希望估值最小。 function evaluate() { var score = 0; score += SingleChessScore(); score += ChouJu(); score += ShuangPao(); return score; }目前的局面评估只包括一个主要部分和两个分支部分，分别为单棋子棋力判断、抽车将军判断和双炮将军判断，后续可能会在github仓库上更新更多的局面评估方法。 主要部分SingleChessScore依次考虑棋面上每个单独的子，由它们本身的属性和所在位置决定它们的分数，黑方取正值，红方取负值，并累加起来。 棋力表部分参考自eleeye。 以马的分数表为例，马的分数表如下： var Ma = [ [90, 90, 90, 96, 90, 96, 90, 90, 90], [90, 96,103, 97, 94, 97,103, 96, 90], [92, 98, 99,103, 99,103, 99, 98, 92], [93,108,100,107,100,107,100,108, 93], [90,100, 99,103,104,103, 99,100, 90], [90, 98,101,102,103,102,101, 98, 90], [92, 94, 98, 95, 98, 95, 98, 94, 92], [93, 92, 94, 95, 92, 95, 94, 92, 93], [85, 90, 92, 93, 78, 93, 92, 90, 85], [88, 50, 90, 88, 90, 88, 90, 50, 88]//马的两个初始位置权值设小一点，防止AI的炮“盲目攻击马” ];有了棋面评估函数，AI现在可以遍历每一个己方棋子的每一种走法，并判断该走法的分数，基于这个，已经可以实现一个贪心算法，该算法只考虑当前的一步，并选择对自己最有利的走法。 V1.0 贪心算法，AI是黑方 function AImove() { var max_score = -100000000; var from = []; var to = []; var can_eat = false; for (var j = 0; j if (map[j][i] for(var q=0;q from[0] = j; from[1] = i; to[0] = dest[0]; to[1] = dest[1]; max_score = score; can_eat = tmp == 0 ? false : true; } map[j][i] = map[dest[0]][dest[1]]; map[dest[0]][dest[1]] = tmp; } } } } } console.log("now best: " + max_score); if (can_eat) { eat(from[0], from[1], to[0], to[1]); } else { move(from[0], from[1], to[0], to[1]); } }显然，这样的AI智能还不够，所以下一步我们用alpha-beta对其进行优化，使其能考虑接下来几步内的较优走法。 算法框架如下： function alpha-beta(depth, alpha, beta) { 对于每一个棋子的每一种走法 修改局面为该走法落子后的局面 ret = alpha-beta(depth + 1, alpha, beta) 修改局面回落子前的局面 if 在MAX层, alpha = max(alpha, ret) else if 在MIN层, beta = min(beta, ret) if beta eat(AIfrom[0], AIfrom[1], AIto[0], AIto[1]); } else { move(AIfrom[0], AIfrom[1], AIto[0], AIto[1]); } } var AIfrom = []; var AIto = []; var AIcan_eat = false; function alpha_beta(depth, alpha, beta) { if (depth >= 5) return evaluate(map); for (var j = 0; j if ((depth & 1) == 1 && map[j][i] 0) {//哪些棋子能走 var t = WhatSpace(j, i);//返回棋子的属性 var tmap = WhereCan(j,i,t);//返回能走的位置，分为能吃和不能吃（即目的棋子或空） if(tmap!=null && tmap.length>0) { for(var q=0;q if (ret > alpha) { alpha = ret; if (depth == 1) { AIfrom[0] = j; AIfrom[1] = i; AIto[0] = dest[0]; AIto[1] = dest[1]; AIcan_eat = !(tmp == 0); } } } else { beta = Math.min(beta, ret); } map[j][i] = map[dest[0]][dest[1]]; map[dest[0]][dest[1]] = tmp; if (beta if (depth == 1) { console.log(j + '-' + i + getCText(dest[0],dest[1])[0] + "移动到 " + dest[0] + '-' + dest[1]) //如果新的最好结果比原最好结果只大了5分以内，以某种概率保持原最好结果，以提高随机性 if (ret - alpha 0.8) { console.log("跨过最优解法"); map[j][i] = map[dest[0]][dest[1]]; map[dest[0]][dest[1]] = tmp; continue; } AIfrom[0] = j; AIfrom[1] = i; AIto[0] = dest[0]; AIto[1] = dest[1]; AIcan_eat = !(tmp == 0); } alpha = ret; } //console.log(j + " " + i + " " + "alpha: " + alpha); }为了提高玩家体验，增加了悔棋功能。 用一个栈保存之前走过的所有步数，每次悔棋从栈中弹出并恢复。 三、结果分析alpha-beta剪枝层数大于4时，AI表现出较好的智能，能够与普通人类进行对战且有较大的胜算。由于象棋游戏本身有较大的不确定性，因此以下结果仅供参考。 对战局数AI获胜局数胜率10880% 搜索深度每步用时4 |
【本文地址】
今日新闻 |
推荐新闻 |