我试图为我的游戏构建一个游戏树,以便找到我的下一步行动。首先,我使用递归算法构建树,然后,使用 alpha - beta 剪枝算法找到最佳移动 Im。我想使用 alpha - beta 修剪来构建游戏树,以最小化游戏树的大小,但我在编写算法时遇到问题。你能帮我在扩展算法中添加 alpha - beta 修剪吗?
这是扩展算法:
public void expand(int depth)
{
expand++;
if(depth > 0)
{
this.children = new ArrayList<GameTreeNode>();
List<Move> possibleMoves = this.b.possibleMoves(this.b.turn);
ReversiBoard tmp = null;
for(Move m : possibleMoves)
{
TurnState nextState = (this.state == TurnState.PLUS ? TurnState.MINUS : TurnState.PLUS);
tmp = new ReversiBoard(this.b);
tmp.makeMove(m);
int nextTurn = (turn == PLAYER1 ? PLAYER2 : PLAYER1);
if(tmp.possibleMoves(nextTurn).isEmpty())
nextTurn = turn;
this.children.add(new GameTreeNode(tmp, nextState, m, nextTurn));
for(GameTreeNode child : children)
child.expand(depth - 1);
}
}
}
这是 alpha - beta 修剪代码:
int alphaBetaMax( int alpha, int beta, int depthleft ) {
alphaBetaNum++;
if ( depthleft == 0 ) return this.b.evaluate();
for (GameTreeNode tree : this.children) {
bestValue = alphaBetaMin( alpha, beta, depthleft - 1 );
if( bestValue >= beta )
{
bestMove = tree.move;
return beta; // fail hard beta-cutoff
}
if( bestValue > alpha )
alpha = bestValue; // alpha acts like max in MiniMax
}
return alpha;
}
int alphaBetaMin( int alpha, int beta, int depthleft ) {
alphaBetaNum++;
if ( depthleft == 0 ) return -this.b.evaluate();
for ( GameTreeNode tree : this.children) {
bestValue = alphaBetaMax( alpha, beta, depthleft - 1 );
if( bestValue <= alpha )
{
bestMove = tree.move;
return alpha; // fail hard alpha-cutoff
}
if( bestValue < beta )
beta = bestValue; // beta acts like min in MiniMax
}
return beta;
}
public void summonAlphaBeta(int depth)
{
this.bestValue = alphaBetaMax(Integer.MIN_VALUE, Integer.MAX_VALUE, depth);
}
谢谢你!