问题 Alpha-beta移动排序


我有一个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;
    }
}

5977
2018-04-01 12:46


起源



答案:


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

    应该完成排序 之前 这[两者都有 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 声明。


15
2018-04-01 13:00



给出问题中的代码示例,请你提供一个可能的实现或排序(因此在排序列表上递归排序和调用)?我对如何实现它感到困惑。 - FedericoCapaldo


答案:


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

    应该完成排序 之前 这[两者都有 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 声明。


15
2018-04-01 13:00



给出问题中的代码示例,请你提供一个可能的实现或排序(因此在排序列表上递归排序和调用)?我对如何实现它感到困惑。 - FedericoCapaldo


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

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

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

  1. 你有一位领域专家,他会向你提出哪些动作更好的建议。例如,在棋子的棋子推广中,捕获具有较低价值棋子的高价值棋子是平均良好的动作。在跳棋中,最好在移动中杀死更多的棋子,然后减少检查,最好创建一个女王。所以你的移动生成函数之前会有更好的移动
  2. 你可以得到一个启发式方法,即从评估1级深度的位置变小(你的浅层搜索/迭代加深)的移动有多好。您在深度n-1处计算了评估,对移动进行了排序,然后在深度n处进行了评估。

您提到的第二种方法与移动排序无关。这与评估功能可能很昂贵并且许多位置被评估很多时间的事实有关。为了绕过这个,您可以在计算后将其存储在哈希值中,并在以后重复使用。


1
2017-10-16 03:04