问题标签 [negamax]

我正在用 Java 制作国际象棋游戏，并且（我认为）已经成功地为 AI 玩家实现了 Negamax。我在为此添加 alpha beta 修剪以改进算法时遇到了一些麻烦。我已经尝试过遵循教程和示例代码，但无法理解它是如何工作的。

以下是我目前必须获得最佳移动的代码：

这是我尝试在我的（工作）negamax 方法中添加 aplha-beta 修剪：

最后是控制台的样子

任何帮助将不胜感激。先感谢您。

我正在制作一个简单的 CLI tic-tac-toe 游戏，其 AI 使用 Negamax 算法和 LISP 进行 alpha-beta 修剪，我对 AI 如何移动有疑问。它没有做出应有的单步棋，而是完全进行游戏，因此游戏仅持续两步。我已经通过（步骤）运行它，看起来问题是在 negamax 函数的（when（> value bestValue））块中设置了 bestPath 变量，即使它说该块没有被执行为。此外，它设置的值不是正确的值，如果它适合设置它的话。有什么建议么？这是我的代码。

这是AI的代码。

注意：如果您认为这篇文章看起来没有足够的细节，例如代码、结果和其他内容，请发表评论；我将相应地编辑帖子。

注2：我自己手工编写了这个程序。

我有一个 negamax 实现，它的结果对我来说看起来很错误我已经尝试了很多调试它的方法，但我似乎仍然无法理解它的症结所在。

首先，这是 Tic Tac Toe 的 negamax 实现，它具有 3X3 板。

以下代码是完整的集合，以复制我在此算法中遇到的错误。如果我错过了什么，请在下面发表评论。

一个例子可以做这个主要的：

我希望游戏以平局结束，因为这是计算机（完美玩家）与计算机（完美玩家），但是，使用以下一组函数，我得到了如下所示的游戏结局：

当前最大移动是：0,0，当前分数是：-inf 当前最大移动是：0,2，当前分数是：3 当前最大移动是：0,1，当前分数是：-3 当前最大移动是：1 ,1, 当前分数是: 3 当前最大移动是: 2,0, 当前分数是: -3 当前最大移动是: 1,2, 当前分数是: 3 当前最大移动是: 2,1, 当前分数是: -3 当前最大移动为：1,0，当前分数为：3 当前最大移动为：1,0，当前分数为：-3

XXO
XOO
XX ---

“ - ”表示该单元格中没有任何动作，这看起来显然是错误的。

我首先实现了我的极小极大值，而这个负极大值在某种程度上基于我的极小极大值实现而发展，这可能是我看不到我的错误的原因。

我知道 minimax 从 2 名玩家的角度进行动作并评估分数也相同，而 negamax 从 2 名玩家的角度进行动作但仅从当前玩家的角度评估分数。

我想这是让我感到困惑的一点。我似乎看不出我的实现在这里出了什么问题。

我通过 main 中的以下函数开始我的游戏：

这是board.hpp：

此处列出的一些关键要素：

打印：

生成动作：

applyMovesNega：

isGameComplete:

评估分数：

删除移动：

这是 move.hpp：

这是实际的 NegaMax 函数：

我使用以下函数评估游戏状态：

我正在学习我的第一个 AI 课程并尝试在我的 c 代码中实现 NegaMax 算法。我正在使用这个算法来玩简单的 Nim 游戏，每个玩家轮流移除 1-3 个匹配项。计算机在这里与自己对抗。但是，我在实施时遇到了麻烦。到目前为止，我似乎无法让函数的每个递归调用都改变状态。我得到一个无限循环，其中最佳值从 -INFINITY 到 INFINITY（其中无穷大为 999999）。所以程序永远不会终止，因为状态永远不会达到 1。我一般在递归方面遇到麻烦，所以如果有人能给我一些关于我应该使用我的代码去哪里的提示，我将不胜感激。

我一直在使用 negamax 玩连接四。我注意到的是，如果我添加 alpha-beta，它有时会给出“错误”的结果，因为在做出失败的举动时，我认为它不应该以我正在搜索的深度进行。如果我删除 alpha-beta 它会按预期播放。alpha-beta 能否切断一些实际可行的分支（尤其是在深度有限的情况下）？这是代码以防万一：

编辑：我不知道为什么有人将我的 TicTacToe 链接为我的问题的重复项，其中甚至没有 MinMax-Algorithm。

目前我正在针对应该使用 MinMax-Algorithm 的计算机进行 Connect4 游戏。在此之前，我们编写了一个也使用 MinMax 的井字游戏，但我不确定如何更改我的旧算法以匹配 Connect4-Game :/。在井字游戏中，我用我写的获胜条件评估了每一个可能的移动，它运行良好，但现在它不适用于我的新条件。我的 makeAMove 等工作正常！

