五子棋AI(下)——AI篇

一 概览

很喜欢动画电影,所以给AI取了一个自己很喜欢的电影人物的名字——瓦力。实现AI的过程其实就是让瓦力模仿人思考的过程,人在五子棋对弈的时候想的事情基本如下:

  1. 是不是到我下棋了

  2. 判断当前棋盘的输赢情况

  3. 没有人赢,那么(1)棋盘上还有哪些位置我可以落子这一步棋(2)我下在哪个位置最可能让自己赢(最难想的部分)


二 分点攻破,代码实现

思路是按我实现的时候的递进型的讲解,会有前面的实现思路被后面的推翻更进的部分。没有一次到位地写的原因是觉得这样读者看起来会比较能理解最后的结果是怎么一步一步想过来的。

2.1 唤醒瓦力宝宝,让瓦力学会找个空白的地方落子

这一步很简单,在棋盘的onclick事件中将瓦力落子的逻辑加进去,每次用户落子后瓦力都自动落在。判断空白点的方式也很简单,用一个count二维数组记录所有的棋盘坐标,未落子的坐标对应值为0,用户落子的坐标对应值为1,瓦力落子的坐标对应值为2。

//为对象添加瓦力的初级AI方法,这一步只实现落子,为了看效果用的
wallEAI: function () {
   //随便找个可以落子的点
   while (1) {
      x = Math.floor(Math.random()*10) + Math.floor(Math.random()*6);
      y = Math.floor(Math.random()*10) + Math.floor(Math.random()*6);
      if (this.count[x][y] == 0) {
         break;
      }
   }

   this.oneStep(x, y, this.me);  //瓦力落子
   this.count[x][y] = 2;     //瓦力落子的点我们记为2
   this.me = !this.me;
}

//用户落子绑定事件中添加瓦力落子的逻辑
_this.chess.onclick = function (e) {
   //判断对局是否完成或是否是轮到挑战者下棋,对局完成和不是挑战者下棋就会跳出循环
   if(_this.over || this.me == false) return;

   //获取鼠标点击位置坐标,并转换为落点坐标
   var x = e.offsetX,
      y = e.offsetY;

   x = Math.floor(x / 30);
   y = Math.floor(y / 30);

   //判断当前落点是否已有棋子,如果没有则落子成功
   if (_this.count[x][y] === 0) {
      _this.oneStep(x, y, _this.me);
      _this.count[x][y] = 1;
      _this.me = !_this.me;

      //判断对弈是否结束,如果没结束换成瓦力下棋
      if (_this.over === false &&  _this.me === false) {
         _this.wallEAI();
      }
   }
};

2.2 调教瓦力,让瓦力学会判断胜负

每次落子的时候都以当前落子点在横竖线,正斜线,反斜线遍历一下,如果有一条线的同颜色连续棋子数大于等于5说明当前的落子方赢了。

