井字棋 - 无递归的 MiniMax

• 下载 TicTacToe_2.0 - 102.9 KB (递归代码)
• 下载 TicTacToe - 2.1 MB (穷举搜索代码)

引言

我萌生了通过搜索所有可行的井字棋游戏状态来构建一个类似 AI 的游戏的想法，想着“这不算真正的 AI，但这可能是一个有趣的项目”。

背景

经过大约十天的折腾，调试了所有关于确定当前游戏状态的可行祖先的问题，并向上发送诸如 `TurnsToExWin`、`TurnsToOhWin`、`Win_Lose` 比率以及多种其他徒劳的尝试数据，我终于让它实现了我的目标——生成所有状态并发送信息，但结果充其量只能说是平淡无奇。然后我读了这篇文章，《如何通过使用 Minimax 算法让你的井字棋游戏无敌》。Minimax 的想法也随之鲜活起来。我如释重负地睡了一觉，因为我得到了一个现成的答案，然后花了两小时实现了递归 Minimax 井字棋游戏，并认为自己懂得该怎么做了。

在已有的代码基础上使用 Minimax 算法并不是什么难事，因为所有的祖先/后代问题都已经解决了。经过一些错误，实际上是从不同的角度重新思考了递归的结果，现在它就是这样了。一个算法，它生成所有可能的游戏状态，并系统地回溯它们，以重现递归 Minimax 算法的结果，现在它只需直接找到文件中的正确记录，查找出招，并根据其智商设置选择一个合适的出招。

Using the Code

这个项目相当友好，你的侄女侄子都可以玩。开发者可能会对 `CK_objects` 中的一些组件感兴趣，例如 `HSlider`，它在一条路径上显示一个图形滑块，允许用户设置一个整数值，这里是电脑的智商。

这里的递归 Minimax 看起来是这样的

int evaluateMove(classGameState cGameState, enuSquareStates eStatePlayer)
{
  intRecursionCounter++;
  int intMyID = intRecursionCounter ;
  enuBoard_State eBoardState = cGameState.getState(ePlayerTurn);
  enuSquareStates eOpponent = getOpponent(eStatePlayer);
  switch (eBoardState)
  {
    case enuBoard_State.Draw:
      return 0;
    case enuBoard_State.Lose:
      return -10;
    case enuBoard_State.Win:
      return 10;
    default:
      int[,] intMoves = new int[3, 3];
      List<classPointListElement> lstMoves = new List<classPointListElement>();
      for (int intY = 0; intY < 3; intY++)
        for (int intX = 0; intX < 3; intX++)
        {
          if (cGameState.board[intX, intY] == enuSquareStates.blank)
          {
            Point pt = new Point(intX, intY);
            classGameState cNextGameState = new classGameState(cGameState.board, pt, eOpponent);
            enuBoard_State eNextBoardState = cNextGameState.getState(ePlayerTurn);

            intMoves[intX, intY] = evaluateMove(cNextGameState, eOpponent);
            classPointListElement cPLE = new classPointListElement(pt, intMoves[intX, intY]);
            lstMoves.Add(cPLE);
          }
        }
      IEnumerable<classPointListElement> query;
      if (ePlayerTurn == eStatePlayer)
        query= lstMoves.OrderBy(pointListElement => pointListElement.value);
      else
        query = lstMoves.OrderByDescending(pointListElement => pointListElement.value);
      lstMoves = query.ToList<classPointListElement>();
      return lstMoves[0].value;
  }
}

并且它会为电脑的每一次出招调用自身（递归）。穷举搜索的 `PlayAi()` 函数只需要根据其智商设置来决定选择什么。

