三子棋AI实现：MiniMax算法

2016/01/20
数据结构
Android
算法

昨天的博客讲述了如何实现一个三子棋游戏，今天就来为这个三子棋游戏来加入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的内部类来封装存放分值和下棋的位置。

  1. package it.miketech.tic_tac_toe;
  3. import android.util.Log;
  5. import java.util.List;
  7. /**
  8.  * Created by mike on 1/18/16.
  9.  */
  10. public class AI {
  12.  int difficulty=3;
  13.  private static int SCORE_WIN=10;
  14.  private static int SCORE_FAIL=-10;
  15.  private static int SCORE_DRAW=0;
  17.  private static int CONTROLOR_AI=2;
  18.  private static int CONTROLOR_PLAYER=1;
  20.  private AImove score(Board game){
  21.  int score ;
  22.  switch (game.getGameResult()){
  23.  case 0:score=0; break;
  24.  case 1:score=1; break;
  25.  case 2:score=-1; break;
  26.  default: score =2; break;
  27.  }
  28.  //Log.d("Score",score+"");
  29.  return new AImove(score);
  30.  }
  32.  public AImove miniMax(Board game){
  34.  game.getGameResult();
  35.  if (game.gameOver){
  36.  MainActivity.counter++;
  37.  //Log.d("miniMax","Game Over");
  38.  return score(game);
  39.  }else {
  41.  int thisScore;
  42.  int bestScore;
  43.  int bestMove=0;
  45.  Board gameCopy;
  47.  if (game.getCurrentPlayer()==1){
  48.  bestScore=-1000;
  49.  }else {
  50.  bestScore=1000;
  51.  }
  53.  List<Integer> moves=game.getAvailableSlots();
  54.  for (int i=0;i<moves.size();i++){
  56.  gameCopy=game.copy();
  57.  gameCopy.placePiece(moves.get(i));
  59.  thisScore=miniMax(gameCopy).score;
  61.  if (game.getCurrentPlayer()==CONTROLOR_PLAYER){ //For player
  63.  if (thisScore > bestScore){
  64.  bestScore=thisScore;//Max
  65.  bestMove=moves.get(i);
  66.  }
  68.  }else { // For CPU AI
  69.  if (thisScore < bestScore){
  70.  bestScore=thisScore;//Min
  71.  bestMove=moves.get(i);
  72.  }
  73.  }
  75.  }
  76.  //Log.d("miniMax","Return Ok! bestScore:"+bestScore+ "bestMove:"+bestMove);
  77.  return new AImove(bestScore,bestMove);
  78.  }
  80.  }
  82.  class AImove{
  84.  int position = 0;
  85.  int score = 0;
  87.  public AImove(int score, int position){
  88.  this.score=score;
  89.  this.position=position;
  90.  }
  92.  public AImove(int score){
  93.  this.score=score;
  94.  }
  96.  }
  98. }

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

Copyright © 2015-2026 MikeTech.it. All rights reserved.

Developed By Yigang Zhou

沪ICP备2021020966号
Dashboard