问题标签 [alpha-beta-pruning]

我有时会编写程序来玩棋盘游戏。基本策略是标准的 alpha-beta 修剪或类似搜索，有时会通过通常的残局或开局方法来增强。我主要玩国际象棋变体，所以当需要选择我的评估函数时，我使用基本的国际象棋评估函数。

但是，现在我正在编写一个程序来玩一个全新的棋盘游戏。如何选择一个好的甚至像样的评估函数？

主要挑战是相同的棋子总是在棋盘上，所以通常的材质函数不会因位置而改变，而且游戏已经玩了不到一千次左右，所以人类不一定会玩够还没有给出见解。（PS。我考虑过 MoGo 方法，但随机游戏不太可能终止。）

游戏详情：游戏在 10×10 棋盘上进行，每边固定 6 个棋子。这些棋子有一定的运动规则，并以一定的方式相互作用，但从来没有一个棋子被捕获。游戏的目标是在棋盘上的某些特殊方格中有足够的棋子。计算机程序的目标是提供与当前人类玩家竞争或更好的玩家。

我花了一整天的时间尝试实现极小极大，但并没有真正理解它。现在，我想我了解极小极大的工作原理，但不了解 alpha-beta 修剪。

这是我对极小极大的理解：

1. 生成所有可能移动的列表，直到深度限制。

2. 评估游戏场对底部每个节点的有利程度。

3. 对于每个节点，（从底部开始），如果层为最大值，则该节点的分数是其子节点的最高分数。如果层是 min，则该节点的分数是其子节点的最低分数。

4. 如果您尝试将其最大化，则执行得分最高的移动，或者如果您想要最小得分，则执行最低的移动。

我对 alpha-beta 剪枝的理解是，如果父层是 min 并且您的节点的分数高于最低分数，那么您可以对其进行剪枝，因为它不会影响结果。

但是，我不明白的是，如果您可以计算出一个节点的分数，您将需要知道低于该节点的层上所有节点的分数（以我对极小极大的理解）。这意味着您仍将使用相同数量的 CPU 功率。

谁能指出我做错了什么？这个答案（为白痴解释了 Minimax）帮助我理解了 minimax，但我不明白 alpha beta pruning 会有什么帮助。

谢谢你。

我有一个基本的 alpha-beta 修剪实现，但我不知道如何改进移动排序。我读过它可以通过浅搜索、迭代深化或将 bestMoves 存储到转换表来完成。

任何建议如何在该算法中实现这些改进之一？

alpha-beta剪枝算法如下：

该算法声明该ACTIONS函数将给出给定 中所有可用操作的列表state。

让我们以跳棋游戏为例。假设一个棋子，比如说A，与另一个棋子，比如说 ，在对角线上B。如果Acan take B，那么这是一个（不可避免的，因为如果可以的话，我们必须采取另一个检查器）动作。或者，如果有多个镜头，这些都是动作。这种情况实际上可以用铅笔和纸画出来。更具体地说，可以使用树来表示情况，其中每个节点代表一个状态，到其子节点的边代表来自该状态的可能动作。

我认为您不需要显式存储树数据结构。但是，上面的算法包含以下语句：return the action in ACTIONS(state) with value v. 现在，ACTIONS(state)将返回某个状态（例如A需要播放的位置）的可能动作。

如果我们计算出所有算法，我们将得到一个 value v，我们将使用v从终端节点传递的值跟随节点。

现在，假设我没有存储来自每个状态的所有可能移动或动作的完整树。当return the action ACTIONS(state) with the value v被执行时，我只会得到引导我进入下一个状态的动作，并且我知道其中一个动作会引导我走向最佳路径。但是，如果我没有额外的簿记，例如完整的树，我是否能够将操作与价值相匹配v？

我目前正在编写一个国际象棋引擎并且已经取得了不错的进展，但是我遇到了一个问题，并希望对这种方式提出一些意见。好的，我的问题是我的国际象棋人工智能没有做出“最好的”举动，它似乎看不到简单的事情，比如它的棋子可能会被收回或其他什么。我的 alpha beta 修剪如下。

我认为我的 alpha beta 修剪效果很好，因为它确实返回了合理的移动，我认为问题在于当我尝试获取我的 rootMove 时。我试图让根移动（

任何想法都会有所帮助，谢谢。

我在 java 中实现了一个 3 * 3 Tic Tac Toe 游戏，仅应用 Minimax 算法。但是，当我将板尺寸更改为 4 * 4 时，程序似乎挂起。我想问我是否应该应用带有 alpha-beta 修剪的 Minimax 来解决这个问题，或者 Minimax 本身可以吗？

有哪些算法可以解决井字游戏？特别是电路板尺寸为 4 * 4 或更大而不是 3 * 3？我尝试了 4 * 4 与 Minimax 和 alpha-beta 修剪，但 pc 似乎挂起并在堆栈溢出时抛出异常。我看到了这些用 javascript 编写的源代码，但我不知道它使用哪种算法，有人可以为我澄清一下吗？ http://js-x.com/page/javascripts__example.html?view=153

我正在编写棋盘游戏。我使用 alpha-beta 修剪生成了一个游戏树，并有 2 个选项：

1. 使用迭代深化来优化 alpha-beta，使其不断生成一层，直到时间结束。
2. 通过反复试验，我知道在时间限制内每个板配置可达到的最大深度，而无需事先检查下层。

哪种方法更好，并且会使搜索达到更深的深度？例如，我知道，一开始我可以生成一棵深度为 X 的树，消耗所有可用的时间......迭代加深可以增加更多深度吗？

让我知道我是否可以更清楚...

I am currently developing a simple AI for Othello using minimax and alpha-beta pruning.

My question is related to the evaluation function for the state of the board.

I am currently looking to evaluate it by looking at:

1. Disc count (parity)

2. Number of legal moves

3. Importance of particular positions

So lets say the root node is the initial game state. The first action is the the AI's action while the second action is the opponent's action.

At node level 1, do I evaluate the disc count of my AI's chips and the number of legal moves it can make at the point of time after it has completed an action?

At node level 2, do I evaluate the disc count of the opponent's chips and the number of legal moves it can make at the point of time after the opponent has completed an action?

Meaning AI move -> Opponent move ==> At this point of time I evaluate the opponent's disc count and the number of legal the opponent can make.

我正在尝试为9Men 的 Morris 游戏实现Game AI 。

到目前为止，我的董事会代表如下：

好的，现在每个节点都表示如下：

一个令牌看起来像这样：

这是我陷入困境的Alpha-Beta修剪算法实现：

好的，这是我目前的功能。我不知道即使我在正确的轨道上？？？

我的功能有什么问题？
请回答我上面的问题（getBestMove() 函数中的 1 到 5）。

提前谢谢你，请排除我的语言错误（我的英语不太好）

非常感谢您的回复！

我以为没有人会回答我:)。我真的帮助我理解我想发生的事情。

因此， CheckWinner( bool )将检查当前玩家到目前为止在此深度是否具有非常好的优势（如获胜或阻止对手等非常好的动作等），如果是，则返回当前玩家的BIG分数。所有这一切都是因为玩家或对手都不会每回合都试图赢得（大比分），对吧？

否则，如果depth =0 则返回当前选定板的评估（分数）（int evaluateBoard()），好吧。

在此之后，我必须生成一个单板（带有单个标记可能的移动）：

好的，现在有了一个新生成的板，递归，如果找到更好的板（具有更好SCORE的板），则将当前板保存到 selectedBoard。如果不是，则切断并返回（不要进一步检查树）。

再次非常感谢你！