void PlayAI()
{
  if (cGame == null) cGame = classBinTree.instance.BinRec_Load(0).Record;

  List<classPointListElement> lstMoves = new List<classPointListElement>();
  classEnumeratedTypes.enuPlayer eOpponent = classTicTacToe_Record.NextPlayer(cGame.ePlayer);
  for (int intY = 0; intY < 3; intY++)
    for (int intX = 0; intX < 3; intX++)
      if (cGame.Descendants[intX, intY] > 0)
        lstMoves.Add(new classPointListElement
        (new Point(intX, intY), cGame.Moves[(int)cGame.ePlayer, intX, intY]));
  IEnumerable<classPointListElement> query = 
              lstMoves.OrderByDescending(move => move.value);
  lstMoves = query.ToList<classPointListElement>(); // lstMoves[0] 
                                   // has the best choice to play next

 // choose a path appropriate for this IQ
      int intRnd = 0;
  if (ghs_IQ[(int)cGame.ePlayer].Value > 90)
  {
    List<classPointListElement> lstTopMoves = new List<classPointListElement>();
    for (int iCounter = 0; iCounter < lstMoves.Count; iCounter++)
      if (lstMoves[iCounter].value == lstMoves[0].value)
        lstTopMoves.Add(lstMoves[iCounter]); intRnd = cRnd.getInt(0, lstTopMoves.Count - 1);
    cGame = classBinTree.instance.BinRec_Load
    (cGame.Descendants[lstTopMoves[intRnd].pt.X, lstTopMoves[intRnd].pt.Y]).Record;
  }
  else
  {
    int intLogBase = 6; // the higher the logbase,
                        // the less biased the result will be towards Minimum
    intRnd = cRnd.getBiasedInt(0, lstMoves.Count - 1, 
             ghs_IQ[(int)cGame.ePlayer].Value, intLogBase);
    cGame = classBinTree.instance.BinRec_Load
                 (cGame.Descendants[lstMoves[intRnd].pt.X, lstMoves[intRnd].pt.Y]).Record;
  }
}

它读取当前玩家的 [3,3] 移动数组，将它们全部复制到一个列表中，保留它们的笛卡尔坐标和出招价值，然后按降序重新排序列表，以便最佳选择排在列表顶部。完成此操作后，它会使用一个有偏随机数生成器随机选择一个允许的出招，该生成器偏向于低范围值以获得更高的 Grade 输入参数（这里是智商），因此最终结果是，电脑玩家的智商越高，它选择最佳路径的可能性就越大。这里，如果电脑的智商高于 90，它将只从同样有效的最佳路径中选择。

`getBiasedInt()` 是一个事后诸葛亮，但结果还不错。它选择一个介于 `0` 和 `MaxRange` 之间的随机数，然后将 `MaxRange` 重置为之前的随机值，并循环 n 次，其中 n 是 `ComputerPlayer` 智商的直接函数。智商越高，循环次数越多，低数字产生的结果就越有可能，而高智商的电脑将选择更好的路径来玩。这并不完美，但已经很好了，而且这不是本文的主题，所以我还是保留了它。

关注点

上面列出的 Minimax 文章非常清晰且写得很好。如果我早点读到它，我就不会浪费一周时间尝试将正确的数据传递给我的 `PlayAI()` 函数了，任何关于 Minimax 的问题，我都会参考它。当算法像那个一样唾手可得时，事情就容易多了！

这个非递归算法的作用是，一旦数据构建完毕，就消除了 AI 思考的需要。

FindEndGames

为了构建数据文件，该算法首先对所有可能的游戏状态进行广度优先搜索。本质上，它列出了从起始位置的所有可能出招，并将它们放入一个队列。然后，它从队列中取出第一个并处理它，通过简单地重复它刚刚所做的——它也将所有可能的游戏状态的出招放入同一个队列，然后从队列中取出下一个游戏状态并继续，直到没有更多的游戏状态可被发现。

为了检索文件中的游戏状态，每个游戏状态的文件记录是一个二叉树叶子节点，叶子的搜索键是其唯一的游戏状态 ID。唯一的游戏状态 ID 是一个整数值，它使用一个基数为 3 的 9 位“十进制”编号系统来描述游戏板，其中顶部左侧 (0,0) 方块是最不重要的 (3⁰)，旁边的 (1,0) 是下一个最不重要的 (3¹)，依此类推，直到右下角 (2,2) 是最重要的 (3⁸)。令空白格 = 0，X = 1，O = 2，我们将方块的内容乘以 3ⁿ，得到一个唯一的 ID，它描述了游戏状态，并可用作存储游戏状态的二叉树的搜索键。