winnerCheck: function (x, y, chessType) {
   //设置每个方向的连子计数
   var countLeftRight = 0;
   var countUpDown = 0;
   var countUpperLeftToLowerRight = 0;//左上到右下
   var countUpperRightToLowerLeft = 0;//右上到左下

   //左右判断
   for (var i = x; i >= 0; i--) {
      if (this.count[i][y] != chessType) {
         break;
      }
      countLeftRight++;

      if (countLeftRight >= 5) return true;//设置该局已经获胜,不可以再走了
   }
   for (var i = x + 1; i < 15; i++) {
      if (this.count[i][y] != chessType) {
         break;
      }
      countLeftRight++;

      if (countLeftRight >= 5) return true;//设置该局已经获胜,不可以再走了
   }

   //上下判断
   for (var i = y; i >= 0; i--) {
      if (this.count[x][i] != chessType) {
         break;
      }
      countUpDown++;

      if (countUpDown >= 5) return true;//设置该局已经获胜,不可以再走了
   }
   for (var i = y + 1; i < 15; i++) {
      if (this.count[x][i] != chessType) {
         break;
      }
      countUpDown++;

      if (countUpDown >= 5) return true;//设置该局已经获胜,不可以再走了
   }

   //左上右下判断
   var t = y;
   var w = y + 1;
   for (var i = x; i >= 0; i--) {
      if (this.count[i][t] != chessType) {
         break;
      }
      if (t >= 0) {
         t = t - 1;
      }
      countUpperLeftToLowerRight++;

      if (countUpperLeftToLowerRight >= 5) return true;//设置该局已经获胜,不可以再走了
   }
   for (var i = x + 1; i < 15; i++) {
      if (this.count[i][w] != chessType) {
         break;
      }
      if (w < 15) {
         w = w + 1;
      }
      countUpperLeftToLowerRight++;

      if (countUpperLeftToLowerRight >= 5) return true;//设置该局已经获胜,不可以再走了
   }

   //右上左下判断
   var h = y;
   var z = y + 1;
   for (var i = x; i < 15; i++) {
      if (this.count[i][h] != chessType) {
         break;
      }
      if (h >= 0) {
         h--;
      }
      countUpperRightToLowerLeft++;

      if (countUpperRightToLowerLeft >= 5) return true;//设置该局已经获胜,不可以再走了
   }
   for (var i = x - 1; i >= 0; i--) {
      if (this.count[i][z] != chessType) {
         break;
      }
      if (z <= 15) {
         z++;
      }
      countUpperRightToLowerLeft++;

      if(countUpperRightToLowerLeft >= 5) return true;//设置该局已经获胜,不可以再走了
   }

   return false; //没有获胜
}

2.3 深度调教瓦力,让瓦力学会寻找最佳落子点

要让瓦力学会像人一样去寻找最佳落子点,我们就得剖析一下作为智能人的我们在寻找落子点的时候是如何考虑的,并尝试将这些考虑转化为瓦力可以识别的代码。

(1)我们首先会分析自己的棋子在棋盘上的布局,假设现在我们的棋子已经在某条线上4子成线,那这个时候这四子首尾可落子的点便是我们这次的最佳落子点——引出问题:要让瓦力可以识别当前的棋局上自己的棋子的排布情况,并能识别排布命中的赢法——设一个三维数组记下所有的赢法,设一个统计数组wallEWin记录瓦力的落子情况,瓦力每次落子(x,y)的时候均将这次落子命中的赢法更新到统计数组中,例 wallEWin[2] = 3,表示瓦力已经在第2种赢法上落了两颗子

(2)我们还会分析对手的棋子排布情况,当对手有可能比我们更快成功的时候我们应该去围堵对手的棋子——引出问题:瓦力还得知道对手的棋子排布——给对手也设一个落子统计数组myWin,对手每次落子(x,y)的时候均将这次落子命中的赢法更新到统计数组中,例 myWin[5] = 3,表示对手已经在第5种赢法上落了两颗子

2.3.1 赢法数组实现
analysis: function () {
   //赢法数组 wins初始化
   for (var i = 0; i < 15; i++) {
      this.wins[i] = [];
      for (var j = 0; j < 15; j++) {
         this.wins[i][j] = [];
      }
   }

   //赢法总类统计 winCount 统计各类赢法总数 共计572种

   for (var i = 0; i < 15; i++) {//横
      for (var j = 0; j < 11; j++) {
         for (var k = 0; k < 5; k++) {
            this.wins[i][j + k][this.winCount] = true;
         }
         this.winCount++;
      }
   }
   for (var i = 0; i < 15; i++) {//竖
      for (var j = 0; j < 11; j++) {
         for (var k = 0; k < 5; k++) {
            this.wins[j + k][i][this.winCount] = true;
         }
         this.winCount++;
      }
   }
   for (var i = 0; i < 11; i++) {//斜
      for (var j = 0; j < 11; j++) {
         for (var k = 0; k < 5; k++) {
            this.wins[i + k][j + k][this.winCount] = true;
         }
         this.winCount++;
      }
   }
   for (var i = 0; i < 11; i++) {//反斜
      for (var j = 14; j > 3; j--) {
         for (var k = 0; k < 5; k++) {
            this.wins[i + k][j - k][this.winCount] = true;
         }
         this.winCount++;
      }
   }

   //赢法计数 myWin wallEWin 分别计算选手获胜的可能
   for (var i = 0; i < this.winCount; i++) {
      this.myWin[i] = 0;
      this.wallEWin[i] = 0;
   }
}


