Реализация Tic Tac Toe negamax.

Я пытаюсь реализовать функцию поиска negamax для приложения крестики-нолики, но она не возвращает оптимальные значения, вместо этого она угадывает полуслучайно. Вот соответствующая часть моего кода:

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;
}

Важно отметить, что я не передаю доску в качестве параметра, а скорее результат хода, который может быть либо ВЫИГРЫШ, НИЧЬЯ, ДЕЙСТВИТЕЛЬНО или ЗАНЯТО (последние 2 не имеют отношения к текущему обсуждению), которые все самоочевидно. Класс Coordinate просто содержит значения строки и столбца перемещения.

Спасибо большое :)


java search minimax negamax
person stensootla    schedule 12.05.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Мне удалось заставить его работать, с методом negamax было 2 проблемы. Прежде всего, токен должен был быть изменен перед циклом всех доступных ходов, а не внутри цикла. Во-вторых, поскольку в методе getNegamaxMove я проверяю лучший ход, то в методе negamax мне приходится отслеживать худший ход, а не лучший. Вот рабочая реализация со старыми частями, закомментированными для сравнения:

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;
}
person stensootla    schedule 17.05.2015