问题标签 [negamax]

对不起，如果这是一个愚蠢的问题，但我很困惑。Negamax 在开始时检查是否已达到结束状态或最大深度。然后，您插入一个评估函数，该函数返回该状态的负分或正分（一个对一方有利，对另一方不利，反之亦然）。我发现很难理解的是下面的否定。这是否意味着返回的分数乘以-1？这能达到什么目的？我很欣赏叶子状态的“泡沫”备份在最小/最大分数之间交替。

线：-NegaMax(c, depth+1, 1-color)

在我创建的游戏中，Negamax 适用于低深度搜索，但更大的深度增加会导致它冻结。我想过将深度更改为输入“long”而不是“integer”，但不确定我还能做什么。我知道计算将花费更长的时间，因此它可能在幕后进行计算，我将其解释为冻结。任何意见，将不胜感激。在游戏中，玩家只能在一个位置上做出 3 个可能的移动中的 1 个，它不像国际象棋那样在任何位置都可能有大量移动，并且很难到达最终位置。

谢谢

达兹

我正在用 C++ 制作一个国际象棋引擎，使用这个算法，我得到预期的最大深度设置为 1 的游戏。然而，除此之外，它忽略了处于危险中的棋子，甚至似乎愿意将自己置于危险之中。

这是我的代码：

I'm making an Othello player, and implemented a minimax algorithm with alpha-beta pruning. Then I did a bunch of research on the best ones online and keep hearing about a "negamax" algorithm that they all use. It seems like most people think negamax is faster than minimax (i think because it doesn't switch between min and max player?), so I'd like to turn my minimax algorithm into negamax if that's not too difficult.

I was wondering if people had any insight on how much faster using negamax is, and any tips or code on how to turn my minimax code into a negamax algorithm that'd be appreciated!

Here's my minimax algorithm:

Since I got a response asking about my Alpha-beta pruning, here is that:

我已经为类似国际象棋的游戏制作了一个 negamax 算法，我想知道如何使用最终的棋盘值结果。我知道 negamax 算法的最终回报代表了玩家采取最佳行动后棋盘的价值，但这并不是完全有用的信息。我需要知道那个动作是什么，而不是它的价值。

这是代码：

我想在确定 bestValue 后重新评估当前匹配状态的孩子。然后我遍历它们并找出其中哪些孩子的 stateScore 等于 bestValue。但这行不通，因为无论如何他们中的很多人都会有相同的 stateScore，这是他们可以导致的结果......

我正在尝试为 Connect 4 实现 NegaMax ai。该算法在某些时候运行良好，并且 ai 可以获胜。但是，有时它完全无法连续阻挡对手3个，或者当它连续3个时没有获胜。

评估函数遍历网格（水平、垂直、对角向上、对角向下），并采用每组四个正方形。然后，它在每个集合中进行检查并基于此进行评估。

我基于此处提供的评估代码的功能：http: //blogs.skicelab.com/maurizio/connect-four.html

我的功能如下：

我的 negamax 函数如下所示：

我知道连接四已经解决，肯定有更好的方法来解决这个问题，但是任何有关修复/改进此问题的帮助或建议将不胜感激。谢谢！

我正在尝试为井字游戏应用程序实现 negamax 搜索功能，但它不会返回最佳值，而是似乎是半随机猜测的。这是我的代码的相关部分：

需要注意的是，我没有将棋盘作为参数传递，而是将棋局的结果作为参数传递，可以是 WIN、DRAW、VALID 或 OCCUPIED（最后 2 个与当前讨论无关），这些都是不言自明。Coordinate 类只保存移动的行和列值。

非常感谢 ：）

我目前正在实施一个跳棋游戏，唯一阻碍我的是我的人工智能状态不佳。它是用 Groovy 编写的。

我有以下（尝试的）带有 alpha、beta 修剪的 negaMax 算法。我已经遵循了几个伪指南，但我显然在某个地方失败了，因为结果相当荒谬。

该方法调用如下：negaMax(3, Integer.MIN_VALUE, Integer.MAX_VALUE, 1)

