java - Minimax Alpha Beta 算法

Question

我想我终于明白了 minimax 和 Alpha beta 修剪，但实现它完全是另一回事!

根据我的理解，基础知识是:您为某些 Action 分配启发式函数分数(例如五子棋)。

• 如果连续有 5 个，我们应该分配一个像 9999 这样的高值，因为这是一个成功的举动。
• 如果我们有 4 个连续的，我们有两个开口端我们应该再次分配一个高值，因为不可能阻止这个举动等等

当我们实际上必须用 Java 实现它时，我的问题就来了!

我有一个颜色 [][] 板 (8x8)，其中黑色是玩家 1，白色是玩家 2，null 表示空白区域，我很困惑我们会怎么做

1. 搜索棋盘以找到对立移动并分配值给他们
2. 搜索棋盘以找到我的着法并为其赋值他们
3. 然后选择最好的一步(我认为我可以做到如果我知道前 2 个是如何工作的，因为这基本上是算法)。

感谢一些帮助和指导!我查看了 YouTube 教程、来自各种在线资源的讲义，但在实际编写代码时，它们对我来说都没有真正意义。

如果有所不同，游戏是在 8x8 棋盘上玩的五子棋

Answer 1

定义状态

首先你必须定义游戏的状态。在您的示例中，它将是表示电路板配置的二维数组。

创建一个用于存储游戏配置和棋盘状态的 java 类。这个类现在将成为您的极小极大树的节点。

定义 child

定义极小极大树的节点后，您必须按照游戏规则定义 child 。这代表你的 Action 。

有了这个你就有了极小极大树!

Search the board to find the opposition moves and assign values to them

为了分配每个板配置的值，将其存储在类本身中。此外，您不必在棋盘上搜索反对行动，因为它由您的 child 代表。 [注意 board 与每个类(class)一起存储]

Search the board to find MY moves and assign values to them

同样，如果给定的类代表玩家 1 的 Action ，那么 child 代表玩家 2 的 Action 。

Then pick the best possible move

这是由算法定义的。如果您在最大节点中，则选择对应于最大值的移动。即你选择最高值(value)的 child 。
在最小节点的情况下，您选择最小值的 child 。

PS:您不必事先定义整个极小极大树。可以在做dfs的时候动态创建。这将显着减少内存。

PPS:引用Chess Programming了解更多详情。