Negamax Chess Algorithm: How To Use Final Return?
I made a negamax algorithm for a chess game and I want to know how to use the final result of the board value. I understand that the final return of the negamax algorithm is what the board value will be after the player has done his best, but this is not really useful information. I need to know what this move is, not what it costs.
Here's the code:
public int negamax(Match match, int depth, int alpha, int beta, int color) {
if(depth == 0) {
return color*stateScore(match);
}
ArrayList<Match> matches = getChildren(match, color);
if(matches.size() == 0) {
return color*stateScore(match);
}
int bestValue = Integer.MIN_VALUE;
for(int i = 0; i != matches.size(); i++) {
int value = -negamax(matches.get(i), depth-1, -beta, -alpha, -color);
if(value > bestValue) {
bestValue = value;
}
if(value > alpha) {
alpha = value;
}
if(alpha >= beta) {
break;
}
}
return bestValue;
}
public void getBestMove(Match match, int color) {
int bestValue = negamax(match, 4, Integer.MIN_VALUE, Integer.MAX_VALUE, color);
// What to do with bestValue???
}
I thought about re-evaluating the children of the current match state after determining the bestValue. Then I iterate over them and find out which of these children has a stateScore equal to bestValue. But that won't work because a lot of them will have the same stateScore, that's what they can lead to what counts ...
I see you are doing qsearch and alpha-beta. Your algorithm is well known, but you are missing a key part.
Let me sketch out a basic chess search algorithm, it even applies to Stockfish (the world's strongest engine).
search(Position p) {
if (leaf node)
qsearch(p)
if (need to do move reduction)
do_move_reduction_and_cut_off(p)
moves = generate_moves(p)
for_each(move in moves) {
p.move(move)
v = -search(p, -beta, -alpha)
p.undo(move)
store the score and move into a hash table
if (v > beta)
cutoff break;
}
This is just a very short sketch, but all chess algorithms follow it. Compare your version to it, will you notice that you have not followed p.move (move) and p.undo (move)?
Basically, the traditional approach generates a list of moves for a given position. Navigate the moves, replay them and undo and review. If you do this, you know exactly which step is producing the result.
Also notice the line for storing the move and score into a hash table. If you do this, you can easily restore the entire main variant from the root node.
I don't know what exactly is in your Java Match class, but your attempt was close anyway, but not exactly the classic way to do a search. Remember that you need to specify a position object in the search algorithm, but instead you gave it a Match object, which is not correct.
source to share