java - 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

• 使用浅搜索对节点重新排序很简单:计算递归之前状态的每个 child 的启发值检查它们。然后，对这些状态的值进行排序[降序对于最大顶点，对于最小顶点升序]，并递归调用排序列表中的算法。这个想法是 - 如果一个国家擅长浅深度，也更有可能擅长深度状态，如果这是真的 - 你会得到更多的修剪。

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

  for (Move move : children) {

• 存储移动也很简单 - 许多状态计算两次，当你完成计算任何状态时，将其存储[深度为计算!这很重要!] 在 HashMap 中。你做的第一件事当您开始计算顶点时 - 检查它是否已经计算 - 如果是，则返回缓存值。背后的想法就是许多状态可以从不同的路径到达，所以这个方式 - 您可以消除冗余计算。

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