或者，完全绕过二叉树可以加速游戏状态记录的检索，如果 `uniqueID` 用作文件中的索引。这样做会显著增加文件大小，但由于硬盘存储设备如此丰富且便宜，如果速度是你的目标，这可能是一个更合适的解决方案。

所有游戏状态都被分sorted 到 9 个单独的文件中，每个文件包含一个指向二叉树中记录的索引列表，该列表在数据重建的 `FindEndGames` 阶段编译。这些索引直接指向二叉树文件中的记录，使我们无需搜索我们正在寻找的记录的 `UniqueID`。这些索引在重建阶段以及 `playAI()` 阶段都会被使用，例如上面看到的这一行，它使用 `classBinTree` 的 `load` 函数来检索 `lstTopMoves[]` 的一个随机索引的记录。

 cGame = classBinTree.instance.BinRec_Load
 (cGame.Descendants[lstTopMoves[intRnd].pt.X, lstTopMoves[intRnd].pt.Y]).Record;   }

TraceEndGames

此时，所有游戏状态都已定义并存储在硬盘上的二叉树文件中。每个状态都指向其自己的后代（可以从当前游戏状态达到的游戏状态）。每个记录的 `Descendants[3,3]` 数组保存了其每个可行后代的索引，但这些记录都不知道如何指向它们自己的祖先。

算法扫描在数据重建的 `FindEndGames` 阶段排序的每个游戏状态列表，从最拥挤的游戏状态开始，这些状态导致 `Draw` 或 `ExWin` 结束游戏（`Ex` 在最后和第一个回合放置 5 个 `Ex`，而 `Oh` 只有 `4` 个）。对于每个记录，它确定它的游戏状态类型。对于结束游戏，根据游戏的结束和玩家，分配的值为 `-10`、`0` 或 `+10`。`Ex` 和 `Oh` 都在每个记录中保存了 Minimax 信息，允许 AI 以与从每个可用方块的递归搜索中获得结果相同的方式选择路径。如果游戏状态不是结束游戏，那么它需要确定要“返回”到其祖先的值，方式模拟递归搜索结果。它检查其所有 `Moves[,]` 数组元素的内容，这些元素在上一扫描文件级别（保存所有比当前扫描文件游戏状态只差一个游戏方块的游戏状态的文件扫描）期间设置，然后将该信息向上发送给其祖先，并存储在其 `Moves[]` 数组中。

向上祖先传递信息的棘手之处在于，在井字棋中，每个玩家轮流出招，因此对于非结束游戏状态，你可以移除对手的任何一个棋子并生成一个可行的祖先。但是，对于导致对手获胜的结束游戏（当前玩家在对手出招后继承了结束游戏），唯一可行的祖先是持有三个获胜棋子的三个方块。这个规则的例外是当游戏以对手的三个棋子组成的两个获胜行或列结束时。

public enum enuTypeWin { H1=0, H2, H3, V1, V2, V3, RS, BS, Multiple, _numTypeWin };

在那些情况下，这里称为“`multiple`”，只有一个可行祖先，那就是对手的三个棋子组成的两个三子连线共同的那个方块。

一旦确定了祖先，每个祖先都会分别提供 `Ex` 和 `Oh` 的 Minimax 信息。这些信息存储在祖先记录的 `Moves[,]` 数组中，对应于通往当前正在处理的游戏状态的方块。由于文件从最拥挤的游戏状态到最不拥挤的依次扫描，Minimax 信息会沿着向上传递，直到到达二叉树文件记录索引 0（根节点）的起始（空）游戏状态。

历史

历史？我不知道。我查了维基百科关于 Minimax 的一些历史，以为能找到一些聪明的东西来点缀这篇文章，但没找到。

未来？嗯，现在。井字棋每个回合会增加棋子，而且相当可预测，所以从这个意义上说，这是一个相对容易完成的项目，所以我在想也许是跳棋？不确定。最终，国际象棋会很好。