阿尔法-贝塔移动排序

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

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

 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;
    }
}

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

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

    for (Move move : children) {

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

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


答案 2

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

它并不总是更快,因为它不能保证修剪,如果事实在更糟糕的情况下,它根本不会修剪,并且搜索绝对相同的树作为minimax,并且由于a / b值簿记而会变慢。在最好的情况下(最大修剪),它允许同时搜索2倍深度的树。对于随机树,它可以同时搜索4/3倍的深度。

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

  1. 您有一位领域专家,他会为您提供哪些举措更好的建议。例如,在棋子的国际象棋推广中,用低价值棋子捕获高价值棋子平均是好的举动。在跳棋中,最好在一招中杀死更多的跳棋,然后少一个跳棋,最好是创造一个女王。因此,您的移动生成函数会返回更好的移动之前
  2. 你得到了从评估深度小于1级的位置(你的浅层搜索/迭代深化)的移动有多好的启发式方法。您在深度 n-1 处计算了评估值,对移动进行了排序,然后在深度 n 处进行了评估。

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