一个JavaScript写的黑白棋AI

Love The Way You Lie 2022-02-05 08:17 318阅读 0赞

赖勇浩（http://laiyonghao.com）

首先，这个代码不是我写的，但注释是我加上去的。作者是shaofei cheng，他的网站：[http://shaofei.name][http_shaofei.name]

第二，目前这个代码只是使用了 alpha-beta 剪枝，棋力还弱，有很大的优化空间。但是代码写得非常清晰，如果有朋友对人机弈棋方面的课题有兴趣又还没有入门，这份代码作为一个例子是很棒的。

第三，目前计算机只能搜索 3 层，我觉得加上迭代深化和历史启发算法之后，搜索到 5 层是不成问题的。现代 JavaScript 的性能不错。

第四，作者在代码里展示了不少技巧，值得学习和借鉴，哪怕不懂 JavaScript 也很容易看懂代码（我也不懂)。

第五，试试这个 AI 的棋力：[http://shaofei.name/OthelloAI/othello.html][http_shaofei.name_OthelloAI_othello.html]

以下是代码：

var AI = \{\};new function()\{AI.Pattern= pattern;// 定义了 8 个偏移量// 可以简单通过加法得到任一点周围 8 个点的坐标// -11 -10 -9//  -1  x  1//  9   10 11// 如左上角的坐标为 x + (-11)var directions=\[-11,-10,-9,-1,1,9,10,11\];function pattern()\{ // 把整个棋盘填满 0 for(var i=0;i<100;i++)this\[i\]=0; // 中间的 4 个格子，先放上两黑两白的棋子 this\[54\]=this\[45\]=1;this\[55\]=this\[44\]=2; // 黑净胜外围子数目（黑减去白），估值时用。  this.divergence=0; // 当前可走棋方为黑棋 this.color=1; // 已经走了几步棋 this.moves=0; // 稳定原型 // 0 是空白，1 是黑棋，2 是白棋，3 是边界 // 把 8 \* 8 的棋盘扩展成 10 \* 10，是一种技巧 // 可以简化坐标有效性的判断 var stableProto = \[   3, 3, 3, 3, 3, 3, 3, 3, 3, 3,  3, 0, 0, 0, 0, 0, 0, 0, 0, 3,  3, 0, 0, 0, 0, 0, 0, 0, 0, 3,  3, 0, 0, 0, 0, 0, 0, 0, 0, 3,  3, 0, 0, 0, 0, 0, 0, 0, 0, 3,  3, 0, 0, 0, 0, 0, 0, 0, 0, 3,  3, 0, 0, 0, 0, 0, 0, 0, 0, 3,  3, 0, 0, 0, 0, 0, 0, 0, 0, 3,  3, 0, 0, 0, 0, 0, 0, 0, 0, 3,  3, 3, 3, 3, 3, 3, 3, 3, 3, 3 \] // 从一个 8 \* 8 的棋盘载入状态 this.load=function(arr) \{  for(var y=1;y<=8;y++)  \{   for(var x=1;x<=8;x++)   \{    this\[y\*10+x\]=arr\[y-1\]\[x-1\];      \}  \} \} // 判断能不能 pass // 如果能，则当前可走棋方变更 this.pass=function() \{  for(var y=1;y<=8;y++)  \{   for(var x=1;x<=8;x++)   \{    if(this\[y\*10+x\]==0)     \{     // 有任何一步棋可走，都不可以 Pass     if(this.move(x,y,this.color))     \{      return false;     \}    \}        \}  \}  //alert("pass");  // 这是一个技巧，因为 this.color 的值域是 \{1, 2\}  // 所以当 color 是 1 时，执行完下一语句后就是 2  // 当 color 是 2 时，执行完下一语句后就是 1  this.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\[this\[y\*10+x\]\]+" ";    //r+=stableDiscs\[y\*10+x\]+" ";   \}   r+="/n";  \}  return r+this.exact(); \}  // 净胜子数 this.exact=function() \{  // 这里是一个技巧， r\[0\] 是不使用的，r\[1\] r\[2\] 对应黑白棋子的个数  var r=\[0,0,0\];  for(var y=1;y<=8;y++)  \{   for(var x=1;x<=8;x++)   \{    r\[this\[y\*10+x\]\]++; // 数目加一   \}  \}  // 当前颜色的数量为 0，输了，返回负极值  if(r\[this.color\]==0) return -64;  // 敌对颜色的数量为 0，赢了，返回极值  if(r\[3-this.color\]==0) return 64;  // 返回当前走棋方比对方多的数量  return r\[this.color\]-r\[3-this.color\]; \} // 对棋盘的估值 this.calculate=function() \{  // 基本估值方法：  // 1、能占棋盘四角是很有价值的  // 2、邻近棋盘四角的位子是很差的  // 3、稳定子  // 4、外围子净胜数  var r=\[0,0,0\];  var r=this.divergence;  // 如果左上角有棋子，自己的，就+30分，敌方的，-30 分   if(this\[11\]) r+=((this\[11\]==this.color)?1:-1)\*30;    // 次左上角，分值是 -15  else if(this\[22\]==this.color)r-=15;  // 右上角，分值 30  if(this\[18\])r+=((this\[18\]==this.color)?1:-1)\*30;  // 次右上角，分值 -15  else if(this\[27\]==this.color)r-=15;  // 左下角，分值 30  if(this\[81\])r+=((this\[81\]==this.color)?1:-1)\*30;  // 次左下角，分值 -15  else if(this\[72\]==this.color)r-=15;  // 右下角，分值 30  if(this\[88\])\{r+=((this\[88\]==this.color)?1:-1)\*30;\}  // 次右下角，分值 -15  else if(this\[77\]==this.color)r-=15;  // 查找稳定子，  // 稳定子就是挨着 4 个角点并且周边的棋子要么是同色，要么是边界  //var color = this.color;  var stableDiscs=stableProto.slice();    var queue = \[\];  if(this\[11\]!=0) queue.push(\[11,this\[11\]\]);  if(this\[18\]!=0) queue.push(\[18,this\[18\]\]);  if(this\[81\]!=0) queue.push(\[81,this\[81\]\]);  if(this\[88\]!=0) queue.push(\[88,this\[88\]\]);  while(queue.length)  \{   var position = queue\[0\]\[0\];   var c = queue\[0\]\[1\];   // 不懂 JS 的数组的内存管理算法，不过感觉从头上删除肯定是比较慢的，   // 我感觉从后面删除会更好，或者使用标记不删除的方法性能会更好   queue.shift();   //if(stableDiscs\[position\]==0 || stableDiscs\[position\]==3) continue;   stableDiscs\[position\] = c;   if( (stableDiscs\[position-10\]==3 || stableDiscs\[position+10\]==3  || stableDiscs\[position-10\] == c || stableDiscs\[position+10\] == c) &&    (stableDiscs\[position-1\]==3 || stableDiscs\[position+1\]==3  || stableDiscs\[position-1\] == c || stableDiscs\[position+1\] == c) &&    (stableDiscs\[position-11\]==3 || stableDiscs\[position+11\]==3  || stableDiscs\[position-11\] == c || stableDiscs\[position+11\] == c) &&    (stableDiscs\[position-9\]==3 || stableDiscs\[position+9\]==3  || stableDiscs\[position-9\] == c || stableDiscs\[position+9\] == c) )   \{    stableDiscs\[position\]=c;    // 稳定子的分值为 7    r += ((c==this.color)?1:-1)\*7;    // 进一步扩展，查找稳定子    for(var i = 0;i <directions.length ; i++)     if(stableDiscs\[directions\[i\]+position\]==0 && this\[directions\[i\]+position\]==c)      queue.push(\[directions\[i\]+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\[y\*10+x\]!=0)r+=(this\[y\*10+x\]==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\[y\*10+x\])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(\[x,y\]+":"+v);     \}     // 离四个角最近的那 3 \* 4 个格子，则多搜索一层     // 因为对手可能在下一手下在角上，会出现大翻盘。     else if( (x==2||x==7) && (y==2||y==7) )      var v=-tmp.search(-Infinity,Infinity,depth+1);     else      var v=-tmp.search(-Infinity,Infinity,depth);     // 还不如之前的棋步     if(v<max)continue;     // 比之前的棋步好     if(v>max)\{      // 保存起来      r=\[\[x,y\]\];max=v;     \}     // 另一个可选的棋步     else r.push(\[x,y\]);    \}   \}  \}  // 在所有可选的棋步中，随机选择一个，让玩家觉得比较多变化，不那么单调。  var tmp=Math.floor(Math.random()\*r.length);  return r\[tmp\]; \} // 搜索算法 // 使用负极大值形式的 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\[y\*10+x\]!=0)r+=(this\[y\*10+x\]==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\[y\*10+x\]!=0);//r+=(this\[y\*10+x\]==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 颜色的棋子，成功返回下一棋盘状态，否则返回 null this.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\[10\*y+x\]!=0)return null;  // 8 方向判断  for(var i=0;i<8;i++)  \{   // 转换为一维索引   var p=10\*y+x+directions\[i\];   // 邻近的格子上棋子不同色   if(pattern\[p\]==3-this.color)    while(pattern\[p\]!=0)    \{     // 往同方向搜索     p+=directions\[i\];        // 另一端还有一个自己的棋子，则是一个可走的点。     if(pattern\[p\]==this.color)     \{      canmove=true;      // 把中间的棋子翻过来      while((p+=-directions\[i\])!=10\*y+x)      \{       pattern\[p\]=this.color;       //alert(p);       for(var d=0;d<8;d++)       \{        // 非空        if(!pattern\[p+directions\[d\]\]                // 非边界                &&p+directions\[d\]>10                &&p+directions\[d\]<89                &&(p+directions\[d\])%10!=0                &&(p+directions\[d\])!=9)            // 外围净胜子数增加            pattern.divergence++;       \}      \}      break;     \}    \}  \}  // 返回新的棋盘状态  if(canmove)\{pattern\[10\*y+x\]=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));\}()

[http_shaofei.name]: http://shaofei.name
[http_shaofei.name_OthelloAI_othello.html]: http://shaofei.name/OthelloAI/othello.html

发表评论取消回复

表情：

评论列表（有 0 条评论，318人围观）

还没有评论，来说两句吧...

相关阅读

相关 c++写一个红黑树代码

这是一段红黑树的 C 代码的例子： \`\`\` \include <stdio.h> \include <stdlib.h> // 定义红黑树的节点 typedef st

小咪咪/ 2024年03月27日 12:10/ 0 赞/ 90 阅读

相关基于Python的强化学习的黑白棋人工智能实验

目录人工智能实验：强化学习实验报告 1 一、基本原理 1 1.1 强化学习 1 1.2 Q学习方法 2 2. 流程图和伪代码 2 3. 代码展示 5

ゝ一世哀愁。/ 2024年03月27日 11:09/ 0 赞/ 114 阅读

相关写一个ai博客助手

好的，我来为你介绍一下 AI 博客助手。 AI 博客助手是一种使用人工智能技术的博客软件，它能够帮助用户更快、更高效地写作，并且可以提供更深入的内容分析。主要功能包括：

朱雀/ 2023年10月08日 20:12/ 0 赞/ 53 阅读

相关如何写一个游戏AI（一）

由于目前游戏的ai最后两手牌打的不尽人意，而手头上的工作又暂时弄完了。就被安排去学习AI，最终目标是重新训练/优化现有的AI。而这只是我的记录，仅仅是偏向我的应用

朱雀/ 2023年03月03日 08:54/ 0 赞/ 195 阅读

相关 c#黑白棋算法_黑白棋C#源代码

namespace WindowsApplication1 \{ partial class Form1 \{ /// /// 必需的设计器变量。 /// pri

秒速五厘米/ 2022年11月03日 05:46/ 0 赞/ 149 阅读

相关 c语言黑白棋报告,C语言黑白棋游戏[转载]

该楼层疑似违规已被系统折叠隐藏此楼查看此楼 else if(k==75&&x>100) \{CoverBlock(x,y);x-=10;PicBlock(x,y);\}

秒速五厘米/ 2022年10月14日 10:57/ 0 赞/ 226 阅读

相关剪枝计算机,α-β剪枝 - 电脑黑白棋 - 黑白棋天地

α-β剪枝算法前面介绍的基本搜索算法，在实际应用是是十分费时的，因为它需要考虑所有可能的棋步。有研究表明，在黑白棋的中盘阶段，平均每个局面大约有10步棋可供选择\[1\]。

布满荆棘的人生/ 2022年09月01日 15:55/ 0 赞/ 218 阅读

相关黑白棋游戏

/黑白棋游戏/ include <iostream> include <stdio.h> include <stdlib.h> incl

忘是亡心i/ 2022年06月12日 01:28/ 0 赞/ 217 阅读

相关 UVA - 220 Othello（黑白棋）

就是模拟。。代码： include <bits/stdc++.h> using namespace std; int xx[] = {

落日映苍穹つ/ 2022年05月07日 21:12/ 0 赞/ 204 阅读

相关一个JavaScript写的黑白棋AI

赖勇浩（http://laiyonghao.com）首先，这个代码不是我写的，但注释是我加上去的。作者是shaofei cheng，他的网

Love The Way You Lie/ 2022年02月05日 08:17/ 0 赞/ 319 阅读