我目前正在为Chess编写带有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)
接收一个Board并计算参数Board的Board状态的值。
本质上,evaluateBoard()为我提供了最佳移动值的最终int结果值Alphabeta()。但是我没有办法让evaluateBoard()返回导致最终得分的举动。即使我要返回一些保存分数值和碎片信息的对象,我也不确定如何在树的顶部获得碎片信息,从而获得最终的最佳分数。
有谁知道我如何获得/返回给出最佳得分值的最佳动作的信息?我是否错过了mini max算法中的关键要素和/或是否必须以不同的方式实现Alphabeta()?
编辑:
例如,假设minimax从以下移动中返回最佳分数:e4,e5,nf3,nc6。我所拥有的将返回董事会情况的数值。如何返回“ e4”?E4是产生最高价值的举动。
谢谢。
即使没有显式使用树,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;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句