1

简化游戏规则：

  • 棋子每回合可以移动一次。
  • 棋子可以向 4 个方向移动。（上下左右）
  • 棋子像棋盘一样在网格上移动。
  • 到达对方行的棋子获胜。
  • 为简单起见，可以忽略其他规则。

评价功能：

  • 如果reached to the target, return 100.
  • 其他：return Opponent Distance From Target - Own Distance From Target

我minimax使用alpha-beta pruning并指定了一个max-depth. 我将我的实现与几个 3rd 方实现进行了比较，它看起来是一样的。因此，我不想粘贴我的实现，而是想直接问我的问题：

当 2 个 AI 相互竞争时。一旦他们检测到其中任何一个赢得比赛，他们就无法选择有意义的方向，因为超过 1 个选择的得分相同。随机选择这些选项中的任何一个，都不会改善它，因为它们永远毫无意义地移动。

这是（死锁）预期的事情吗？如果不是，可能是什么问题？如果是这样，我该如何解决？

4

1 回答 1

0

是的，这可以通过简单的 alpha-beta/minimax 实现轻松实现。

对此的最佳解决方案可能是迭代加深 - 迭代搜索 1...max-depth ply。这很好用有几个原因：

  1. 额外迭代的开销很小，因为每次迭代都比上一次昂贵得多。（这棵树呈指数增长。）

  2. 当您在给定的迭代中为自己赢得胜利时，您会立即终止（例如，不要继续搜索更大的迭代）并采取获胜的行动。这避免了寻找更长的获胜序列而不是最短的获胜序列的问题。（解决你的问题。）

  3. 您可以在早期迭代中使用类似历史启发式的方法来改进后期迭代的排序并提高 alpha-beta 的效率。（如果您限制最大深度并不重要，但如果您限制时间，它可能会有所帮助。）

于 2019-11-04T18:30:47.080 回答