这些是我的旧条件和井字游戏的 MinMax：

//玩家1获胜

}

// 玩家 2 获胜

}

正如我所说，我将这些条件用于我的 MinMax，如下所示：

...

我不确定如何让它适应我的新条件：

我想我必须编写一个评估函数来检查这个例如（这是我的行的wincondition）：

我知道这是很多文字，但也许有人可以给我一些有用的提示:)

谢谢！

最大限度

I'm trying to develop a Tic-Tac-Toe game with an unbeatable AI and am at a point where my negamax function returns correct output most of the time. At times, though, under certain predictable conditions, the computer chooses a board move that doesn't make sense and fails to block a user win.

Based on the research I've done, the negamax algorithm itself seems to look fine. I'm more concerned that there may be something wrong in my evaluation function; in other words, in the way the heuristic value is calculated. Most of my energies were directed at tackling negamax, so the other functions were mostly afterthoughts.

Here's just one example of what I'm describing:

When faced with this scenario, rather than choosing square 1 (top middle: array is zero-indexed) to block user from achieving a win, the negamax function outputs 5, a square that doesn't have any immediate use to either player. However, in testing, if I call negamax on the same scenario with userNum as an argument, negamax does its job and finds the winning square 1 for the user.

I know I'm missing something deceptively simple, and I have a feeling that it's related to the way I've set up userNum and compNum and the way they're hard-coded. I may have taken my Minimax ideas and translated them unsuccessfully to negamax, meaning that I may not be maximizing value for both user and computer. Or I may be maximizing from the wrong player's point-of-view. If someone would kindly provide a push in the right direction, I would be grateful.

The full, working version, along with tests, is available at: https://repl.it/CnGD/4

I didn't want to post an overwhelming amount here, but I can create a snippet on this site if requested.

Negamax function

Evaluation function(s)

我正在尝试实现 Negamax 搜索，以在 Java 中搜索名为Nine Men's Morris的游戏。

如果玩家连续拥有三个棋子（这里称为磨），他会在切换回合之前移除对手的棋子（“额外”移动）。

此外，在放置所有初始棋子之后，还有一个定位棋子阶段和一个移动棋子阶段。

我的实现如下所示：

可能建议不要更改基本的 Negamax 算法并将放置石头和移动石头封装在一个操作中，以便在算法本身中不区分两者，但根据我的理解，它应该仍然像这样工作。

函数 negamaxRemove 与 negamaxSet 基本相同，但不检查磨机（不可能）并寻找要移除的部件。

使用与调用函数相同的参数调用 negamaxRemove 并且不切换符号（从而再次最大化）是否正确？

不知何故，人工智能玩家并没有阻止对手形成一个磨坊（但如果可能的话，他自己形成一个）。

这样的算法是否正确，我应该在代码的其他地方查找错误？还是我误解了 Negamax 应该如何工作？（我注释掉了 alpha-beta 修剪，因此错误地设置 alpha 或 beta 在这里不会产生影响）

我真的很感激一些指示！

我正在尝试为一个简单的游戏实现 negamax，其中玩家交替将一两个添加到运行总和中。将总数增加到 21 的玩家获胜。

我在这里使用伪代码：https ://en.wikipedia.org/wiki/Negamax#Negamax_base_algorithm

人类玩家首先移动，因此计算机应该通过添加使总数等于 0 mod 3 的数字轻松获胜。

我没有做任何动态移动生成。只需将运行总和加 1 的 negamax 分数与运行总和加 2 的 negamax 分数进行比较。

负最大函数：

最大方法：

不知道为什么 AI 每次都加 2。

TLDR：我有一个用于实现 negamax 的不对称评估函数 - 这可以接受吗？还是我需要使它对称？

Longer：我正在编写一个游戏 AI（用于类似国际象棋的棋盘游戏“Hive”），它使用带有 alpha-beta 修剪和非对称评估函数的 minimax。

但是我在正确添加转置表时遇到了麻烦，并且对我的 minimax 实现失去了信心，所以我决定使用这里的伪代码切换到 negamax：https ://en.wikipedia.org/wiki/Negamax#Negamax_with_alpha_beta_pruning_and_transposition_tables

我的一切都“正常工作”了，AFAIK 准确地遵循了伪代码，但我的 AI 现在做出了一些与以前截然不同的动作，通常在 10-15 回合后结束的游戏现在需要 30+，我不相信AI实际上比以前玩得更好。我担心具有不对称的评估函数意味着我对节点的评分与以前不同（因为 negamax 触发器）。

我不想更改为对称函数，除非我真的必须这样做——我一直在尝试通过实验（AI 与 AI 之战）生成一个最佳函数，并且已经投入了数百甚至数千小时的计算时间来生成强大的评估功能。