3

这是我的第一个问题，如果我做错了什么，请告诉我...

我目前正在用 Java 制作草稿游戏。事实上，除了人工智能之外，一切都正常。AI 目前是单线程的，使用极小极大和 alpha-beta 修剪。这段代码有效，我认为，它只是很慢，我只能深入我的游戏树 5。

  1. 我有一个函数可以接收我的主板、深度（从 0 开始）和最大深度。在这个最大深度处，它停止，返回棋盘上棋子最多的玩家值（-1,1 或 0）并结束递归调用。
  2. 如果还没有达到最大深度，我会计算所有可能的动作，我会一一执行它们，以某种方式将我的更改存储到主板上。
  3. 我还使用 alpha-beta 修剪，例如，当我发现一个可以让玩家获胜的动作时，我不会担心下一个可能的动作。
  4. 我从该主板状态递归地计算下一组移动。退出递归调用时，我撤消了这些更改（从第 2 点开始）。我存储这些递归调用返回的值并在它们上使用 minimax。

情况就是这样，现在我有一些问题。我想更深入地研究我的游戏树，因此我必须减少计算移动所需的时间。

  1. AI 可能的走法（例如 AI 可以选择的走法）的值总是 0 是否正常？或者如果我可以更深入地研究递归，这种情况会改变吗？因为此时我只能在递归中进行 5 次深度（最大深度），否则它需要的时间太长了。
  2. 我不知道它是否有用，但我如何将此递归转换为多线程递归。我认为这可以将工作时间除以一些价值......

有人可以帮我吗？

4

3 回答 3

2

1. AI 可能的走法（例如 AI 可以选择的走法）的值总是 0 是否正常？

对我来说听起来很奇怪。如果可能的移动数为 0，则该玩家不能玩他的回合。这应该不是很常见，还是我误解了什么？

如果您所指的值代表该动作的“分数”，那么显然“始终为 0”表示所有动作都同样好，这显然不是一个很好的 AI 算法。

2.我不知道它是否有用，但是我如何将这个递归转换为多线程递归。我认为这可以将工作时间除以一些价值......

我相信它会非常有用，尤其是考虑到如今大多数机器都有多个内核。

让它变得复杂的是你的“尝试移动，记录它，撤消它，尝试下一步”的方法。这表明您正在使用可变数据结构，这使得并行化算法变得极其复杂。

如果我是你，我会让边框/游戏状态由一个不可变的数据结构来表示。然后，您可以将每个递归调用视为一个单独的任务，并使用线程池来处理它们。您将接近 CPU 的最大利用率，同时大大简化代码（通过删除整个恢复到先前状态的代码）。

假设您的机器上确实有多个内核，这可能会让您更深入地了解树。

于 2012-05-12T11:10:45.050 回答
1

我强烈推荐阅读这本书：

领先一步：跳棋的计算机完美

它将为您提供有关跳棋游戏中计算机 AI 的深入历史，并且可能会为您的评估功能提供一些帮助。

与其让评估函数只对不同的棋子给出 1/0/-1，不如对每个常规棋子给出 100 分，对国王给出 200 分。然后给块结构奖金。例如，如果我的棋子形成了一个无法被捕获的安全结构，那么我会得到奖励。如果我的棋子独自在棋盘中间，那么我会得到负奖金。正是这种片段配置的丰富功能将使您的程序运行良好。最终得分是对两名球员的评价之差。

此外，您不应该以统一的深度停止搜索。静止搜索会扩展搜索，直到棋盘“安静”。在跳棋的情况下，这意味着棋盘上没有强制捕获。如果您不这样做，您的程序将运行得非常糟糕。

正如其他人所建议的那样，转置表可以很好地减少搜索树的大小，尽管程序运行速度会稍慢。我还推荐历史启发式，它易于编程，并且将大大改善树中移动的顺序。（谷歌历史启发式有关这方面的更多信息。）

最后，董事会的代表可以产生很大的不同。搜索的快速实现不会在每次应用移动时都复制棋盘，而是尝试快速修改棋盘以应用和撤消移动。

于 2012-05-13T06:03:36.007 回答
0

（我假设你所说的草稿是指我们在美国这里所说的跳棋。）

我不确定我是否理解你在游戏树中的评分系统。您是否通过说“如果玩家的棋子比对手多，则该位置得分 1 分，玩家的棋子少，则为 -1 分，如果他们的棋子数量相同，则为 0 分？”

如果是这样，那么您的算法可能只是前五步的捕获厌恶，或者事情正在发挥作用，因此所有捕获都是平衡的。我对跳棋并不十分熟悉，但对于只有五步棋的游戏来说，这似乎并非不可能。如果它只有 5层（其中一层是一个玩家的移动，而不是一整套相反的移动），它可能一点也不稀奇。

您可能想通过在您绝对知道正确答案的棋盘位置上输入来测试这一点，也许棋盘上只有两个棋子，其中一个棋子可以捕获。

不过，作为一般原则，棋盘评估功能没有多大意义——它忽略了棋子和加冕棋子之间的区别，将三人优势与单人优势视为相同。

于 2012-05-12T20:39:08.990 回答