三子棋AI实现:MiniMax算法

ZZVZzaU.png!web

昨天的博客讲述了如何实现一个三子棋游戏,今天就来为这个三子棋游戏来加入AI,实现让程序来与玩家对弈。这篇博客讲述的这个AI算法会根据玩家的落子进行分析并且算出自己的最优的下法,而且AI最不理想的情况就是平局,也就是说AI不会输掉棋局。这个算法就是MiniMax算法。

什么是MiniMax算法

Minimax算法在中文上叫做极大极小值算法,常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,另一方则选择令对手优势最小化的方法。

这个算法被普遍采用在现金的各种棋盘游戏中来帮助计算机AI做出决定,这类的游戏有一个共同点,就是游戏开始后游戏的所有的信息玩家都是知道的,玩家可以知道如何取得胜利,棋盘中还有哪些位置可以走,这类游戏都可以采用这个算法。

完美三子棋走法

什么是一个完美的三子棋走法呢?按照人的思路,可以在尽量短的步数内赢得游戏,或者平局的走法就是一个完美的走法,于此同时,在这期间也要阻止另一方去赢得胜利。也就是说如果对方也用的是一个完美的走法,那么我们两个人下棋将永远是平局。

人在处理这些的时候用脑子想一想就可以了,至少在三子棋方面,人的计算能力就可以走出完美的棋局,可是计算机呢?如何让计算机来评估什么是完美什么是不完美呢?那就得用到分值的方法,计算机只能去处理定量的东西,当赢或输或平局的时候可以让计算机为这个走法打分:

  • 我赢了!得10分!!!
  • 我输了。。好吧,减10分。。(这时对方是加10分)
  • 平局。。行,0分,没有玩家在这一局取得分数

下图就是一个例子:

TicTacToePerfect

 

在一个状态中,对于O来说,下一步可以有三种情况,第一种情况会赢,其他两种不会结束游戏,所以理所应当的,第一个位置就是O下一局的完美走法。

但是X呢,我们可以假设X也在下棋,并且X也想赢得比赛,作为O,在模拟的时候当然不希望X赢得比赛啦,所以就想一开始介绍的那样,模拟X的时候应该去选择一个低分数(输掉-10或者平局0)来作为X的最佳走法。

这也就是MiniMax的思路,模拟自己走法时,尽可能让自己赢,模拟对手是,尽可能让对手输,也就是让自己的优势最大化,让对方的优势最小化,这样下来就可以寻找出来最优的下法。

MiniMax算法描述

就像上文说的一样,MiniMax算法在得到当前棋盘状态后,会模拟走出所有可能的地方,每走一步之后,算法会接着模拟对方玩家走出下一步,就这样你走一步他走一步,直到游戏结束得到分值,这样不断递归,程序就能得到所有的游戏结果以及相应的分值,分值最大的那个就是AI最有可能赢的。之后玩家每走一步,AI都会以相同的算法取得最优走法。

以上就是算法大概的工作过程,对于三子棋来说,如果使用这个MiniMax算法,9格都是空的的情况下,算法会算出总共25万种游戏可能性,递归50万次,每当有一个格被走出,游戏剩下的可能性和运算的递归次数都会减少很多,因为这个算法复杂度是指数型的,非常的浪费时间,之后我会写文章去优化这个算法,当前这个算法只能用于三子棋,要是四子棋,五子棋的话,如果不优化。。第一局电脑算两天都不一定能算出一个最优结果。

MiniMax算法实现

实现这个算法的数据结构是博弈树(Game Tree)模型,博弈树是指由于动态博弈参与者的行动有先后次序,因此可以依次将参与者的行动展开成一个树状图形。

通俗地讲就是树状结构,算法会算出游戏所有的结果,每个结果的相应走法就是树的一个枝(Branch),每一个可能的走法就是一个节点(Node),而游戏结束时刻的哪一个走法就是相应的一个根节点(Root)。算法要搜索整个博弈树,获得所有节点分值,选择分值最高的节点。

arbre-tic-tac-toe

算法流程描述

假设”X”是当前玩家:

  • 如果游戏结束,返回当前棋盘状况的分值
  • 否则,得到棋盘中所有可以下子的点(3子棋最多九个)
  • 创建一个数组来存放分值
  • 对于每一个可能的游戏状态,再次调用Minimax算法(递归)
  • 如果是‘X’的回合(AI),返回最大的分值
  • 如果是‘O’的回合(玩家),返回最小的分值

你会注意到这个算法是递归的,他会一直向下搜索,知道游戏结束,得到当前游戏结果的分值

我们来根据下面的图来过一下这个算法(下图是游戏中的一部分):

