逆行搜索烦恼

Question

我正在使用对抗性搜索技术与AI对手一起编写Connect4游戏,我有点碰壁.我觉得我离解决方案不远,但是我可能会出现问题,我正在转换观点(如:参与者的观点是我的评估分数基础),在某处丢失减号或类似的东西那.

问题是,在我尝试过的变体中,当玩家有三连胜时人工智能选择不阻挡玩家,但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的一部分.

我有一张第二张桌子,其中包含了两个玩家在每个胜利组合中有多少石头.当我搬家时,我会做以下事情:

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.如果我在也是win-combination 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的建议,虽然它确实有了很大的改进,但由于某种原因它不会阻止任何列上的三行,而是两个左右最多的行,并且只有当搜索深度时不平衡.人工智能甚至在搜索深度都是无与伦比的,但直到8级以上.然后它拒绝再次阻止.这很有说服力,我可能非常接近,但仍然有一些关键的缺陷.

也许这与我设置专栏应该如同Brennan评论的那样放下一块石头,但我不知道何时设置它.仅在深度0处设置它不起作用.

更新2

编辑了现在看起来像Brennan的变化的代码.

更新3

使用完整代码创建了一个Github仓库.如果您不知道如何使用Git,只需从此处下载zip文件即可.

它是一个.NET 4.0项目,运行它将在documents/logs目录中创建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;

再说一遍，我不确定这是否正确。但我希望您尝试这两项更改，并让我知道它是否有效。我很好奇！