Negamax chess algorithm: How to use final return?

Question

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...

possible duplicate of [How to get actual move rather than move value from mini max algorithm](http://stackoverflow.com/questions/24836499/how-to-get-actual-move-rather-than-move-value-from-mini-max-algorithm) — David Eisenstat, Sep 02 '14 at 04:39

ABCD · Accepted Answer · 2014-09-02T15:09:57.260

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.

oh, right... See I thought if I used a getChildren() method to get all the possible moves, and then apply each of those moves in turn to a copy of the game state, and then return all those possible resulting game states, then I wouldn't need to make and undo moves in the middle of my loop. Do I just have a major misunderstanding in thinking that I can just loop through all the match states and score them? Would it work if there was like a getParent() method call after the recursive negamax call? — , Sep 02 '14 at 17:27
By the way each Match contains a list of the pieces on the board, as well as a 2d array describing the board itself, which can change over the course of the match - so it is essentially just a Position object with a few bells and whistles. — , Sep 02 '14 at 17:37

Negamax chess algorithm: How to use final return?

1 Answers1