Tic Tac Toe negamax implementation.

Question

I'm trying to implement the negamax search function for a tic-tac-toe application, but it does not return the optimal values, instead it appears to guess semi-randomly. Here's the relevant part of my code:

public int negamax(Result result, Token token) {
    if (result == Result.WIN) {
        return 1;
    } else if (result == Result.DRAW) {
        return 0;
    }

    int best = -1;

    for (Coordinate move : Board.getAvailableMoves()) {
        Token other = token.getOther();
        Result r = Board.makeMove(move, other);
        int eval = -negamax(r, other);
        Board.unmakeMove(move);

        if (eval > best) {
            best = eval;
        }
    }

    return best;
}

public Coordinate getNegamaxMove(Token token) {
    int score = -1;
    Coordinate bestMove = null;

    for (Coordinate move : Board.getAvailableMoves()) {
        Result result = Board.makeMove(move, token);
        int newScore = negamax(result, token);
        Board.unmakeMove(move);

        if (newScore >= score) {
            score = newScore;
            bestMove = move;
        }
    }

    return bestMove;
}

It's important to note that I don't pass the board as a parameter, but rather the outcome of a move, which can be either WIN, DRAW, VALID or OCCUPIED (the last 2 are not relevant to the current discussion) which are all self-explanatory. The Coordinate class just holds the row and column values of the move.

Thank you very much :)

score 2 · Answer 1 · answered May 17 '15 at 12:29

I have managed to get it working, there were 2 problems with the negamax method. First of all, the token should have been changed before looping through all available moves, not inside the loop. Secondly, since I check the best move in getNegamaxMove method, in negamax method, I have to keep track of the worst move instead of the best. Here's the working implementation with the old parts commented out for comparison:

public int negamax(Result result, Token token) {
    if (result == Result.WIN) {
        return 1;
    } else if (result == Result.DRAW) {
        return 0;
    }

    int worst = 1;
    // int best = -1

    Token other = token.getOther();
    for (Coordinate move : Board.getAvailableMoves()) {
        // Token other = token.getOther();
        Result r = Board.makeMove(move, other);
        int eval = -negamax(r, other);
        Board.unmakeMove(move);

        // if (eval > best) {
        //     best = eval;
        // }

        if (eval < worst) {
            worst = eval;
        }
    }

    // return best
    return worst;
}

Tic Tac Toe negamax implementation.

1 Answers1