Negamax chess algorithm: How to use final return?
I've made a negamax algorithm for a chess-like game and I want to know how to use the final board value result. I understand the final return of the negamax algorithm represents what the board value will be after the player takes his best possible move, but that isn't exactly useful information. I need to know what that move is, not what it's worth.
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 of re-evaluating the children of the current match state after bestValue is determined. Then I iterate through them and find which of those children has a stateScore equal to bestValue. But that wouldn't work because a lot of them will have the same stateScore anyway, it's what they can lead to which counts...
I can see you're doing a qsearch and alpha-beta. Your algorithm is well-known but you're missing a key part.
Let me sketch out the basic algorithm for chess search, it applies even to Stockfish (the strongest engine in the world).
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 brief sketch, but all chess algorithms follow it. Compare your version with it, do you notice that you haven't done p.move(move) and p.undo(move)?
Basically, the traditional approach generates a list of moves for a given position. Loop through the moves, play it and undo it and search it. If you do it, you know exactly which move produces which score.
Also notice the line for storing the move and score into a hash table. If you do this, you can easily reconstruct the entire principal variation from a root node.
I don't know what exactly is inside your Java class Match, but in any case your attempt was close but no exactly the classical way to do a search. Remember you'll need to give a position object in a search algorithm but instead you gave it a Match object, which is wrong.
链接地址: http://www.djcxy.com/p/84678.html