Alpha-beta移动排序

Question

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

有关如何在此算法中实现这些改进之一的任何建议？

 public double alphaBetaPruning(Board board, int depth, double alpha, double beta, int player) {
    if (depth == 0) {
        return board.evaluateBoard();
    }

    Collection<Move> children = board.generatePossibleMoves(player);
    if (player == 0) {
        for (Move move : children) {
            Board tempBoard = new Board(board);
            tempBoard.makeMove(move);
            int nextPlayer = next(player);
            double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer);
            if ((result > alpha)) {
                alpha = result;
                if (depth == this.origDepth) {
                    this.bestMove = move;
                }
            }
            if (alpha >= beta) {
                break;
            }
        }
        return alpha;
    } else {
        for (Move move : children) {
            Board tempBoard = new Board(board);
            tempBoard.makeMove(move);
            int nextPlayer = next(player);
            double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer);
            if ((result < beta)) {
                beta = result;
                if (depth == this.origDepth) {
                    this.bestMove = move;
                }
            }
            if (beta <= alpha) {
                break;
            }
        }
        return beta;
    }
}

public int next(int player) {
    if (player == 0) {
        return 4;
    } else {
        return 0;
    }
}

Answer 1

• 使用浅搜索进行节点重新排序是微不足道的:在递归检查状态之前,计算状态的每个子​​节点的启发式值.然后,对这些状态的值进行排序[降序为最大顶点,升级为最小顶点],并在排序列表上递归调用算法.这个想法是 - 如果一个国家擅长浅水深处,它也更有可能擅长深度状态,如果它是真的 - 你会得到更多的修剪.

  排序应在此之前完成[在两个if和else子句中]

  for (Move move : children) {

• 存储移动也是微不足道的 - 许多状态计算两次,当你完成任何状态的计算时,存储它[与计算的深度!它是重要的!]在一个HashMap.当你开始计算一个顶点时,你要做的第一件事 - 检查它是否已经计算 - 如果是,则返回缓存的值.它背后的想法是许多状态可以从不同的路径到达,所以这样 - 你可以消除多余的计算.

  改变应该在方法的第一行[类似if (cache.contains((new State(board,depth,player)) return cache.get(new State(board,depth,player))] [请原谅我缺乏优雅和效率 - 只是在这里解释一个想法].
  您还应该cache.put(...)在每个return语句之前添加.

Answer 2

首先，我们必须了解 alpha-beta 剪枝算法中移动顺序背后的推理。Alpha-beta 产生与极小极大相同的结果，但在很多情况下可以更快，因为它不会搜索不相关的分支。

它并不总是更快，因为它不能保证修剪，如果事实上在最坏的情况下它根本不会修剪并搜索与 minimax 完全相同的树，并且由于 a/b 值簿记而会更慢。在最好的情况下（最大修剪），它允许同时搜索树的两倍深度。对于随机树，它可以同时搜索 4/3 倍的深度。

移动排序可以通过多种方式实现：

1. 您有一位领域专家可以为您提供更好的建议。例如，在国际象棋棋子的推广中，用低价值棋子吃掉高价值棋子通常是好棋。在西洋跳棋中，最好在一步棋中杀死更多的棋子，然后减少更少的棋子，并且最好创建一个皇后。所以你的移动生成函数会返回之前更好的移动
2. 通过评估较小深度的 1 级位置（浅层搜索/迭代加深），您可以得到启发式的移动效果有多好。您计算了深度 n-1 处的评估，对移动进行排序，然后在深度 n 处评估。

您提到的第二种方法与移动顺序无关。这与评估函数可能很昂贵并且许多位置被评估很多次这一事实有关。要绕过这个问题，您可以在计算出位置值后将其存储在哈希中，并在以后重复使用。