问题标签 [minimax]

alpha-beta剪枝算法如下：

该算法声明该ACTIONS函数将给出给定 中所有可用操作的列表state。

让我们以跳棋游戏为例。假设一个棋子，比如说A，与另一个棋子，比如说 ，在对角线上B。如果Acan take B，那么这是一个（不可避免的，因为如果可以的话，我们必须采取另一个检查器）动作。或者，如果有多个镜头，这些都是动作。这种情况实际上可以用铅笔和纸画出来。更具体地说，可以使用树来表示情况，其中每个节点代表一个状态，到其子节点的边代表来自该状态的可能动作。

我认为您不需要显式存储树数据结构。但是，上面的算法包含以下语句：return the action in ACTIONS(state) with value v. 现在，ACTIONS(state)将返回某个状态（例如A需要播放的位置）的可能动作。

如果我们计算出所有算法，我们将得到一个 value v，我们将使用v从终端节点传递的值跟随节点。

现在，假设我没有存储来自每个状态的所有可能移动或动作的完整树。当return the action ACTIONS(state) with the value v被执行时，我只会得到引导我进入下一个状态的动作，并且我知道其中一个动作会引导我走向最佳路径。但是，如果我没有额外的簿记，例如完整的树，我是否能够将操作与价值相匹配v？

我自己的国际象棋引擎使用 minimax 算法搜索国际象棋移动时遇到问题我使用 5 层深度搜索并且仅使用材料/奖励/移动性评估，但它也会做出愚蠢的移动并牺牲有价值的棋子，即使我给他们无穷大（这肯定是一个搜索问题），我没有使用任何类型的修剪，并在几秒钟内给出 5 个深度的搜索结果。

我被这个问题困了一个星期，我确定问题出在回溯而不是国际象棋逻辑（所以没有国际象棋背景的人都会解决这个问题:)）我搜索了很多这是我在 Stack Overflow 中的第一个问题我希望你们不会让我失望:)

这是简单的搜索代码

在这些天里，我一直在努力使用 minimax 算法，我可以说我终于明白了（感谢 stackoverflow 中的另一篇文章）。因此，我打开了我的编辑器，并尝试将其实现为极其简单的（请不要责怪我的代码：P）井字游戏，只是为了尝试一下。一切正常，但计算机移动功能总是检索我-1。我不是要你给我代码，只是要“为什么”这样做。我已经多次搜索代码，但一无所获。该代码可能与我在网上找到的另一个代码非常相似。这是我的代码：

我在 java 中实现了一个 3 * 3 Tic Tac Toe 游戏，仅应用 Minimax 算法。但是，当我将板尺寸更改为 4 * 4 时，程序似乎挂起。我想问我是否应该应用带有 alpha-beta 修剪的 Minimax 来解决这个问题，或者 Minimax 本身可以吗？

我正在研究用于无与伦比的井字游戏的 Minimax 算法。我需要它在计算机先行和播放器先行时都能正常工作。使用当前版本，计算机先行永远不会丢失。但是，如果玩家先走，Minimax 似乎永远不会找到最佳移动（总是返回 -1 作为分数）。

如果玩家迈出第一步，是什么导致计算机返回的 Minimax 得分为 -1？

例子：

这是“Minimax”类：

这是“董事会”课程：

如果有任何混淆，这里是“Mark2”类：

我正在为一个小游戏实现极小极大，并注意到我称之为“拖延”的东西。归结为一个非常简单的例子：

在夺旗游戏中，旗帜距离玩家 A 向上一格，而玩家 B 距离玩家 50 格。轮到A了，他可以向前搜索6步。我所看到的是所有可能的动作都有一个“赢”的价值，因为 A 知道他可以在 B 之前到达旗帜，即使他没有立即抓住它。因此，如果 UP 是顺序中的最后一步，他将向左和向右移动一段时间，直到 B 处于攻击距离之内，然后他必须最终拿到旗帜。

