MinMax - генерация игрового дерева

Question

Я пытаюсь написать программу MinMax на Java для игры connect-four, но эта программа также должна быть применима и к другим играм. Но я столкнулся с проблемой, которую не могу пройти несколько дней. Значения для узлов установлены неправильно. Я делюсь своим фрагментом кода, который отвечает за генерацию дерева.

Может быть, вы заметите, где я допустил ошибку.

Если кто-нибудь может мне помочь с этим, я буду очень счастлив.

public Node generateTree(Board board, int depth) {
    Node rootNode = new Node(board);
    generateSubtree(rootNode, depth);
    minMax(rootNode, depth);
    return rootNode;
}

private void generateSubtree(Node subRootNode, int depth) {
    Board board = subRootNode.getBoard();

    if (depth == 0) {
        subRootNode.setValue(board.evaluateBoard());
        return;
    }

    for (Move move : board.generateMoves()) {
        Board tempBoard = board.makeMove(move);
        Node tempNode = new Node(tempBoard);
        subRootNode.addChild(tempNode);
        generateSubtree(tempNode, depth - 1);
    }
}

public void minMax(Node rootNode, int depth) {
    maxMove(rootNode, depth);
}

public int maxMove(Node node, int depth) {
    if (depth == 0) {
        return node.getValue();
    }
    int bestValue = Integer.MIN_VALUE;
    for (Node childNode : node.getChildren()) {
        int tempValue = minMove(childNode, depth - 1);
        childNode.setValue(tempValue);
        if (tempValue > bestValue) {
            bestValue = tempValue;
        }
    }
    return bestValue;
}

public int minMove(Node node, int depth) {
    if (depth == 0) {
        return node.getValue();
    }
    int bestValue = Integer.MAX_VALUE;
    for (Node childNode : node.getChildren()) {
        int tempValue = maxMove(childNode, depth - 1);
        childNode.setValue(tempValue);
        if (tempValue < bestValue) {
            bestValue = tempValue;
        }
    }
    return bestValue;
}

Доска класса является представлением совета государства.

КлассMove удерживает движение, которое нужно выполнить (целое число [0-8] для крестики-нолики, [0-6] для Connect Four).

КлассNode содержит Move и оценивает, насколько хорош данный ход. Также держит всех своих детей.

В коде я использую этот метод следующим образом:

Node newNode = minmax.generateTree(board, depth, board.getPlayer());
Move newMove = new TicTacToeMove(board.getPlayer(), newNode.getBestMove().getMove(), depth);
board = board.makeMove(newMove);

И когда очевидно, что данный ход является проигрышным (или выигрышным), я не получаю этот ход.

Answer 1

Хорошо, вы сделали пару ошибок. Около 3-4, в зависимости от того, как ты считаешь;) Мне потребовалось немного отладки, чтобы все это выяснить, но я наконец-то получил ответ для тебя:D

Ошибка № 1: Все твои родители всегда получают двойню (эта бедная мать)

Это только в случае с кодом, который вы загрузили, а не с кодом в вашем вопросе, так что, может быть, мы считаем это ошибкой? Поскольку ваши деревья еще не такие большие, и это не разрушит ваш алгоритм, в любом случае это был наименее важный. Тем не менее, это то, что нужно остерегаться. В своем загруженном коде вы делаете это в своем generateSubtree метод:

Node tempNode = new Node(tempBoard, move, subRootNode);
subRootNode.addChild(tempNode);

Поскольку этот конструктор уже добавляет дочерний элемент в subRootNode, вторая строка всегда добавляет его во второй раз.

Ошибка № 2: эта проклятая глубина

Если вы еще не достигли желаемой глубины, но игра уже решена, вы полностью игнорируете это. Таким образом, в приведенном вами примере это не сработает, если, например, вы посмотрите на ход 7 вместо 3 (что было бы "правильным" ходом), а затем оппонент сделал ход 3, вы не считаете это -10 баллов, потому что вы еще не достигли своей глубины. Он по-прежнему не получит детей, поэтому даже при вашем минимуме он никогда не поймет, что это испорченный путь.

Вот почему каждое движение "возможно" в этом сценарии, и вы просто возвращаете первое.

К счастью, в предыдущих ходах всегда был способ получить проигрышный ход с третьим ходом ваших оппонентов (он же ход № 5), поэтому они были названы правильно.