2.3.2 赢法统计数组实现
//瓦力落子后加上如下代码,(u,v)表示瓦力落子的坐标
//判断当前落点是否已有棋子,如果没有则落子成功,如果有则后台提示
for (var k = 0; k < _this.winCount; k++) {
   if (_this.wins[u][v][k]) {
      _this.wallEWin[k]++;
      _this.myWin[k] = 999;
      if (_this.wallEWin[k] == 5) {
         alert('瓦力赢了');
         _this.over = true;
      }
   }
}

//在对手落子后加上如下代码,(x,y)表示对手落子坐标
for(var k = 0; k < this.winCount; k++){
   if(this.wins[x][y][k]){
      this.myWin[k]++;
      this.wallEWin[k] = 999;
      if(this.myWin[k] == 5){
         alert('你赢了');
         this.over = true;
      }
   }
}


2.3.3 瓦力大脑升级
wallEAI: function () {   //瓦力的大脑
   var _this = this;

   //定义变量,分数统计数组和坐标存储变量
   var myScore = [],
      computerScore = [],
      max = 0,
      u = 0,
      v = 0;

   //分数统计初始化
   for (var i = 0; i < 15; i++) {
      myScore[i] = [];
      computerScore[i] = [];
      for (var j = 0; j < 15; j++) {
         myScore[i][j] = 0;
         computerScore[i][j] = 0;
      }
   }

   //分数(权重)统计&计算,获取最佳的落子坐标
   for (var i = 0; i < 15; i++) {
      for (var j = 0; j < 15; j++) {
         //判断当前位置是否没有落子
         if (_this.count[i][j] == 0) {
            //计算分数
            for (var k = 0; k < _this.winCount; k++) {
               if (_this.wins[i][j][k]) {
                  switch (_this.myWin[k]) {
                     case 1:
                        myScore[i][j] += 200;
                        break;
                     case 2:
                        myScore[i][j] += 400;
                        break;
                     case 3:
                        myScore[i][j] += 2000;
                        break;
                     case 4:
                        myScore[i][j] += 10000;
                        break;
                  }

                  switch (_this.wallEWin[k]) {
                     case 1:
                        computerScore[i][j] += 220;
                        break;
                     case 2:
                        computerScore[i][j] += 420;
                        break;
                     case 3:
                        computerScore[i][j] += 2100;
                        break;
                     case 4:
                        computerScore[i][j] += 20000;
                        break;
                  }
               }
            }
            //通过判断获取最优的落子点
            if (myScore[i][j] > max) {
               max = myScore[i][j];
               u = i;
               v = j;
            }

            if (computerScore[i][j] > max) {
               max = computerScore[i][j];
               u = i;
               v = j;
            }
         }
      }
   }
   _this.oneStep(u, v, _this.me);
   _this.count[u][v] = 2;

   //判断当前落点是否已有棋子,如果没有则落子成功,如果有则后台提示
   for (var k = 0; k < _this.winCount; k++) {
      if (_this.wins[u][v][k]) {
         _this.wallEWin[k]++;
         _this.myWin[k] = 999;
         if (_this.wallEWin[k] == 5) {
            alert('瓦力赢了');
            _this.over = true;
         }
      }
   }
   if (_this.over == false) {
      _this.me = !_this.me;
   }

}


三 完整代码地址

https://github.com/summer1914/Wall-E/tree/master/AI

欢迎讨论,欢迎留言。若喜欢可送颗star