副词检索故障

Question

我写了一个Connect4游戏与人工智能的对手使用对抗性搜索技术，我有点撞墙。我觉得我离解决方案不远，但可能存在一个问题，我正在转换观点(比如，我所依据的是哪个参与者的观点)，在某个地方遗漏了一个负号或类似的东西。

问题是，在我尝试过的变体中，当玩家有三排的时候，AI选择不阻止玩家，否则AI会玩一个完美的游戏，或者他更喜欢阻止玩家，即使他有机会赢得这场比赛。搜索深度是否是偶数还是不均匀数字似乎也很重要，因为人工智能在6层搜索中表现得非常迟钝，这很能说明问题出在哪里。

搜索

所使用的算法是带有α-β剪枝的否定算法，其实现如下：

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;
}

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

评价

我的评估功能是基于这样一个事实，即只有69种可能的方法可以在7x6板上实现四行。我有一个由大约350个项目组成的查找表，其中包含了每一列和每一行的硬编码信息，row+column是其中的一部分。例如，对于第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行是win-组合21、27和61的一部分.

我有第二张表，它包含了两位玩家在每一次胜利组合中有多少块石头。当我做一个动作时，我会做以下几件事：

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的情况正好相反。

因此，在Player.Human对0列第0行进行移动之后，表中将填充索引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种可能的双赢组合，并根据它是一块石头，两排还是三块加了一个数值。

在这个充满敌意的搜索过程中，我仍然感到困惑的是，我是否应该关心哪个球员在移动？我的意思是，我应该像在这里一样通过球员，还是应该总是从AI球员的角度来评估董事会？我尝试过许多aiScore - humanScore组合，或者总是从Player.AI的角度来看，诸如此类。但我已经走到了死胡同，我尝试过的每一个组合都有很大的缺陷。

所以：

1. 我的评价逻辑在其基础上牢固吗？
2. 我什么时候应该“切换视角”？

任何帮助都将不胜感激。

更新

我在下面实现了Brennan的建议，虽然确实有了很大的改进，但出于某种原因，它并没有阻止任何列中的三行，只有在搜索深度不均匀的情况下，才能阻止最左边和最右边的两列。AI在甚至搜索深度上都是无敌的，但只有在深度8或更高时才能被打败。然后它拒绝再次封锁。这很能说明我可能很接近，但仍然有一些关键的缺陷。

也许这与我设置专栏有关-- AI应该像布伦南所说的那样扔一块石头，但是我不知道什么时候设置它。只将其设置为深度0是不起作用的。

更新2

用Brennan的更改编辑代码，就像现在一样。

更新3

用完整的代码创建了一个Github回购程序。如果您不知道如何使用Git，只需从这里下载一个压缩文件即可。

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

Answer 1

这些东西让我的大脑很疼，所以我不确定这个答案是正确的，但现在就这样了。

在“否定”中，得分总是相对于当前正在移动的球员进行评估的。如果这是白人的举动，那么高分对白人是有利的。如果是黑人的举动，那么高分对黑人是有利的。因此，如果您有一个叶节点，得分是+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;

再说一次，我不确定这是对的。但我希望你尝试这两种改变，让我知道它是否有效。我很好奇！

Answer 2

如果没有阻止某些组合，听起来你的可能获胜表中有一个缺陷。

我还在你的评估功能中看到了一个问题:它给那些没有获胜希望的动作带来了价值。假设你有xoo.x，你在玩o。你的例行公事说在这里玩它值15分，而实际上它值0。任何已经包含来自两位玩家的牌的胜利模式对任何人都没有任何价值。

我发现在调试这类东西时，调试器没有多大价值，因为它不能让您很好地了解全局。尝试写入一个日志文件，它正在检查的每个模式--将一个实际的绘图放在日志中。