Хорошо, так как мы можем это исправить?

private void generateSubtree(Node subRootNode, int depth, int player) {
    Board board = subRootNode.getBoard();
    List<Move> moveList = board.generateMoves();

    if (depth == 0 || moveList.isEmpty()) {
        subRootNode.setValue(board.evaluateBoard(player));
        return;
    }

    for (Move move : moveList) {
        Board tempBoard = board.makeMove(move);
        Node tempNode = new Node(tempBoard, move, subRootNode);
        generateSubtree(tempNode, depth - 1, player);
    }
}

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

Ошибка № 3: Эта проклятая глубина снова

Разве мы не прошли через это?

К сожалению, сам алгоритм Min Max имеет ту же проблему. Он будет даже смотреть на ваши значения, только если вы достигли желаемой глубины. Вы должны изменить это.

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

Вы можете проверить, установлено ли ваше значение, но вот проблема: оно может быть установлено на 0 и вы должны принять это во внимание также (так что вы не можете просто сделать if (node.getValue() != 0)).

Я просто установил начальное значение каждого узла -1 вместо этого и сделал проверку против -1, Это не... ты знаешь... красиво. Но это работает.

public class Node {
    private Board board;
    private Move move;
    private Node parent;
    private List<Node> children = new ArrayList<Node>();;
    private boolean isRootNode = false;

    private int value = -1;
   ...

И это в maxMove:

public int maxMove(Node node, int depth) {
    if (depth == 0 || node.getValue() != -1) {
        return node.getValue();
    }
    int bestValue = Integer.MIN_VALUE;
    for (Node childNode : node.getChildren()) {
        int tempValue = minMove(childNode, depth - 1);
        childNode.setValue(tempValue);
        if (tempValue > bestValue) {
            bestValue = tempValue;
        }
    }               
    return bestValue;
}

Это работает так же для minMove конечно.

Ошибка № 4: игрок с вами

Как только я изменил все это, мне потребовалось время с отладчиком, чтобы понять, почему это все еще не работает.

Эта последняя ошибка была не в коде, который вы указали в вопросе. Позор тебе!;)

Оказывается, это был замечательный кусок кода в вашем TicTacToeBoard учебный класс:

@Override
public int getPlayer() {
    // TODO Auto-generated method stub
    return 0;
}

И так как вы позвонили

        MinMax minmax = new MinMax();
        Node newNode = minmax.generateTree(board, (Integer) spinner.getValue(), board.getPlayer());

в вашем makeMove метод TicTacToeMainWindow, вы всегда начинаете с неправильного игрока.

Как вы, вероятно, можете догадаться, вам просто нужно изменить это на:

public int getPlayer() {
    return this.player;
}

И это должно сработать.

Также:

Просто пару вещей, которые я хотел бы отметить в этом пункте:

• Очистите свой импорт! Ваш TicTacToe фактически все еще импортирует ваши классы ConnectFour! И без причины.

• Ваша доска вращается и отражается в массиве ваших досок. ЗАЧЕМ? Вы знаете, как это раздражает отлаживать? Я имею в виду, я думаю, что вы, вероятно, делаете:D Кроме того, если у вас есть проблемы с вашим кодом, и вам нужно отладить, это очень полезно переписать ваши платы toString() метод, потому что это даст вам очень хороший и простой способ взглянуть на вашу доску в отладчике. Вы можете даже использовать это, чтобы повернуть это снова, таким образом, Вы видите, не должны смотреть на это, лежа на стороне;)

• Пока мы находимся на предмете доски... это только я, но... Я всегда сначала пытался нажать на окрашенную поверхность, а затем должен был вспомнить: о да, были кнопки: я имею в виду... почему бы и нет просто поместите изображения на кнопки или реализуйте MouseListener так что вы можете просто нажать на окрашенную поверхность?

• При предоставлении кода и / или примеров изображений, пожалуйста, извлеките результаты тестов. Я говорю о Player 1 won!конечно же;)

• Пожалуйста, узнайте, что такое полный, проверяемый и минимальный пример для следующего вопроса о Stackru. Тот, что в вашем вопросе, не был полным или проверяемым, а тот, который вы предоставили на github, был... ну... не полным (изображения отсутствовали), но достаточно полным. Это также поддается проверке, но это не было минимальным. Вы получите ответы много раньше, если будете следовать инструкциям.