问题标签 [minimax]

我必须为 Android 实现一个黑白棋游戏。我已经设法实现了所有游戏，功能齐全，但问题是我没有人工智能。事实上，每走一步，计算机都会移动到使他获得最多棋子的位置。

我决定实现和 alpha-beta 修剪算法。我在互联网上做了很多关于它的研究，但我无法得出最终结论如何去做。我尝试实现一些功能，但无法实现所需的行为。

我的棋盘存储在 Board 类中（在这个类中，每个玩家占用的棋子存储在一个二维 int 数组中）。我附上了一张小图（对它的外观感到抱歉）。

图表：https ://docs.google.com/file/d/0Bzv8B0L32Z8lSUhKNjdXaWsza0E/edit

我需要帮助来弄清楚如何在我的实现中使用 minimax 算法。

到目前为止，我所理解的是，我必须对董事会的价值进行评估。

为了计算棋盘的价值，我必须考虑以下因素： - 自由角（我的问题是我必须只关心自由角，或者我现在可以采取的那个？！这里的困境） . - 棋盘移动性：检查当前移动后可移动的棋子数。-棋盘的稳定性……我知道这意味着棋盘上不能翻转的棋子数量。- 移动将提供给我的件数

我计划实现一个新的 Class BoardAI，它将我的 Board 对象和部门作为参数。

你能告诉我我应该如何实现这个人工智能的逻辑思路吗？在进行深度计算时，我需要一些有关递归的帮助，但我不明白它是如何计算最佳选择的。

谢谢！

我一直在稳定地开发一个国际象棋程序，并且很快就会有一个极小极大搜索、迭代深化和转置表。然而，目前，我有一个错误，我已将其隔离在我的静止搜索中。我很沮丧，因为我直接复制了一个伪代码实现，但它似乎对我不起作用。我在网上找到的其他实现给了我类似的结果。

当多次重新捕获可用时，该错误似乎错误地计算了对手的“最佳”捕获，因此返回一个通常有利于调用搜索的一方的值。

引擎是用 C# 编写的

我的评估函数分别返回有利于白色或黑色的 +/- 值。

我有我认为可能只是这个 Python 代码中的一个同步问题。该代码旨在将极小极大算法应用于井字游戏，通过并行进程而不是单个进程来实现，一一探索所有可能的移动。在将其标记为一个非常糟糕的主意之前，我被要求这样做。

假设未知方法确实与他们的名字所暗示的完全一致，并假设它们可以正常工作（它们已经过手动测试）。我不能 100% 确定的唯一方法是这个，这里是代码：

游戏板用一个简单的Board类（扩展list类）表示。 SimpleQueue和Process类是从multiprocessingPython 模块导入的。 H函数是我实现的启发式函数：它返回对玩家 MAX 有利的棋盘正值，对 MIN 返回负值，对平局返回 0。这是算法代码：

主要方法很简单：

我经常遇到这种错误：

但不总是。递归方法有错误吗？我实在想不通。

我的想法是为每一回合建立一个本地队列，然后从该队列中提取最大/最小值，将其带到“上”队列，即前一回合的队列。

我将参加我学校的棋盘游戏 AI 比赛，并试图提出一些关于并发的想法以获得优势。我很可能会处于劣势，因为我将在 java 中实现它，而且我知道 c 或 c++ 会快得多。

似乎您不能将游戏树分成两半，因为移动顺序应该首先留下最好的移动，而且在给定深度传达当前的 alpha/beta 似乎很困难，甚至可能是不可能的. 我也将使用需要同步的转置表。

除了搜索之外，是否有第二个线程可以做的事情可以帮助搜索或提供某种类型的速度提升。每个 AI 将有 5 秒的时间进行移动，并且您的程序可以在对手思考的同时运行。

任何输入，无论多么晦涩，都将不胜感激。

对于井字游戏等游戏的两个玩家，极小极大算法得到了很好的描述。我需要为坦克游戏编写 AI。在这个游戏中，坦克必须在一个有墙壁形式障碍物的迷宫中移动。目标是收集硬币堆。如果只有两个玩家，则可以实现极小极大算法。但是如何实现两个以上呢？在每个回合中，每个玩家都会尝试最大化自己的获胜优势。我不能将所有玩家视为一个敌人，试图仅减少我的获胜优势，创建两个玩家级别，就像在原始的极小极大算法中一样。如果问题的格式不好，请原谅。这个论坛还是新手

（注意：这不是 CS 作业）

