Минимаксный алгоритм Connect4 делает глупые ходы - PullRequest
Новая
       43

Минимаксный алгоритм Connect4 делает глупые ходы

0 голосов
/ 23 сентября 2018

Я пытаюсь реализовать алгоритм, который бы выбирал оптимальный следующий ход для игры Connect 4. Поскольку я просто хочу убедиться, что базовый минимакс работает правильно, я на самом деле его тестируюкак Connect 3 на поле 4x4.Таким образом, мне не нужно сокращать альфа-бета, и это становится более очевидным, когда алгоритм делает глупый ход.

Проблема в том, что алгоритм всегда запускает игру с крайним левым ходом, а также во время игры он просто очень глупый.Он не видит лучших ходов.

Я тщательно проверил методы makeMove(), undoMove(), getAvailableColumns(), isWinningMove() и isLastSpot(), поэтому я абсолютно уверен что проблема не в этом.

Вот мой алгоритм.

NextMove.java 

private static class NextMove {
    final int evaluation;
    final int moveIndex;

    public NextMove(int eval, int moveIndex) {
        this.evaluation = eval;
        this.moveIndex = moveIndex;
    }

    int getEvaluation() {
        return evaluation;
    }

    public int getMoveIndex() {
        return moveIndex;
    }
}

Алгоритм 

private static NextMove max(C4Field field, int movePlayed) {
    // moveIndex previously validated

    // 1) check if moveIndex is a final move to make on a given field
    field.undoMove(movePlayed);

    // check
    if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(BLUE_WIN, movePlayed);
    }
    if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(RED_WIN, movePlayed);
    }
    if (field.isLastSpot()) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(DRAW, movePlayed);
    }

    field.playMove(movePlayed, C4Symbol.RED);

    // 2) moveIndex is not a final move
    // --> try all possible next moves
    final List<Integer> possibleMoves = field.getAvailableColumns();
    int bestEval = Integer.MIN_VALUE;
    int bestMove = 0;
    for (int moveIndex : possibleMoves) {           
        field.playMove(moveIndex, C4Symbol.BLUE);

        final int currentEval = min(field, moveIndex).getEvaluation();
        if (currentEval > bestEval) {
            bestEval = currentEval;
            bestMove = moveIndex;
        }

        field.undoMove(moveIndex);
    }

    return new NextMove(bestEval, bestMove);
}

private static NextMove min(C4Field field, int movePlayed) {
    // moveIndex previously validated

    // 1) check if moveIndex is a final move to make on a given field
    field.undoMove(movePlayed);

    // check
    if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(BLUE_WIN, movePlayed);
    }
    if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(RED_WIN, movePlayed);
    }
    if (field.isLastSpot()) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(DRAW, movePlayed);
    }

    field.playMove(movePlayed, C4Symbol.BLUE);

    // 2) moveIndex is not a final move
    // --> try all other moves
    final List<Integer> possibleMoves = field.getAvailableColumns();
    int bestEval = Integer.MAX_VALUE;
    int bestMove = 0;
    for (int moveIndex : possibleMoves) {
        field.playMove(moveIndex, C4Symbol.RED);

        final int currentEval = max(field, moveIndex).getEvaluation();
        if (currentEval < bestEval) {
            bestEval = currentEval;
            bestMove = moveIndex;
        }

        field.undoMove(moveIndex);
    }

    return new NextMove(bestEval, bestMove);
}

Идея состоит в том, что алгоритм принимает аргументы currentField и lastPlayedMove.Затем он проверяет, закончил ли последний ход игру.Если это так, я просто возвращаю этот ход, в противном случае я углубляюсь в последующие ходы.

Синий игрок - МАКС, красный игрок - МИН.

На каждом шаге я сначала отменяюпоследний ход, потому что легче проверить, завершит ли «следующий» ход игру, чем проверить, закончено ли текущее поле (для этого потребуется проанализировать все возможные варианты выигрыша на поле).После проверки я просто переделываю ход.

По какой-то причине это не работает.Я застрял с этим в течение нескольких дней!Понятия не имею, что не так ... Любая помощь очень ценится!

...