17

我有一个基本的 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;
    }
}
4

2 回答 2

23

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

    排序应该在此之前完成[在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语句之前添加。

于 2012-04-01T13:00:18.367 回答
4

首先，必须了解 alpha-beta 修剪算法中移动排序背后的原因。Alpha-beta 产生与 minimax 相同的结果，但在很多情况下可以做得更快，因为它不会搜索不相关的分支。

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

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

  1. 你有一位领域专家，他会给你建议什么动作更好。例如，在棋子的国际象棋推广中，用低价值的棋子捕获高价值的棋子通常是好棋。在跳棋中，最好在一次移动中杀死更多跳棋而不是减少跳棋，并且最好创建一个皇后。所以你的移动生成功能之前会返回更好的移动
  2. 您可以从评估深度较小的 1 级的位置（您的浅搜索/迭代深化）中获得移动的启发式方法。您计算了深度 n-1 处的评估，对移动进行了排序，然后在深度 n 处评估。

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

于 2015-10-16T03:04:38.783 回答