我目前正在为象棋编写一个带有alpha beta剪枝的minimax算法。
从我看到的所有例子中,minimax算法将返回一个int值,它表示最佳得分或最佳移动所产生的董事会状态。
我的问题是,我们如何返回与分数返回值相关的最佳移动?
例如,我的alphabeta()在下面的伪..。
public int alphabeta(int depth, Board b, int alpha, int beta, boolean maxPlayer) {
if(depth == 0)
return evaluateBoard(b);
if(maxPlayer) {
for(each of max player's moves) {
// make move on a tempBoard
int eval = alphabeta(depth - 1, tempBoard, alpha, beta, false);
alpha = Math.max(alpha, eval);
if(beta <= alpha)
break;
}
return alpha;
}
else {
for(each of min's moves) {
// make move on a tempBoard
int eval = alphabeta(depth - 1, tempBoard, alpha, beta, true);
beta = Math.min(beta, eval);
if(beta <= alpha)
break;
}
return beta;
}
}在我实现的minimax / alphabeta中,我有一个Board对象,它代表棋盘,棋子可以在上面移动以表示不同的棋盘纹理/游戏状态。
我的函数evaluateBoard(Board b)接受一个板,并计算参数板的板状态的值。
本质上,evaluateBoard()给出了alphabeta()作为最佳移动值的最终int结果值。但是,我看不到evaluateBoard()返回最终得分的移动的方法。即使我要返回一些持有分数值和片段信息的对象,我也不知道如何才能在树的顶端得到给我最后最佳分数的信息。
有人知道我如何访问/返回给出最佳得分值的最佳移动信息吗?我是否遗漏了mini算法中的一个关键元素和/或必须以不同的方式实现alphabeta()?
编辑:
例如,假设minimax从以下动作中返回最佳得分: e4、e5、nf3、nc6。我所得到的将返回董事会情况的数值。如何返回"e4“?E4是导致最高值的移动。
谢谢。
发布于 2014-07-19 03:55:56
minimax算法的工作原理是探索可能的移动树,即使您没有显式地使用树。因此,所有需要的是,您的函数返回最好的移动,除了它的价值。
你可以这样做:
ScoredMove alphabeta(Board board, String player, Move move) {
board.applyMove(move);
if (board.gameOver())
{
score = board.scoreForPlayer(player);
return ScoredMove(score, move);
}
if (player == "player1") {
next_player = "player2";
} else {
next_player = "player1";
}
ScoredMove best_move = null;
for (next_move in board.movesForPlayer(next_player)) {
ScoredMove scored = alphabeta(board, next_player, next_move)
if (best_move == null || best_move.score < scored.score) {
best_move = scored;
}
}
board.removeMove(move);
return best_move;
}https://stackoverflow.com/questions/24836499
复制相似问题