如何实现高效的α-β剪枝博弈搜索树？ [英] How to implement efficient Alpha-Beta pruning Game Search Tree?
问题描述
我想学习人工智能，以及如何在程序中实现它。开始最简单的地方大概就是用简单的游戏（在这种情况下，井字棋）和游戏搜索树（递归调用，而不是实际的数据结构）。 我发现这的一本关于该主题的讲座非常有用的视频。
I'm trying to learn about artificial intelligence and how to implement it in a program. The easiest place to start is probably with simple games (in this case Tic-Tac-Toe) and Game Search Trees (recursive calls; not an actual data structure). I found this very useful video on a lecture about the topic.
我遇到的问题是，该算法的第一个呼叫正在一个非常长的时间（约15秒）来执行。我已经放在调试日志输出整个code和看起来它是调用算法的部分倍过量。
The problem I'm having is that the first call to the algorithm is taking an extremely long amount of time (about 15 seconds) to execute. I've placed debugging log outputs throughout the code and it seems like it is calling parts of the algorithm an excessive amount of times.
下面就是该方法的选择计算机的最佳举措：
Here's the method for choosing the best move for the computer:
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;
}
凡 makeMove 方法使移动中如果地方是空的，并返回一个值（-1 - 人类的胜利，0 - 平局，1 - 计算机获胜，-2或2 - 其他）。虽然我相信，错误可能是在 getAllLegalMoves 方法：
Where the makeMove method makes the move if the spot is empty and returns a value (-1 - human win, 0 - draw, 1 - computer win, -2 or 2 - otherwise). Though I believe the error may be in the getAllLegalMoves method:
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;
}
要总括起来：是什么导致我的电话，要选择最好的移动，以这么长的时间？我在想什么？有没有实现这个算法更简单的方法？任何帮助或建议，将大大AP preciated，谢谢！
To sum it all up: What's causing my call, to choose the best move, to take so long? What am I missing? Is there an easier way to implement this algorithm? Any help or suggestions will be greatly appreciated, thanks!
推荐答案
与α+β修剪极小树应该就像一棵树，树的是一个可能的移动的每个节点，不少圈进去以后，和它的孩子们是所有可以从它的举动。
A minimax tree with alpha beta pruning should be visualized as a tree, each node of the tree being a possible move that many turns into the future, and its children being all the moves that can be taken from it.
要尽可能快，尽可能保证你只需要在你正在寻找未来的移动数字空间的线性，你做一个深度优先搜索和'扫'从一边到另一边。如，如果你想像整棵树正在建设中，你的程序实际上只是构建一个单链的导向root一次，并丢弃它它与完成的任何部分。
To be as fast as possible and guarantee you'll only need space linear on number of moves you're looking ahead, you do a depth first search and 'sweep' from one side to another. As in, if you imagine the whole tree being constructed, your program would actually only construct a single strand from lead to root one at a time, and discard any parts of it it is done with.
我只是去复制维基百科伪code在这一点上，因为它是真的，真的很简洁明了：
I'm just going to copy the wikipedia pseudo code at this point because it's really, really succinct and clear:
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 β
注：
- 号节点的每个孩子 - 而不是编辑目前主板的状态，创建一个全新的董事会，将移动的结果的使用不可变对象，你的code会遭到不易发生错误，并更快地一般推理。
-'for each child of node' - Rather than editing the state of the current board, create an entirely new board that is the result of applying the move. By using immutable objects, your code will be less prone to bugs and quicker to reason about in general.
- 要使用此方法，调用它的每一个可能的举动，你可以从当前的状态，给它的深度-1，负无穷大的alpha和+无限的测试，它应该由是不动的玩家开始把在每个调用 - 一个返回的最高值是最好的拿
-To use this method, call it for every possible move you can make from the current state, giving it depth -1, -Infinity for alpha and +Infinity for beta, and it should start by being the non-moving player's turn in each of these calls - the one that returns the highest value is the best one to take.
这是非常非常简单的概念。如果$ C C $它正确的，那么你永远不会实例化多个（深度）板一次，你永远不考虑无意义的分支机构等。
It's very very conceptually simple. If you code it right then you never instantiate more than (depth) boards at once, you never consider pointless branches and so on.
这篇关于如何实现高效的α-β剪枝博弈搜索树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
