Gomoku中的Minimax代表性好吗？

Question

我想在Java中编写一个Gomoku（五行）游戏作为一个单独的项目。对于AI，我知道使用Alpha-beta Pruning的Minimax函数是解决这个问题的好方法。但是，我在设想如何工作时遇到了一些麻烦。

我的问题是这样的：什么是一个极小树节点的很好的代表性？

我想对我的评价功能将“重量”的所有空电路板上的空间。然后它将从该板取得最佳值作为minmax决策树的节点。我在正确的方向吗？

和其他任何提示也欢迎！ 在此先感谢！

Answer 1

状态空间搜索是通过董事会的不同状态。有很多动作，因为你可以把石头放在任何地方。每个状态可以表示为例如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次。

等等。

然后你只需要申请标准极大极小算法 - 即α+β剪枝 - 这将是完全一样的棋，但你有一个不同的状态空间发生器和评价职能。

Answer 2

我会考虑以下形式的评价函数：考虑每一组的，比方说，6个位置在一条线上。 （在19x19板上，每行有14个字符，每个对角线上的数字从0到14变化;我认为在整个棋盘上有742个字符，我的算法可能是错误的）。对于每个集合，有729个可能的排列黑色，白色和空白空间。或者，呃，如果你考虑到端到端的对称性，呃，378。或者，呃，比这个还要少，但如果考虑到黑白对称性，我也不会费心研究减少了多少。

因此，现在您的评估函数将包含每个6块宝石块的查表，或者378个或多个元素的表格（或者其中两个，一个用于水平和垂直线条，一个对角线的）。将结果相加，这就是您对该职位的评估。

事实上，一张更大的表格（来源于更长的一排排位置）效果更好。

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

• 在每场比赛中，记录每个球员在每个球员位置出现的次数。当游戏结束时，调整每个模式的得分，以便获胜玩家更频繁地看到更好的模式。
• 每次您执行搜索时，请调整当前位置中的模式的分数，以使当前静态分数接近搜索获得的分数。
• 每次移动时，都要调整“之前”位置中每个模式的分数，以使“之前”分数与“之后”分数更好地匹配。
• 有很多不同的表格（因此很多不同的评估函数的变体）。让他们相互对抗。应用某种进化（例如，全部反对，然后抛出表现最差的表演者，并用来自更好表演者的突变体取而代之）。

对于这些想法的更复杂的版本（适用于国际象棋，但相同的想法将适用于gomoku），看看http://cs.anu.edu.au/~Lex.Weaver/pub_sem/publications/knightcap.pdf。