java – Alpha-beta移动排序
发布时间:2020-12-14 05:17:17 所属栏目:Java 来源:网络整理
导读:我有一个alpha-β修剪的基本实现,但我不知道如何改进移动顺序.我已经看到可以用浅层搜索,迭代深化或存储最好的转换表来完成. 有什么建议如何在这个算法中实现这些改进之一? public double alphaBetaPruning(Board board,int depth,double alpha,double beta
我有一个alpha-β修剪的基本实现,但我不知道如何改进移动顺序.我已经看到可以用浅层搜索,迭代深化或存储最好的转换表来完成.
有什么建议如何在这个算法中实现这些改进之一? 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,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){ 这些更改应该在方法的第一行中完成[像if(cache,…)((state,board,depth,player))返回cache.get(new State(board,player))]请原谅我缺乏优雅和效率 – 只是在这里解释一个想法].您还应该在每个返回语句之前添加cache.put(…). (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |