问题标签 [negamax]

我正在尝试在 Haskell 中实现Negamax算法。

为此，我代表游戏在玫瑰树中的未来可能性（Data.Tree.Forest (depth, move, position)）。但是，通常可以通过两种不同的移动顺序到达某些位置。重新评估重复位置（的子树）是一种浪费（并且很快变得非常慢）。

这是我到目前为止所尝试的：

• 实现打结的变体以共享常见的子结果。但是，我只能找到为（可能是无限的）列表打结的解释，而没有找到关于重用子树的解释。

• 我考虑过的另一种方法是在Statemonad 内构建一棵树，其中要保留的状态将是Map (depth, position) (Forest (depth, move, position))执行显式记忆，但到目前为止我也无法正确设置它。

我认为这两种方法都可能存在只能以核心递归方式构建博弈树的问题：我们不是从叶子到根构建树，而是从根向下懒惰地构建一个（可能是无限的）树。

编辑：给你一个我目前正在使用的代码的例子（太慢了）：

（TypeFamilies 用于允许每个Game实现都有自己的 a 概念，Move然后需要 FlexibleContexts 来强制Move s实现Ord.

我正在尝试为我的 negamax AI（不是国际象棋 - 10-10-5 mnk 或名为 Take 5 的五子棋风格的游戏）实现一个简单的静止搜索。它已经有一个转置表。主要的 negamax 算法如下所示：

我在网上寻找了一些静止搜索算法，但它们似乎无法正常工作，但这就是我想出的：

你能检查我是否正确地实现了这个算法的静止搜索？

Negamax 通常如下所示：

最初的调用是negamax(rootNode, depth, −∞, +∞, 1)最大化玩家调用它。

我以最大化玩家调用它的方式实现了 Negamax，但每个rootNode都是最大化玩家的移动之一：

因为 Negamax 返回一个值，所以我想要一个棋盘状态（移动）。所以我手动做第一级的 Negamax，这样我就可以解析出最好的移动在哪里。但是我应该呼吁什么价值观negamax？为了更具说明性，如果最大化玩家调用negamaxHandler，应该negamaxHandler调用：

或者是其他东西？澄清：

• 最大化玩家通话negamaxHandler
• 每个顶级调用negamaxinnegamaxHandler应该最小化

这将是一堵巨大的代码墙，但我希望有人有时间和耐心来帮助我。

我目前正在尝试为我的 HTML Tic-Tac-Toe 游戏创建一个 AI 播放器。我正在使用这个资源，其中包含使用 minimax 算法在 Java 中编写的工作 AI 播放器代码：https ://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html （第 1.5 节）

我想把这个给定的 Java 代码翻译成 JavaScript。资源代码和我的 HTML/JS 代码之间的一个主要区别是资源使用二维数组作为游戏板，而我使用一维数组。

这意味着资源的数组如下所示：Cell[][] cells;其中第一个索引代表行，第二个索引代表列；我的数组看起来像这样：let board_array = [];它的长度为 9，表示从左上角到右下角读取的棋盘，例如，左上角的单元格位于索引 0 处，而中间右侧的单元格位于索引处 5。

另一个小的区别是资源使用玩家种子存储在单元格数组中，而我只'X'为人类和'O'人工智能使用字符串。

我花了很多时间尝试将给定的 Java 函数转换为我的 JS 脚本，但无论我尝试什么，minimax总是返回-1作为最终的最佳单元格，据我了解，只有在没有更多可用单元格的情况下才会发生，这表明游戏已经结束。我已经进行了一些console.log 调试，我可以看到在递归过程中，实际上返回了合法的最佳单元格（例如0 或4），但在最终返回时它始终为-1。

我敢打赌，我的错误要么在于从二维数组到一维数组的有缺陷的转换，要么与 JS 在特定行中所做的与 Java 完全不同的事情有关。我可以想象WINNING_PATTERNS数组中的二进制值或hasWon函数中对它们的操作可能会造成麻烦。我不知道它在 JS 中是否像这样工作，但它不会抛出任何错误，所以我无法自己弄清楚。

