我已经实现了一个基本的阿尔法-贝塔剪枝算法，但不知道如何改进移动排序。我读到可以通过浅层搜索、迭代加深或将最佳移动存储到转换表中来实现这一点。
关于如何在该算法中实现这些改进之一，有什么建议吗？
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; }}回答：
-
使用浅层搜索进行节点重新排序非常简单：在递归检查每个子节点之前，计算每个子节点的状态的启发式值。然后，根据状态值进行排序（对于最大顶点按降序，对于最小顶点按升序），并在排序后的列表上递归调用算法。基本思路是，如果一个状态在浅层深度表现良好，那么它在深层状态下也更可能表现良好，如果这是真的，你将获得更多的剪枝效果。
排序应该在以下代码之前进行（在
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(...)。
