1

我正在尝试将 Java 中的 Gomoku（连续五个）游戏编写为一个单独的项目。对于 AI，我知道使用带有 Alpha-beta 修剪的 Minimax 函数是解决这个问题的好方法。但是，我很难想象这将如何工作。

我的问题是：对于极小极大树中的节点，什么是好的表示？

我认为我的评估函数将“加权”板上的所有空白空间。然后它将从该板上取最佳值作为 minmax 决策树的节点。我在正确的方向吗？

也欢迎任何其他提示！提前致谢！

4

2 回答 2

4

状态空间搜索是通过棋盘的不同状态进行的。有很多动作，因为你可以在任何无人的地方放置一块石头。每个状态都可以表示为一个 9x9 矩阵，具有 3 个值——白色、黑色或未占用。因此，对于 9x9 板，有 3 ^ 81 种可能的板状态。

在任何棋盘状态下，移动的数量是未占用顶点的数量。您可以在这些顶点中的任何一个上放置一块石头。你只能玩自己的颜色。因此，最多有 81 种可能的移动.. 第一次移动 81 次，第二次移动 80 次，依此类推。因此，您可以合理地搜索到深度 5，并且可能更多……还不错。

如前所述，正确的表示是一个 2D 矩阵——这可以只是一个 2D 整数数组，其值例如 0 表示未占用，1 表示白色，2 表示黑色。... int[9,9]。

您的评估功能听起来不太好。相反，我会给以下几点：

-- 连续获得 5 分 -- 基本上给它最高分，因为这是一场胜利 -- 连续 4 分，有 2 个开放端 -- 也是最高分，因为对手无法阻止您获得 5 分。 -- 连续 4 次有 1 个开端 -- 仍然是一个非常有威胁的位置，因为对手必须在一个位置上进行阻挡。-- 连续 3 个，有 2 个开放端 -- 再次获得非常高的分数 --- 4, 3, 2, 1 有两个封闭端 -- 0，因为不可能连续获得 5 个。

等等。

然后，您只需应用标准的极小极大算法——即 alpha beta pruning——它与国际象棋完全相同，但您有不同的状态空间生成器和评估函数。

于 2011-03-29T08:55:30.177 回答
2

我会考虑以下形式的评估函数：考虑每组，例如，一行中的 6 个位置。（在 19x19 的棋盘上，每条线有 14 个，每条对角线有 0 到 14 个不等的数字；我认为整个棋盘上有 742 个。我的算术可能是错误的。）每组有 729 种可能的排列黑色、 白色和空白空间。或者，呃，378，如果你考虑到端到端的对称性。或者，呃，嗯，比那个少，但如果你也考虑黑白对称性，我不会费心去计算少了多少。

因此，现在您的评估函数将包括在 378 或许多元素的表中对每块 6 块石头进行表查找（或者可能其中两个，一个用于水平线和垂直线，一个用于对角线） . 把结果加起来，这就是你对这个职位的评价。

事实证明，实际上更大的表格（从更长的位置行派生）效果更好。

但是表里有什么？让你的程序解决这个问题。从表中的任意值开始（例如，您可以使用 eval(line) = #black(line)-#white(line) 或其他值）。让您的程序自行运行，使用 alpha-beta 搜索。现在根据发生的情况更新表条目。有很多不同的方法可以做到这一点；这里有一些（粗略描述的）。

  • 在每场比赛中，记录每个模式在每个玩家的位置上出现的次数。游戏结束后，调整每个图案的得分，使获胜玩家更常看到的图案看起来更好。
  • 每次搜索时，调整当前位置的模式分数，使当前的静态分数更接近搜索得到的分数。
  • Each time a move is made, adjust the scores for each pattern in the "before" position to make the "before" score match the "after" score better.
  • Have lots of different tables (hence lots of different variants of the evaluation function). Let them play against one another. Apply some sort of evolution (e.g., play all against all, then throw out the worst performers and replace them with mutants derived from the better performers).

For a more sophisticated version of these ideas (applied to chess, but the same ideas would work fine for gomoku), take a look at http://cs.anu.edu.au/~Lex.Weaver/pub_sem/publications/knightcap.pdf .

于 2011-03-29T09:23:32.647 回答