一个JavaScript写的黑白棋AI
赖勇浩（http://laiyonghao.com）首先，这个代码不是我写的，但注释是我加上去的。作者是shaofei cheng，他的网站：http://shaofei.name
第二，目前这个代码只是使用了 alpha-beta 剪枝，棋力还弱，有很大的优化空间。但是代码写得非常清晰，如果有朋友对人机弈棋方面的课题有兴趣又还没有入门，这份代码作为一个例子是很棒的。
第三，目前计算机只能搜索 3 层，我觉得加上迭代深化和历史启发算法之后，搜索到 5 层是不成问题的。现代 JavaScript 的性能不错。
第四，作者在代码里展示了不少技巧，值得学习和借鉴，哪怕不懂 JavaScript 也很容易看懂代码（我也不懂)。
第五，试试这个 AI 的棋力：http://shaofei.name/OthelloAI/othello.html
以下是代码：
var AI = {};new function(){AI.Pattern= pattern;// 定义了 8 个偏移量// 可以简单通过加法得到任一点周围 8 个点的坐标// -11 -10 -9//-1x1//9 10 11// 如左上角的坐标为 x + (-11)var directions=[-11,-10,-9,-1,1,9,10,11];function pattern(){// 把整个棋盘填满 0for(var i=0;i<100;i++)this=0;// 中间的 4 个格子，先放上两黑两白的棋子this=this=1;this=this=2;// 黑净胜外围子数目（黑减去白），估值时用。 this.divergence=0;// 当前可走棋方为黑棋this.color=1;// 已经走了几步棋this.moves=0;// 稳定原型// 0 是空白，1 是黑棋，2 是白棋，3 是边界// 把 8 * 8 的棋盘扩展成 10 * 10，是一种技巧// 可以简化坐标有效性的判断var stableProto = // 从一个 8 * 8 的棋盘载入状态this.load=function(arr){for(var y=1;y<=8;y++){for(var x=1;x<=8;x++){this=arr; }}}// 判断能不能 pass// 如果能，则当前可走棋方变更this.pass=function(){for(var y=1;y<=8;y++){for(var x=1;x<=8;x++){if(this==0) {// 有任何一步棋可走，都不可以 Passif(this.move(x,y,this.color)){return false;}} }}//alert("pass");// 这是一个技巧，因为 this.color 的值域是 {1, 2}// 所以当 color 是 1 时，执行完下一语句后就是 2// 当 color 是 2 时，执行完下一语句后就是 1this.color = 3 - this.color;return true;}this.clone=function(){function pattern(){}pattern.prototype=this;return new pattern();}this.toString=function(){var icon=[" ","*","o"]var r="";for(var y=1;y<=8;y++){for(var x=1;x<=8;x++){r+=icon]+" ";//r+=stableDiscs+" ";}r+="\n";}return r+this.exact();}// 净胜子数this.exact=function(){// 这里是一个技巧， r 是不使用的，r r 对应黑白棋子的个数var r=;for(var y=1;y<=8;y++){for(var x=1;x<=8;x++){r]++; // 数目加一}}// 当前颜色的数量为 0，输了，返回负极值if(r==0) return -64;// 敌对颜色的数量为 0，赢了，返回极值if(r==0) return 64;// 返回当前走棋方比对方多的数量return r-r;}// 对棋盘的估值this.calculate=function(){// 基本估值方法：// 1、能占棋盘四角是很有价值的// 2、邻近棋盘四角的位子是很差的// 3、稳定子// 4、外围子净胜数var r=;var r=this.divergence;// 如果左上角有棋子，自己的，就+30分，敌方的，-30 分if(this)r+=((this==this.color)?1:-1)*30; // 次左上角，分值是 -15else if(this==this.color)r-=15;// 右上角，分值 30if(this)r+=((this==this.color)?1:-1)*30;// 次右上角，分值 -15else if(this==this.color)r-=15;// 左下角，分值 30if(this)r+=((this==this.color)?1:-1)*30;// 次左下角，分值 -15else if(this==this.color)r-=15;// 右下角，分值 30if(this){r+=((this==this.color)?1:-1)*30;}// 次右下角，分值 -15else if(this==this.color)r-=15;// 查找稳定子，// 稳定子就是挨着 4 个角点并且周边的棋子要么是同色，要么是边界//var color = this.color;var stableDiscs=stableProto.slice();var queue = [];if(this!=0) queue.push(]);if(this!=0) queue.push(]);if(this!=0) queue.push(]);if(this!=0) queue.push(]);while(queue.length){var position = queue;var c = queue;// 不懂 JS 的数组的内存管理算法，不过感觉从头上删除肯定是比较慢的，// 我感觉从后面删除会更好，或者使用标记不删除的方法性能会更好queue.shift();//if(stableDiscs==0 || stableDiscs==3) continue;stableDiscs = c;if( (stableDiscs==3 || stableDiscs==3|| stableDiscs == c || stableDiscs == c) &&(stableDiscs==3 || stableDiscs==3|| stableDiscs == c || stableDiscs == c) &&(stableDiscs==3 || stableDiscs==3|| stableDiscs == c || stableDiscs == c) &&(stableDiscs==3 || stableDiscs==3|| stableDiscs == c || stableDiscs == c) ){stableDiscs=c;// 稳定子的分值为 7r += ((c==this.color)?1:-1)*7;// 进一步扩展，查找稳定子for(var i = 0;i <directions.length ; i++)if(stableDiscs+position]==0 && this+position]==c)queue.push(+position,c]);}}// 返回估值return r;}this.toLocalString=function(depth){var r="";if(!depth)depth=0;for(var y=1;y<=8;y++){for(var x=1;x<=8;x++){if(this!=0)r+=(this==1?"*":"o")+" ";else {var tmp=this.move(x,y,this.color);if(tmp){var tmp2=-tmp.search(-Infinity,Infinity,depth);if(tmp2<0||tmp2>9)r+=tmp2;else r+=" "+tmp2;}else r+="X ";} }r+="\n";}return r+this.exact();}// 计算机去找一步可走的棋步// 这里 AI 部分的入口this.computer=function(depth,exactDepth){if(!depth)depth=0;if(!exactDepth)exactDepth=depth;var r=[];var max=-Infinity;for(var y=1;y<=8;y++){for(var x=1;x<=8;x++){if(this)continue;// 找到一个空白格子else {// 尝试走这个格子var tmp=this.move(x,y,this.color);// 不成功，非法if(!tmp)continue;// 已走步数+已搜索深度 >= 有 60 步// 这时使用精确搜索得到更精确的结果if(this.moves+exactDepth>=60){var v=-tmp.exactSearch(-Infinity,Infinity);//alert(+":"+v);}// 离四个角最近的那 3 * 4 个格子，则多搜索一层// 因为对手可能在下一手下在角上，会出现大翻盘。else if( (x==2||x==7) && (y==2||y==7) )var v=-tmp.search(-Infinity,Infinity,depth+1);elsevar v=-tmp.search(-Infinity,Infinity,depth);// 还不如之前的棋步if(v<max)continue;// 比之前的棋步好if(v>max){// 保存起来r=[];max=v;}// 另一个可选的棋步else r.push();}}}// 在所有可选的棋步中，随机选择一个，让玩家觉得比较多变化，不那么单调。var tmp=Math.floor(Math.random()*r.length);return r;}// 搜索算法// 使用负极大值形式的 Alpha-Beta 剪枝搜索算法this.search=function(alpha,beta,depth,pass){// 叶子节点，返回估值if(depth==0)return this.calculate();var canmove=false;for(var y=1;y<=8;y++){for(var x=1;x<=8;x++){if(this!=0)r+=(this==1?"*":"o")+" ";else {var tmp=this.move(x,y,this.color);if(!tmp)continue;canmove=true;// 往更深搜索var r=-tmp.search(-beta,-alpha,depth-1);//if(depth==4)WScript.echo(r);// 收窗窗口if(r>=alpha)alpha=r;// 胜着if(alpha>beta)return Infinity;}}}// 返回当前局面的最佳着法估值if(canmove)return alpha;// 双方都没有可下子之处，返回净胜子数 if(pass) return this.exact();// pass 一次，往深搜索this.color=3-this.color;return -this.search(-beta,-alpha,depth-1,true);}// 精确搜索，这段的算法原理跟 search 是一样的this.exactSearch=function(alpha,beta,pass){// 已经走了 60 步了，返回净胜子数if(this.moves==60)return this.exact();var canmove=false;for(var y=1;y<=8;y++){for(var x=1;x<=8;x++){if(this!=0);//r+=(this==1?"*":"o")+" ";else {var tmp=this.move(x,y,this.color);if(!tmp)continue;canmove=true;var r=-tmp.exactSearch(-beta,-alpha);if(r>=alpha)alpha=r;if(alpha>beta)return Infinity;}}}if(canmove)return alpha;if(pass)return this.exact();this.color=3-this.color;return -this.exactSearch(-beta,-alpha,true);}// 尝试在 x, y 放下 this.color 颜色的棋子，成功返回下一棋盘状态，否则返回 nullthis.move=function(x,y){// 复制当前状态var pattern=this.clone();pattern.color=3-this.color;// 注意这个负号pattern.divergence=-pattern.divergence;// move 数++pattern.moves++;var canmove;canmove=false;// 放在函数入口处，可以优化性能// 把 10*y+x 放入临时变量可优化性能if(pattern!=0)return null;// 8 方向判断for(var i=0;i<8;i++){// 转换为一维索引var p=10*y+x+directions;// 邻近的格子上棋子不同色if(pattern==3-this.color)while(pattern!=0){// 往同方向搜索p+=directions; // 另一端还有一个自己的棋子，则是一个可走的点。if(pattern==this.color){canmove=true;// 把中间的棋子翻过来while((p+=-directions)!=10*y+x){pattern=this.color;//alert(p);for(var d=0;d<8;d++){// 非空if(!pattern]// 非边界&&p+directions>10&&p+directions<89&&(p+directions)%10!=0&&(p+directions)!=9)// 外围净胜子数增加pattern.divergence++;}}break;}}}// 返回新的棋盘状态if(canmove){pattern=this.color;return pattern;}else return null;}}//pattern.prototype = emptyboard;//WScript.echo(new pattern().move(5,6).move(6,4).move(4,3).move(3,4).toLocalString(3));//WScript.echo(new pattern().move(5,6).search(-Infinity,Infinity,2));}()
页:
[1]