无论如何，这是我的代码：

我的 Negamax 算法有问题，希望有人能帮助我。

我正在用 Cython 写它

我的搜索方法如下：

在许多示例中，您在检测到截止后中断，但是当我这样做时，算法找不到最佳解决方案。我正在测试一些国际象棋谜题，我想知道为什么会这样。如果我在检测到截止后返回最大数量它工作正常但我需要很长时间（深度 6 为 252 秒）......

速度：节点前秒：21550.33203125

或者，如果您有其他改进，请告诉我（我使用转置表、pvs 和杀手启发式）

我不明白为什么按原样使用表条目的标志。例如，考虑带有 alpha-beta 修剪和转置表的 Negamax伪代码，并专注于 TT 部分。

没关系。如果 entry 包含确切值的下限，我们会尝试从左侧缩小窗口，等等。

而这部分我不明白。如果值太小，为什么要设置 UPPERBOUND 标志？value位于搜索窗口的左侧——它小于已知的下限—— alpha。所以看起来价值应该是一个LOWERBOUND。

从我的测试以及每个人都使用该版本的事实中可以看出，我的逻辑肯定是错误的。但我不明白为什么。

我有一个带有 alpha-beta 修剪的普通 Negamax 算法，它是通过迭代加深 (ID) 启动的。我认为要真正使用 ID，我将从深度 1 计算的有效移动保存在表格中，所以下次我去深度 2 并且相同的原始位置到达时，我可以从表格中获取有效移动来节省时间. 但是，我发现这个想法并没有真正节省任何时间，这让我想到：

1. 我从未见过有人这样做，出于某种原因不值得吗？
2. 我的实现是错误的？
3. 我对 Negamax 的工作方式感到困惑，也许这首先是不可能做到的？

这是原始的迭代调用，以及 Negamax 函数本身的片段：

我的完整程序中最耗时的任务是这样分布的（占游戏总运行时间的百分比）：

• 计算有效动作：60%
• 评估函数（目前中等复杂度）：25%
• Negamax 本身具有查找、表格保存等功能：5%
• 做出/取消动作：4%

计算移动时间这么高是否正常/合理？这是我首先考虑将有效动作保存在列表中的主要原因。

或者有人可以解释为什么这是一个好/坏的主意，我应该怎么做？感谢您的任何意见。

我的国际象棋算法是基于 negamax 的。相关部分是：

如果我能够访问 negamax 算法基于其评估的移动序列（在决策树上找到评估值的位置），这将极大地帮助调试。

目前我正在尝试将棋盘的移动历史保存到作为封闭类字段的哈希图中。但是，由于某种原因，它不起作用，因为产生的移动序列不是最佳的。

由于对 negamax 的直觉并不是很容易，所以我已经把头撞到墙上已经有一段时间了。如果有人能指出我正确的方向，我将不胜感激！

我尝试使用带有 alpha-beta 修剪的 Negamax 在 C 中创建一个国际象棋引擎，但我无法让它工作。它在游戏的前几个动作中按预期工作，并开始在没有目标的情况下牺牲棋子。但是当它接近尾声时，它似乎再次按预期运行。我已经尝试调试了大约一个星期，但没有任何成功。任何帮助是极大的赞赏。以下是相关代码：

嘿，我正在尝试使用 alpha-beta 和 4 名玩家的静默搜索来实现 negamax，但它有点不同。例如，假设0 = Red、1 = Blue、2 = Yellow、 和3 = Green以及 Red 和 Green 在同一个团队中，这意味着 2 个回合将是最大化者，2 个回合将是最小化者。这是我基于 wiki 的实现。

这似乎无法正常工作，我认为如果下一个要移动的玩家在我的团队中，我们不应该切换 alpha 和 beta 并且不要反转值。关于我做错的任何事情的任何建议。