如何实现高效的α-Beta剪枝游戏搜索树？
我正在努力学习人工智能以及如何在一个程序中实现它。最容易开始的地方可能是简单的游戏(在本例中是Tac Toe)和游戏搜索树(递归调用，而不是实际的数据结构)。关于这个话题的讲座，我发现了这个非常有用的视频。
我遇到的问题是，对该算法的第一个调用需要非常长的时间(大约15秒)才能执行。我已经在整个代码中放置了调试日志输出，似乎调用算法部分的次数太多了。
下面是为计算机选择最佳操作的方法：
public Best chooseMove(boolean side, int prevScore, int alpha, int beta){
Best myBest = new Best();
Best reply;
if (prevScore == COMPUTER_WIN || prevScore == HUMAN_WIN || prevScore == DRAW){
myBest.score = prevScore;
return myBest;
}
if (side == COMPUTER){
myBest.score = alpha;
}else{
myBest.score = beta;
}
Log.d(TAG, "Alpha: " + alpha + " Beta: " + beta + " prevScore: " + prevScore);
Move[] moveList = myBest.move.getAllLegalMoves(board);
for (Move m : moveList){
String choice;
if (side == HUMAN){
choice = playerChoice;
}else if (side == COMPUTER && playerChoice.equals("X")){
choice = "O";
}else{
choice = "X";
}
Log.d(TAG, "Current Move: column- " + m.getColumn() + " row- " + m.getRow());
int p = makeMove(m, choice, side);
reply = chooseMove(!side, p, alpha, beta);
undoMove(m);
if ((side == COMPUTER) && (reply.score > myBest.score)){
myBest.move = m;
myBest.score = reply.score;
alpha = reply.score;
}else if((side == HUMAN) && (reply.score < myBest.score)){
myBest.move = m;
myBest.score = reply.score;
beta = reply.score;
}//end of if-else statement
if (alpha >= beta) return myBest;
}//end of for loop
return myBest;
}如果点为空并返回值(-1 -人赢，0-平局，1-计算机赢，-2或2-否则)，则makeMove方法进行移动。虽然我认为错误可能在getAllLegalMoves方法中：
public Move[] getAllLegalMoves(String[][] grid){
//I'm unsure whether this method really belongs in this class or in the grid class, though, either way it shouldn't matter.
items = 0;
moveList = null;
Move move = new Move();
for (int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
Log.d(TAG, "At Column: " + i + " At Row: " + j);
if(grid[i][j] == null || grid[i][j].equals("")){
Log.d(TAG, "Is Empty");
items++;
if(moveList == null || moveList.length < items){
resize();
}//end of second if statement
move.setRow(j);
move.setColumn(i);
moveList[items - 1] = move;
}//end of first if statement
}//end of second loop
}//end of first loop
for (int k = 0; k < moveList.length; k++){
Log.d(TAG, "Count: " + k + " Column: " + moveList[k].getColumn() + " Row: " + moveList[k].getRow());
}
return moveList;
}
private void resize(){
Move[] b = new Move[items];
for (int i = 0; i < items - 1; i++){
b[i] = moveList[i];
}
moveList = b;
}总结这一切：是什么导致了我的电话，选择最好的一步，花这么长时间？我遗漏了什么？有更简单的方法来实现这个算法吗？任何帮助或建议都将不胜感激，谢谢！
Stack Overflow用户
发布于 2013-03-25 23:53:01
带有alphaβ剪枝的minimax树应该形象化为一棵树，树的每一个节点都是一个可能的移动，许多人都会进入未来，而它的子节点是可以从树中获取的所有移动。
为了尽可能快，并保证你只需要空间线性的数目，你要向前看，你做一个深度第一搜索和‘扫描’从一边到另一边。就像你想象的那样，如果你想象整棵树正在被建造，你的程序实际上一次只构建一条从铅到根的单链，并丢弃它的任何部分。
我现在只想复制维基百科的伪代码，因为它非常非常简洁和清晰：
function alphabeta(node, depth, α, β, Player)
if depth = 0 or node is a terminal node
return score
if Player = MaxPlayer
for each child of node
α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break (* Beta cut-off *)
return α
else
for each child of node
β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break (* Alpha cut-off *)
return β备注：
-“节点的每个子节点”--而不是编辑当前板的状态，而是创建一个完全新的板，这是应用移动的结果。通过使用不可变的对象，您的代码就不会那么容易出错，并且通常更快地进行推理。
-To使用这个方法，对你可以从当前状态做的每一个可能的移动调用它，给它深度-1，-Infinity表示alpha，+Infinity表示beta，它应该从每个调用中的非移动玩家回合开始--返回最高值的调用是最好的。
这在概念上非常简单。如果代码正确，那么就永远不会一次实例化超过(深度)的板，也不会考虑无意义的分支等等。
https://stackoverflow.com/questions/15626660
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号