c# - 对抗性搜索问题

Question

我正在使用对抗性搜索技术与 AI 对手一起编写 Connect4 游戏，但我遇到了一些障碍。我觉得我离解决方案不远了，但可能存在问题，我正在转换观点(例如:我的评估分数基于哪个参与者的观点)，在某处缺少减号或类似的东西那。

问题是，在我尝试过的变体中，当玩家有三连胜时 AI 选择不阻止玩家，否则 AI 会玩完美的游戏，或者他更喜欢阻止玩家，即使他有机会赢得比赛。搜索深度是偶数还是奇数似乎也很重要，因为人工智能在 6 层搜索中是头昏眼花的，这很明显表明出了什么问题。

搜索

使用的算法是具有 alpha-beta 剪枝的 negamax，实现如下:

private int Negamax(int depth, int alpha, int beta, Player player)
{
  Player winner;
  if (Evaluator.IsLeafNode(game, out winner))
  {
    return winner == player ? (10000 / depth) : (-10000 / depth);
  }

  if (depth == Constants.RecursionDepth)
  {
    return Evaluator.Evaluate(game, depth, player);
  }

  foreach (var move in moves)
  {
    int row;

    if (board.DoMove(move, player, out row))
    {
      var value = -Negamax(depth + 1, -beta, -alpha, (Player)1 - (int)player);

      board.UndoMove(move, row, player);

      if (value > alpha)
      {
        alpha = value;
        if (player == Player.AI)
        {
          bestColumn = move;
        }
      }

      if (alpha >= beta)
      {
        return alpha;
      }

    }
  }
  return alpha;
}

我不怀疑问题出在这个函数中，但它可能是。

评价

我的评估函数基于这样一个事实，即在 7x6 板上只有 69 种可能的方法来获得四排。我有一个大约 350 个项目的查找表，其中包含每列和行的硬编码信息，行+列是其中的组合。例如，对于第 0 行和第 0 列，表格如下所示:

//c1r1
table[0][0] = new int[3];
table[0][0][0] = 21;
table[0][0][1] = 27;
table[0][0][2] = 61;

这意味着第 0 列第 0 行是组合 21、27 和 61 的一部分。

我有第二张 table ，里面包含了两个玩家在每个获胜组合中都有多少石头。当我移动时，我会执行以下操作:

public bool DoMove(int column, Player p, out int row)
{
  row = moves[column];

  if (row >= 0)
  {
    Cells[column + row * Constants.Columns] = p;

    moves[column]--;

    var combinations = this.Game.PlayerCombinations[p];

    foreach (int i in TerminalPositionsTable.Get(column,row))
    {
      combinations[i]++;
    }

    return true;
  }
  else
  {
    return false;
  }
}

对 UndoMove 的做法当然是相反的。 .

因此，在第 0 列、第 0 行上移动后 Player.Human ，该表将在索引 21、27 和 61 处填充值 1。如果我在也是双赢组合 27 的一部分的单元格中执行另一个移动，则玩家组合表在索引 27 处增加到 2。

我希望我已经说明了这一点，因为它在评估功能中用于非常快速地确定一名球员与四连胜的接近程度。

我怀疑问题所在的评估函数如下:

public static int Evaluate(Game game, int depth, Player player)
{
  var combinations = game.PlayerCombinations[player];

  int score = 0;

  for (int i = 0; i < combinations.Length; i++)
  {
    switch (combinations[i])
    {
      case 1:
        score += 1;
        break;
      case 2:
        score += 5;
        break;
      case 3:
        score += 15;
        break;
    }
  }

  return score;
}

所以我简单地遍历 69 种可能的获胜组合，并根据它是单块、连续两块还是三块来添加分数。

在整个对抗性搜索中我仍然感到困惑的部分是我是否应该关心哪个玩家在做 Action ？我的意思是，我应该像这里一样传递玩家，还是应该始终从 AI 玩家的角度评估棋盘？我尝试了很多 aiScore - humanScore 的组合，或者只是总是从 Player.AI 的角度来看，诸如此类。但我已经走到了死胡同，我尝试过的每一个组合都有很大的缺陷。

所以:

我的评估逻辑是否扎实？

我什么时候应该“切换视角”？

任何帮助将非常感激。

更新

我已经在下面实现了布伦南的建议，虽然它确实有 多改进，出于某种原因，它不会阻止任何列上的三行，而是最左边和最右边的两个，并且仅当搜索深度不均匀时。即使在搜索深度上，AI 也是无与伦比的，但仅限于深度 8 及以上。然后它拒绝再次阻止。这很有说服力，我可能非常接近，但仍然有一些关键的缺陷。

也许这与我设置了 AI 应该像 Brennan 评论的那样扔石头的列有关，但我不知道什么时候可以设置它。仅在深度 0 处设置它不起作用。

更新 2

使用 Brennan 的更改编辑了现在的代码。

更新 3

使用完整代码创建了一个 Github 存储库。如果您不知道如何使用 Git，只需从 here 下载一个 zip 文件即可。 .

这是一个 .NET 4.0 项目，运行它会在你的文档/日志目录中创建 negamax 算法的日志文件。该解决方案还包含一个测试项目，其中包含对每个棋盘列的测试，当玩家在那里有三排时，AI 是否选择阻止玩家。

Answer 1

这些东西让我的大脑受伤，所以我不确定这个答案是正确的，但是这里是。

在 negamax 中，分数总是相对于当前移动的玩家进行评估。如果是白棋，那么高分对白棋有利。如果是黑棋，那么高分对黑棋有利。因此，如果您有一个叶节点，那么分数是 +inf 还是 -inf 并不取决于该节点是白人获胜还是黑人获胜，而是取决于您当前正在评估的玩家是否获胜。替换这个:

return winner == Player.AI ? (10000 / depth) : (-10000 / depth);

有了这个:

return winner == player ? (10000 / depth) : (-10000 / depth);

您的评估函数中存在类似的问题。替换这个:

return player == Player.AI ? score : -score;

有了这个:

return score;

同样，我不确定这是正确的。但我希望您尝试这两个更改，并让我知道它是否有效。我很好奇!