我已经尝试在 Coffeescript 中实现 minimax 游戏树搜索算法，并继续使用我的算法出错。似乎有两个主要问题：1）算法本身在 alpha-beta 修剪期间似乎没有返回正确的值（显然是更大的问题），以及 2）我的游戏板对象，由 9 个整数组成的数组表示，似乎附加到 DOM，使板的复制并将其作为参数传递给 minimax 搜索函数的递归调用有问题。

有 3 类：棋盘、机器人（极小极大算法所在的位置）和游戏。请注意，加载时会启动一个新游戏（相应地弹出调试警报），并且使用预先配置的播放来模拟板以简化调试。

您会注意到，我已经尝试了三个单独的极小极大解决方案尝试（在我的业余时间我一直在努力解决这个问题），后两个现在已被注释掉。在我的最终解决方案中，我一直在关注这个伪代码。

索引.html

board.coffee

机器人咖啡

规则.咖啡

游戏.咖啡

非常感谢任何帮助。

我知道以前有人问过这种问题，但我无法解决我的疑问。我有一个简单的黑白棋引擎（实际上它玩得很好），它使用下面的类来获得最好的移动：

我有一个bestFound实例变量，我的疑问是，为什么必须调用

并传递它？该代码有效，但对我来说似乎很奇怪！

是否有“更好”的方法来获得最佳移动或主要变化？我真的不是递归专家，这很难调试和可视化。谢谢！

**PS：您可以在https://github.com/fernandotenorio/克隆它

我正在尝试用 alpha-beta 修剪为 Java 中的跳棋游戏实现 minimax。我的极小极大算法完美运行。我的代码使用 alpha-beta 代码运行。不幸的是，当我与标准 minimax 算法玩 1000 场比赛时，alpha-beta 算法总是落后 50 场左右。

由于 alpha-beta 修剪不应该降低移动的质量，只是实现它们所需的时间，所以一定是有问题的。但是，我已经拿出纸笔，画出了假设的叶节点值，并使用我的算法来预测它是否会计算出正确的最佳移动，并且似乎没有任何逻辑错误。我使用了这个视频中的树：Alpha-Beta Pruning来跟踪我的算法。它在逻辑上应该做出所有相同的选择，因此是一个有效的实现。

我还将打印语句放入代码中（它们已被删除以减少混乱），并且值正在正确返回它出现并且确实发生了修剪。尽管我尽了最大的努力，我还是无法找到逻辑错误的所在。这是我实现这一点的第三次不同尝试，他们都遇到了同样的问题。

我这里不能贴出完整的代码，太长了，所以我已经包含了与错误相关的方法。我不确定，但我怀疑问题可能出在非递归 move() 方法中，尽管我无法在其中找到逻辑错误，所以我只是在它中翻来覆去，可能会做一些事情没有押韵或理由，更糟而不是更好。

是否有从 for 循环中的递归调用中恢复多个整数值的技巧？它适用于我的 minimax 和 negamax 实现，但 alpha-beta 修剪似乎会产生一些奇怪的结果。

我正在编写一个九人莫里斯游戏，到目前为止，我的 Negascout 搜索工作得很好。但是，我想添加迭代深化，所以我想出了这段代码：

我也使用抽吸窗口。然而，搜索返回最糟糕的举动！我认为问题在于重新/设置搜索窗口。搜索窗口是否应该移到外循环？

我必须创建一个必须与其他 AI 竞争的 AI。

两个 AI 将在相同的硬件上运行，具有相同的处理时间和内存。我知道对手 AI 将使用带有 alpha beta 剪枝的 minimax 算法。

现在我的问题是 - 有什么方法可以击败这样的对手？如果我自己使用 minimax - 那么两个 AI 都可以完美地预测彼此的动作，并且游戏会根据游戏的固有属性（先手获胜等）来解决。

显而易见的解决方案是以某种方式进一步了解可能的移动，这将允许更好的评估 - 因为处理器时间相同，我无法评估更深入的深度（假设相反的 AI 代码同样优化）。我可以使用预先计算的树来获得额外的优势，但如果没有超级计算机，我当然无法“解决”任何非平凡的游戏。

故意选择一个非最佳节点，例如 alpha beta 会修剪的节点，是否有一些价值？这可能会对对手造成 CPU 时间损失，因为他们必须返回并重新评估树。这会对我造成惩罚，而且我必须评估 minimax 树 + alpha beta 以查看 alpha beta 会修剪哪些节点而不会获得任何直接收益。

还有哪些其他策略可以针对这样的对手进行优化？