好的Minimax在Gomoku的表示法？

Question

我试图在Java中编写一个Gomoku (连续五个)游戏，作为一个单独的项目。对于AI，我理解使用带有Alpha-beta剪枝的Minimax函数是一种很好的方法。然而，我在设想这将如何工作时遇到了一些小麻烦。

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

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

任何其他提示也是受欢迎的！提前感谢！

Answer 1

状态空间搜索是通过板的不同状态进行的。有很多的动作，因为你可以把一块石头放在任何无人居住的地方。每种状态都可以表示为例如9x9矩阵，有3个值--白色、黑色或空值。与9x9板，因此，有3^ 81可能的董事会状态。

从任何董事会状态，移动的数量是未被占用的顶点的数目。你可以在这些顶点上放置一块石头。你只能玩你自己的颜色。所以，最多有81个可能的动作。第一步81次，第二次80次，依此类推。这样你就可以合理地搜索到第五深度，而且可能更多。不算太糟。

正确的表示形式是，正如前面提到的，一个2D矩阵--这可以是一个由ints组成的二维数组，值为0表示无人居住，1表示白色，2表示黑色。..。9. int9,9 9.

你的评估功能听起来不太好。相反，我想提出以下几点：

--一连得5分--基本上是这一场比赛的最高得分，因为这是一场胜利--连续4场有2个开局--也是最高分，因为对手不能阻止你获得5分。--连续3次，两次开放-又是很高的分数-非常高的分数

诸若此类。

然后，你只需要应用标准的极大极小算法--即αβ剪枝--它和国际象棋完全一样，但是你有一个不同的状态空间生成器和评估函数。

Answer 2

我会考虑一个评估函数的如下形式:考虑每一组，例如，6个职位在一条线。(在19x19的棋盘上，每条线有14条，每条对角线上的数字从0到14不等；我认为整个板上有742条。我的算术可能错了。)每组有729个可能的黑、白和空空间。或者，呃，378，如果你考虑到端到端的对称性。或者，呃，嗯，比这个少，但是我也不想知道，如果你也考虑了黑白对称的话，还会少几个。

因此，现在您的评估功能将包括一个表-查找每块6块石头，在一个378-或-然而-多元素表(或者其中可能有两种，一条水平线和垂直线，一条对角线)。把结果加起来，这就是你对这个职位的评价。

结果可能会发现，更大的表(从较长的位置派生而来)工作得更好。

但是桌子里放的是什么？让你的程序解决这个问题。从表中的任意值开始(例如，您可以使用eval(line) = #black(line)-#white(line)或其他什么)。让你的程序发挥自己，使用α-β搜索。现在，根据发生的情况更新表条目。有许多不同的方法来做这件事；这里有一个(粗略描述)的少数。

• 在每一场比赛中，要跟踪每个玩家的位置上每个模式发生了多少次。游戏结束后，调整每一种模式的得分，使获胜玩家看到的模式更好看。每次搜索时，
• 调整当前位置模式的得分，使当前静态得分更接近搜索获得的分数。每次移动时，
• 调整每个模式在“前”位置上的分数，使“得分”之前的“分数”更好地匹配“得分”。
• 有许多不同的表(因此有许多不同的评估功能)。让他们互相对抗。应用某种进化(例如，把所有的人都击倒，然后把表现最差的人赶出去，用从表现较好的人身上衍生出来的变种人来代替)。

对于这些想法的更复杂的版本(适用于国际象棋，但同样的想法对gomoku来说也很好)，请看一下http://cs.anu.edu.au/~Lex.Weaver/pub_sem/publications/knightcap.pdf。