4

所以，我一直在玩最小最大树，在两人棋盘游戏中创建一个简单的电脑玩家。我了解算法的基础知识，但有一个案例让我的火鸡大脑无法理解……当 MIN 可以分两步获胜时会发生什么？

例如，假设一个四连棋/井字游戏，其中只有两个玩家中的一个可以拥有一个方格。我如何让 MAX 仅仅为了防止 MIN 获得广场而占据一个广场？

让我们尝试一个简化的示例（以漂亮的 ASCII 艺术显示），其中选项是左和右。假设他的树太大而无法一直遍历到终端状态，所以中间值是根据启发式函数计算的（下面用 * 标记）。-INF 是 MIN 获胜的最终状态。

                MAX (a)             
                /   \
               A     B
              /       \
           MIN (b)    MIN (c)     
           /  \       /  \
          A    B     A    B
         /     |     |     \
      -INF    *5    *22    *20

MIN 将在状态 (b) 中选择动作 A，得分为 -INF
MIN 将在状态 (c) 中选择动作 B，得分为 +20
MAX 将在状态 (a) 中选择动作 B，获得 a +20 的分数

问题——当然——是如果 MAX 选择 B，那么 MIN 将执行动作 A（因为该方块仍然可用），因此 MIN 将获胜。我需要让 MAX 来实现在状态（a）中选择动作 A 的价值，以防止 MIN 在下一步中获得 -INF。

我会在代码中进行大量测试以检查 MIN 是否可以获胜，但在我看来，算法应该解决这个问题。我认为我在确定导致此问题的 MAX 值时遗漏了一部分。

（编辑澄清）

4

2 回答 2

3

极大极小树中的每个节点都是一个完整的博弈状态。当玩家选择一个动作时，游戏会进入该状态，限制两个玩家的动作（无法从另一个分支中选择另一个动作）。因此，在您的示例中，如果处于状态 (a) 的玩家 Max 选择动作 B，则游戏现在处于状态 C。此时 min 玩家的唯一选择是 A(22) 和 B(20)。树的深度无关紧要；最大和最小玩家总是会从游戏的当前状态中选择他们最好的动作。

对于井字游戏，每个状态都需要是一个完整的棋盘（当然可行）。例如，第一层将是 X 可以放置其标记的每个可能位置。然后这些状态的每个孩子将是 O 可以放置的每个可能的位置，给定父状态（X 放置的位置），等等......

当您无法表示整个博弈树（例如，国际象棋）时，启发式很有帮助，但不要更改如何使用极小极大树。

于 2011-12-21T22:01:10.513 回答
0

如果认为问题出在启发式函数上。如你所说，如果 MAX 在状态 (a) 中选择 B，

MIN 将执行动作 A（因为该方块仍然可用），因此 MIN 将获胜

但是在树上你用 *22 而不是 -Inf 来标记它应该是（MIN 获胜）。

于 2011-12-19T11:49:27.513 回答