ZZVZzaU.png!web

 

  1. 棋局1是‘X’的回合,棋局1之后还可能有三种走棋可能,他们分别是棋局2,3和4,下面对棋局2,3,4分别调用minimax算法。
  2. 棋局2的走法,X赢得了比赛,游戏结束,所以在状态1的分值中加10
  3. 棋局3和4,很明显游戏没有结束,没有人赢或输,博弈树要继续向下扩展,棋局3可以延伸出来棋局5和棋局6,分别对棋局5,6调用Minimax. 当然棋局4可以扩展为棋局7和棋局8,分别调用Minimax。
  4. 棋局5,X输掉了比赛,所以把-10放到棋盘3的分值里面,棋局7,X同样输了,所以把-10加入到棋盘4的分值里面。
  5. 因为棋盘3和棋盘4是O的回合,所以O要寻找最小的分值,所以不管是否继续搜索O的分值最小就是-10了
  6. 最后棋盘2,3,4得到的分值分别是10,-10和-10,因为棋盘1是X的回合,X需要赢得比赛,所以X要找2,3,4棋盘中分数最多的棋盘,所以2就被选择为下一个走法,AI下回合会选择棋盘正中间落子,因为这样赢得可能性最大。

下面是比较通俗讲解:

这是一个深度为5的树

  • 第0层需要第1层中最大得值,所以是-7
  • 第1层需要第2层中最小的值,所以的是-10和-7
  • 第3层又需要最大的值,所以是10,-10,5,Screen Shot 2016-01-22 at 12.57.37 PM

不过上面的解释有些牵强,树结构在这个算法中是由下向上的,所以应该从最底层的跟节点向上分析,整个算法遵循了一个“冒泡”(Bubble Up)的思路。

 

 

算法代码

下面的代码只是minimax算法的伪代码,要想实现这个算法,还需要一个函数来获得当前棋局中剩下可以走的位置,和一个用来给游戏结果打分的函数。

def MinMax (board, player)

       if ( board.isGameOver() )

          return board.evaluate(player), null

       bestMove = null

       if ( board.currentPlayer() == player )

               bestScore = -INFINITY

      for move in board.getMoves()

               newBoard = board.makeMove(move)

               score = MinMax(newBoard, player)

               if ( board.currentPlayer() == player )

                       if ( score > bestScore ) # max

                                 bestScore = score

                                 bestMove = move 

                      else if ( score < bestScore ) # min 

                                 bestMove = move

            return bestScore, bestMove

MinMax(board, player)

下面是哪个3子棋游戏AI类的完整代码,这段代码稍作修改可以应用到任何棋类游戏中:

我写了一个AImove的内部类来封装存放分值和下棋的位置。

package it.miketech.tic_tac_toe;

import android.util.Log;

import java.util.List;

/**
 * Created by mike on 1/18/16.
 */
public class AI {

 int difficulty=3;
 private static int SCORE_WIN=10;
 private static int SCORE_FAIL=-10;
 private static int SCORE_DRAW=0;

 private static int CONTROLOR_AI=2;
 private static int CONTROLOR_PLAYER=1;

 private AImove score(Board game){
 int score ;
 switch (game.getGameResult()){
 case 0:score=0; break;
 case 1:score=1; break;
 case 2:score=-1; break;
 default: score =2; break;
 }
 //Log.d("Score",score+"");
 return new AImove(score);
 }

 public AImove miniMax(Board game){

 game.getGameResult();
 if (game.gameOver){
 MainActivity.counter++;
 //Log.d("miniMax","Game Over");
 return score(game);
 }else {

 int thisScore;
 int bestScore;
 int bestMove=0;

 Board gameCopy;

 if (game.getCurrentPlayer()==1){
 bestScore=-1000;
 }else {
 bestScore=1000;
 }

 List<Integer> moves=game.getAvailableSlots();
 for (int i=0;i<moves.size();i++){

 gameCopy=game.copy();
 gameCopy.placePiece(moves.get(i));

 thisScore=miniMax(gameCopy).score;

 if (game.getCurrentPlayer()==CONTROLOR_PLAYER){ //For player

 if (thisScore > bestScore){
 bestScore=thisScore;//Max
 bestMove=moves.get(i);
 }

 }else { // For CPU AI
 if (thisScore < bestScore){
 bestScore=thisScore;//Min
 bestMove=moves.get(i);
 }
 }

 }
 //Log.d("miniMax","Return Ok! bestScore:"+bestScore+ "bestMove:"+bestMove);
 return new AImove(bestScore,bestMove);
 }

 }

 class AImove{

 int position = 0;
 int score = 0;

 public AImove(int score, int position){
 this.score=score;
 this.position=position;
 }

 public AImove(int score){
 this.score=score;
 }

 }

} 

昨天的三子棋游戏已经修改加上MiniMax算法,可以到这里查看AI部分代码:点击进入

打赏

Leave a Reply

Your email address will not be published. Required fields are marked *