0

我正在为 3x4（行 x 列）网格上的 3-in-a-row 游戏的 negamax 算法而苦苦挣扎。它像众所周知的 4-in-a-row 一样播放，即丢掉棋子（不像井字游戏）。让我们称玩家 R 和 B。R 有第一步，B 的动作由 negamax 控制。可能的移动是 1、2、3 或 4。这是在 R：移动 3 --> B：移动 1 --> R：移动 3 之后到达的相关位置：

  1 2 3 4 

| | | | | 

| | | 右 | | 

| 乙| | 右 | |

现在，为了防御 R 的第 3 步，B 必须自己下第 3 步，但它拒绝这样做。取而代之的是，它执行第 1 步，并且在 R 的下一步移动之后游戏结束。

顺便说一句，我花了一整天的时间寻找我的 negamax 实现中的错误，该错误非常适用于 3x3 网格，但我找不到任何错误。

然后我开始思考：对于负最大算法行为的另一种解释是，在 R 在 3x4 网格上以第 3 步开始游戏之后，无论如何 B 在所有变体中都丢失了。

任何人都可以反驳这个命题或指出我的证据（我更喜欢;-)）吗？

谢谢， 塞尔

4

2 回答 2

1

事实上，这是一场从一开始就赢的比赛。并且可以相当容易地用手演奏。我将假设 B 避免了 R 的所有 1 步获胜，并将按颜色标记移动，并在网格中定位游戏发生的位置。

1. R3,1
  ... B1,1  2. R3,2 B3,3  3. R4,1 B2,1  4. R2,2 (and R1,2 or R4,2 wins next)
  ... B2,1  2. R3,2 B3,3  3. R2,2 B2,3  4. R1,1 (and R1,2 or R1,3 wins next)
  ... B3,2  2. R2,1 (and R1,1 or R4,1 wins next)
  ... B4,1  2. R2,1 B1,1  3. R3,2 B3,3  4. R2,2 (and R1,2 or R4,2 wins next)

至于您的算法，我建议您对其进行修改，使其更喜欢胜利而不是失败，并且更喜欢远处的损失而不是近处的损失。如果你这样做，它将“更加努力”以避免不可避免的损失。

于 2011-06-13T17:54:19.663 回答
0

B3也输的证明：

B3：R(1,2,4)->R1；B(1,2,4)->B2（输），所以 B1；R(2,4)->R2 失败，所以 R4；B(2,4)->B2 输，所以 B4；R 现在在任何一个选择上都输了……所以 R1 会输给 R - 所以 R 不会选择它。

B3: R(1,2,4)->R2 因为B2输了，所以R不会选择它 B3: R(1,2,4)->R4; B2（强制）；R2（强制）；B 在 R 的下一步行动中输了

...所以，B3 输给 B 和 B1...所以 B 在这种情况下输了。

编辑：以防万一有人想知道 "B3: R(1,2,4)->R1; B(1,2,4)->B2 (输)，所以B1 "...它们是无关紧要的，因为一旦 Red 选择 R1，这个场景表明 B（计算机）可以选择 B1 并获胜。B 的其他选择会发生什么并不重要——这个选择会赢，所以 Red 不能选择 R1，否则他会输。

于 2011-06-13T17:53:23.793 回答