问题标签 [alpha-beta-pruning]

I've implemented an alpha beta search with iterative deepening and i've read several techniques to further optimize the algorithm by searching for the best move first that came up from previous depth search.

as far as i understand, can i just store the principal variation from the previous depth search in dynamic length list? for example, suppose i have searched until depth 4 with PV : [1, 0, 2, 3] means that at depth 1, choose move number 1, at depth 2 choose move number 0, at depth 3 choose move number 2 , etc..., and then for depth 5 search, the algorithm will first search the child of the node from that previous depth PV.

is that what you call the refutation tables?

description of refutation table from this link : For each iteration, the search yields a path for each move from the root to a leaf node that results in either the correct minimax score or an upper bound on its value. This path from the d - 1 ply search can be used as the basis for the search to d ply. Often, searching the previous iteration’s path or refutation for a move as the initial path examined for the current iteration will prove sufficient to refute the move one ply deeper.

if it's not the same, can you explain what is refutation table really is(because to me, both seems equal, but im not sure) and what is the advantage of using the refutation tables instead of the way i mentioned first?

我了解 minimax 和 alpha-beta 修剪的基础知识。在所有文献中，他们谈到最佳情况的时间复杂度是 O(b^(d/2))，其中 b = 分支因子，d = 树的深度，基本情况是所有首选节点都首先展开。

在我的“最佳情况”示例中，我有一个 4 级的二叉树，所以在 16 个终端节点中，我最多需要扩展 7 个节点。这与 O(b^(d/2)) 有什么关系？

我不明白他们是如何得出 O(b^(d/2)) 的。

我正在尝试开发一个简单的国际象棋引擎，但我正在努力解决它的性能问题。我已经使用 alpha-beta 修剪和迭代加深（没有任何额外的启发式方法）实现了 Negamax，但我无法获得超过 3-4 层的合理搜索时间。这是游戏开始时我的程序日志的摘录：

它表明分支因子大约是 10。我已经读过，通过正确的移动排序，我应该得到大约 6 的东西，所以我怀疑我的排序是错误的。它目前以这种方式工作：

1. 游戏树节点有一个其子节点的链表；最初，捕获和提升是在安静的移动之前放置的
2. 在搜索过程中，增加 alpha 或导致 cutoff 的 child 被放置在列表的开头
3. 在下一次迭代加深 PV 时应先搜索

这是一种正确的方式来订购移动和我得到的分支因子是可以预期的吗？目前我正在使用一个简单的静态评估函数，它只考虑位置的材料差异 - 这可能是截止率低的原因（如果还考虑了数字的流动性，我会得到类似的结果）？诸如减少无效移动或杀手启发式等技术是否会显着帮助（不是 10-15%，而是一个数量级）？我不希望我的引擎很强大，但我希望分支因子约为 6。

我必须做一个项目，我们需要实现 mancala 棋盘游戏，然后还为它实现 AI。

我们被告知，我们需要修改或更改极小极大树以能够与 mancala 一起使用，因为在游戏中玩家可以连续进行多个回合。

我已经实现了我的游戏逻辑和 GUI，但现在在我开始使用 AI 之前，我想尝试了解它背后的理论。我在网上搜索了基于非回合的迷你最大树，但我似乎找不到任何东西。但是我看到很多人在谈论使用 minimax 做 mancala。

现在我了解了正常的极小极大树以及每个级别如何在最小节点和最大节点之间交替。有了我现在需要的树，我会说： min > max > max > min > max如果第二个玩家有两个回合？

我们还需要能够指定 Minimax 树的给定层深度。我们还需要进行 alpha beta 修剪，但那是稍后，一旦我真的有一棵树。

我知道以前有人问过这个问题，但我无法弄清楚这个问题。

我有一个 7x7 板，用于连接 4ish 游戏。

我定义了这个方法，来实现 Minimax 的 Alpha Beta 剪枝。

它应该返回我的启发式，并设置最佳移动。但我总是得到最好的移动，因为是我棋盘上最后一个可用的移动....

这里有什么我可能会丢失的吗？

谢谢！

我一直在寻找名为 Duchess http://www.cse.unsw.edu.au/~blair/duchess/rules.html的游戏的算法/方法

我正在考虑 alpha beta 修剪，但我不知道它是否适用于两个以上玩家的游戏。

我理解杀手启发式背后的想法以及它为什么有用。我正在努力解决的是如何在 Alpha-Beta 搜索例程中实现它。特别是，如何保证只有兄弟节点的杀手锏先被尝试？伪代码会有很大帮助。

我尝试制作具有不同棋盘大小和棋子的井字游戏来获胜。

我有取决于开放路径的评估功能。例如，如果我们有

我们得到 10^2（垂直第一列）+ 10^1（垂直第二列）+ 10^1（对角线）+ 10^1（水平第二行）+ 10^1（最后水平行）。

为了获得最好的最佳移动，我使用功能：

程序查找移动，但它并不总是最好的。特别是当对手有2次获胜机会时，他看不到动作。而且当算法有获胜的动作时，他首先会阻止对手。例如：

如果计算机是 O，他会先阻止 X，但它不应该。

你能告诉我在这个功能上我可以改进什么吗？也许有我看不到的错误:(评估功能工作正常我写了单元测试来测试它。

我正在尝试开发一个国际象棋程序。这将是对树的常规蛮力搜索，唯一不同的是评估。最初，我将使用 Claude Shannon 设计的标准评估器，以便更容易测试它是否在基础上工作正常。移动列表生成和它周围的所有其他基础设施都可以正常工作。

现在进行搜索：我想使用wikipedia的 alpha/beta 修剪代码示例。这就是一个问题：它对一件事模棱两可；应该从谁的角度进行评估？我已经用谷歌搜索了好几天（字面意思），但没有一个例子明确说明这一点。所以：评估应该是

• 从那个深度的“当前推动者”的角度来看
• 从那个深度的“当前行动的对手”的角度来看
• 从树根的移动者的角度来看，例如正在为其进行树搜索的人（AI 玩家）
• 从树根的移动者的对手的角度来看

?

我实验性地尝试了 rootSide、side、rootOpponent，基本上所有选项，然后让它们互相对抗。这样做的结果是，“在那个深度的当前推动者”将是使用的那个（它最常获胜），但是针对任何其他引擎测试该版本会导致 100% 的损失。

当然，维基百科会更新得更清楚！（请忽略维基百科历史中的注释：那是我自己写的，可能不正确，所以我删除了它）

我正在尝试将 Alpha Beta 修剪添加到我的极小值中，但我不明白我哪里出错了。

目前我正在经历 5,000 次迭代，据一位朋友说，我应该经历大约 16,000 次迭代。选择第一个位置时，它返回 -1（失败），而此时它应该能够肯定返回 0（平局），因为它应该能够从空板中抽奖，但是我看不到当我遵循我的代码时，我哪里出错了，这似乎很好

奇怪的是，如果我在检查中切换返回 Alpha 和 Beta（以实现返回 0），计算机将尝试绘制但不会启动任何获胜动作，只会阻止

我的逻辑流程

如果我们正在寻找 alpha：如果分数 > alpha，则更改 alpha。如果 alpha 和 beta 重叠，则返回 alpha

如果我们正在寻找 beta：如果分数 < beta，则更改 beta。如果 alpha 和 beta 重叠，则返回 beta

这是我的递归调用

初始调用（当计算机应该选择一个位置时）

任何有关我的逻辑流程的帮助将使计算机返回正确的结果并做出明智的举动将不胜感激