我已经决定 1 将是电脑播放器；其他任何东西都是用户。

我选择了一个移动的哈希映射，键作为检查器（Piece 对象），值作为实际移动。我认为仅存储动作没有任何意义，因为我需要跟踪实际可以实现的动作。

我利用另一个哈希映射来存储后继评估，再次将检查器存储为键，但这次我存储了值的位置和位置分数（我为此创建了一个类 PositionAndScore）。

evaluateGameState 函数初始化该玩家可以移动多少棋子的分数，为任何国王加一分，为任何处于可取位置的棋子收回一分。

玩的时候，电脑做的前两个动作看起来很聪明，但从那以后，它就走下坡路了。很多时候，计算机试图做出无效的动作，因此它们不会执行。

我将非常感谢任何给我时间来查看我到目前为止所做的事情并评论是否有任何问题的人。

非常感谢。

编辑：好的，我取得了一些进展。正如我可能没有提到的，evaluations哈希图用于计算计算机的最佳移动。它从中获得最高分。

这导致的问题是，对于玩家为 1 的每个循环都添加了评估哈希图，因此添加了不合法的动作（但即它们是未来的动作）。

为了解决这个问题，我决定添加一个名为的前体方法callSearch()，而不是negaMax使用所有相同的参数来调用它，但是它也rootDepth将depth.

然后我对算法做了这个小改动

我的想法是，一旦搜索回到根，我只想添加后继评估。

无论如何，完成所有这些操作后，计算机不再尝试进行非法移动，但它仍然无法做出有效的移动。这可能是我的评估功能，虽然有点初级。

我正在尝试构建一个国际象棋 AI，但遇到了一个奇怪的错误。作为前言，我确实通过了 stackoverflow 并尝试找到类似的问题，但这对我没有帮助，因为我认为我正在正确实现元组解包并且我似乎无法在我的代码中找到错误。

下面是我的 negamax 函数的代码。它包含棋盘、当前玩家和当前深度。
它使用 board.evalFunction() 函数将代表棋盘位置值的数字返回给当前玩家。该功能工作正常。我已经标记了出现错误的行：ValueError: need more than 0 values to unpack。
有人可以帮我吗？

好的，所以我先承认这会有点长。我正在为 C# 编写一个国际象棋引擎，最终目标包括 UCI 实现。我已经做到了，给定一个棋盘，引擎将生成所有有效动作的列表；但是，我的评估代码似乎在挣扎，因为在与自己对战时，引擎会在两边移动两个棋子，然后在两边来回移动一个棋子。我将在下面概述程序的关键部分，以便最好地让您了解我的代码在什么条件下被调用和使用，希望它能帮助您回答我的问题。

这只是我的接口调用的主要方法，这里没有什么令人兴奋的。

这种方法工作得很好。它返回格式为 x1、y1、x2、y2、权重的移动列表。此方法生成的权重是任何被杀死的棋子的值。如果您有任何问题，请告诉我。

这个方法还不完整（因为它不处理castling 或en passant），但它基本上只是从任何给定的移动生成一个新的棋盘对象。

可能不需要此代码，但我将其包括在内是因为此处的拼写错误导致错误。这只是一个非常基本的用户界面，允许我与我的引擎玩游戏，或者让引擎自己玩。

现在，在介绍评估算法本身之前，我将做一个简短的切线。这是您在整个代码中多次引用的板对象。它包含一个棋盘数组，以及定义游戏当前状态所需的其他变量。

现在我已经概述了我的程序的其余部分，这里是评估方法本身。代码接受一个移动列表，如果它到达应该搜索的最远深度，它只会返回具有最大绝对值的移动。如果它没有到达底部，它只是为它收到的期货列表中的每一步生成一个期货列表，然后再次调用自己。然后将返回的值添加到原始移动的权重，并与迄今为止找到的最佳移动进行比较。但是，我一直在使用这种方法时遇到问题，我猜可能是因为我误解了 negamax 应该如何工作，或者我在此过程中的某个地方打错了字。知道发生了什么吗？