java - 修剪井字棋动作

Question

我已经写了一个井字游戏代码。我也有 Alpha-Beta 修剪工作。我遇到了一个我需要想法的问题，而不是代码。我如何选择将在 4 步中获胜的步法与将在 8 步中获胜的步法。我遇到的问题是从 minimax/AB 修剪中返回最佳分数的分支可能会在 8 步中获胜，因此它可能会修剪掉可能会在 4 步中获胜的分支。

我遇到了一些想法，例如杀手启发式、转置表和迭代深化搜索。任何想法都会很棒

Answer 1

I would look more into iterative deepening. This would help you find the 4 move win before the 8 move win.

Answer 2

当采取的动作较少时，您的评估应该更高地评价获胜的游戏状态。这应该很容易实现。假设您通常将所有获胜游戏状态的值分配为 100。对于 9 号棋盘，只需将数量（9 - 转）添加到此值。因此，8 回合后的获胜棋盘将评估为 101，5 回合后的获胜棋盘将评估为 104。

Answer 3

您可以这样做的一种方式：

以最大深度 2 进行搜索，如果没有找到胜利，则增加深度限制，直到找到胜利。

对于 tic-tac-toe、killer heuristic、transposition table 来说，这可能有点多，因为您可以将所有棋盘可能性都保存在内存中。

在我的项目中，我使用Proof-Number Search。但是有很多算法可以使用。你也可以在这个网站上找到想法，但即使是关于国际象棋的，大部分想法都可以用于你的项目。

Answer 4

（想在评论中包含这个，但它变得太长了）

迭代深化可能是这个问题最简单的“修复”。只需将 alpha-beta 搜索放入一个循环中，该循环会稳步增加 alpha-beta 的深度。您可以在循环中包含几个测试，以使其提前终止（例如，找到获胜的举动）。

前任：

while (!win_found && depth < 8)
{
    alphaBetaSearch(win_found, depth);
    depth++;
}

迭代深化可能看起来很浪费，因为状态是多次生成的，但事实证明这并没有那么昂贵。这样做的原因是在每个级别具有相同（或几乎相同的分支因子）的搜索树中，大多数节点都位于底层，因此多次生成上层并不重要。

Answer 5

如果你用编译语言编写，你可以在不到一秒的时间内从第 1 步开始搜索整个树，而不需要任何启发式方法（只有 alpha beta 和 eval 函数返回 -1,0,+1），否则它不应该花费超过 5 秒第一步，而其他步则更少。

Answer 6

我相信 tictactoe 实际上已经“解决”了，因为有一种算法可以保证获胜或平局，至少形成初始状态，因此 alpha-beta 搜索似乎过度。（除非您只是学习在比国际象棋或其他更简单的游戏中实现它）

Answer 7

在 alpha beta 修剪函数开始时，我假设你有这样的东西：

function alphabeta(node, α, β, maximizingPlayer) is
    if node is a terminal node then
        return 100

相反，如果您在终端节点中，请计算空方格的数量并将其添加到节点的值中。

function alphabeta(node, α, β, maximizingPlayer) is
    if node is a terminal node then
        bonus = count_empty_squares(node)
        return 100 + bonus

阿尔法贝塔算法将有利于最快的获胜。