起初这种行为看起来像一个错误，但通过它我说服自己每一步确实是“胜利”，但行为并不好。我可以通过使从现在起 4 步后捕获的标志的价值低于现在捕获的标志来影响评估，但我想知道 minimax 搜索是否有比我遗漏的方面？有没有比后来才获得的同样高分更可取的高分概念？

令人困惑的标题。我将尝试详细说明：我有一个 AI 国际象棋游戏，它使用极小极大搜索来生成计算机的下一步行动。在将极小极大树下到选定的深度（比如 5）之后，它最终会找到下一个最佳移动。出于我自己的测试目的，我希望能够打印出下一个最佳动作（表示为棋盘配置），以及用于确定下一步动作得分的以下 4 个动作。也就是说，在极小极大树中每个较低级别的最佳选择路径，从​​最终被选为最佳下一步的顶部节点开始。有任何想法吗？

我目前正在尝试自学 Minimax 算法，并尝试在 java 中的井字游戏中实现它。但是，我的算法中有一个错误，我无法弄清楚是什么原因造成的。

以下是完整的源代码（对不起，文字墙！）：

这是我运行程序时的输出（计算机是圆圈）：

正如您在第一步之后看到的那样，计算机认为无论它做出什么举动都可以平局（Score = 0）。

在第二步中，我在第 0 列第 1 行打了一个叉。由于某种原因，计算机认为有两个可能的棋步可以达到平局（得分 = 0），只有四个棋步会输（得分 = -1） . 然后它做出了错误的举动，认为它会平局。

我首先认为 hasWon 方法有问题，但是我测试了所有 8 种连续获得三个的方法，它们都返回 true。

我怀疑问题存在于 findBestMove、max 或 min 方法中的某个地方，但我无法准确找出导致它的原因。

如果有人能说出导致错误的原因或就如何更好地调试我的递归算法提供任何建议，我将不胜感激。

我现在为我糟糕的英语道歉，我是意大利人。

我正在用 C#、Player vs Player 和 Player vs Computer 编写一个国际象棋游戏的完整实现，现在我在实现 NegaMax 算法时遇到了一些困难。对于有兴趣的人，这是我的 github 存储库：https ://github.com/crybot/ChessEngine_NOGUI/tree/master/Chess%20Engine%20-%20NOGUI

我试图让这个项目尽可能地面向对象，所以，如果你认为我的设计不正确，请告诉我:)

这是我的问题：

我实现了一个非常简单的评估函数，它对所有玩家对称地工作：

这是我的 NegaMax 函数，它接受一个游戏参数（包括棋盘、玩家、ecc.ecc。）、由枚举提供的 playerColor 和深度搜索；

我首先扫描了 EnginePlayer 的所有可能动作，然后我从 NegaMax 函数中得到了他们的分数，但是有些东西不起作用......

我想这就是全部......我希望你会发现我做错了什么:)谢谢。

编辑： 我实现了一个 Perft，它显示了移动生成器的不正确性。它帮助找到了一些相对容易找到的错误，但最后一些结果仍然是错误的。结果如下：

这是正确的结果：https ://chessprogramming.wikispaces.com/Perft+Results

如您所见，在深度 4，我得到了正确的节点分析，但不正确的捕获和检查值（而配合是正确的）。

由于这些结果，我试图通过在深度 4 处划分每次移动分析的节点来隔离错误，得到这些结果：

并与从 Sharper 获得的那些结果进行比较：

但即使在这里，这些值也是正确的......所以我尝试了深度 5 perft 以获得这些结果：

然后与Sharper的结果进行比较：

所以我意识到问题是由棋子的两次推动产生的动作引起的......但我真的找不到这个错误...... 有没有人有同样的问题？ 或类似的东西，或者只是提示找到那个错误......

谢谢大家 ：）

所以我最近在研究零和游戏中使用的极小极大函数。我完全理解它，除了如何为实际功能实现板：

例如，我发现的这个示例实现有这个声明：

我唯一的问题是到底是Board什么？它是结构、类、数组还是其他结构？另外，我将如何为 mini-max 实现示例板，例如井字游戏板（例如）？在维基百科或谷歌上找不到任何东西。