How to get the actual move and not move the value from the mini-max algorithm
I am currently writing a minimax algorithm with alpha-beta cropping for Chess.
Of all the examples I've seen, the minimax algorithm returns an int value that represents the best result, or the board state that will result in the best move.
My question is, how can we return the best move associated with the return score?
For example my alphabeta () in the pseudo below ...
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 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 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;
}
}
In my minimax / alphabeta implementation, I have a Board object representing a checkerboard and pieces can move around it to represent different textures / states of the game.
My function evaluateBoard(Board b)
takes a board and calculates a value for the state of the parameter board.
Essentially valueBoard () gives me the final result value of int alphabeta () for the best motion value. However, I don't see a way to evaluate Board () to return the move that led to the final result. Even if I returned some object containing the score value and part information, I am not sure how I could get the part information at the top of the tree, which gave me the last best result.
Does anyone know how I can get / return information about the best move that gives the best score? Am I missing a key element in the minimax algorithm and / or do I need to implement alphabeta () differently?
EDIT:
For example, let at least minimax return the best result from the following steps: e4, e5, nf3, nc6. What I have will return the numeric value of the board status. How can I get "e4" back? E4 is the step that leads to the highest value.
Thank.
source to share
The minimax algorithm works by examining a tree of possible moves, even if you are not explicitly using a tree. Thus, all that is needed is that your function will return the best move in addition to its value.
You can do something like this:
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;
}
source to share