«Поиск по дереву Монте-Карло для игры в крестики-нолики на Java»

«1. Обзор

В этой статье мы рассмотрим алгоритм поиска по дереву Монте-Карло (MCTS) и его приложения.

Мы подробно рассмотрим его этапы, реализовав игру Крестики-нолики на Java. Мы разработаем общее решение, которое можно будет использовать во многих других практических приложениях с минимальными изменениями.

2. Введение

Проще говоря, поиск по дереву Монте-Карло является алгоритмом вероятностного поиска. Это уникальный алгоритм принятия решений из-за его эффективности в открытых средах с огромным количеством возможностей.

Если вы уже знакомы с алгоритмами теории игр, такими как Minimax, вам потребуется функция для оценки текущего состояния, и она должна вычислить множество уровней в дереве игры, чтобы найти оптимальный ход.

К сожалению, это невозможно сделать в такой игре, как Го, в которой есть высокий коэффициент ветвления (что приводит к миллионам возможностей по мере увеличения высоты дерева), и трудно написать хорошую функцию вычисления для вычисления насколько хорошее текущее состояние.

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

И небольшое замечание: он произвел революцию в мире компьютерного го. С марта 2016 года он стал широко распространенной темой исследований, поскольку Google AlphaGo (построенный с помощью MCTS и нейронной сети) победил Ли Седоля (чемпион мира по го).

3. Алгоритм поиска по дереву Монте-Карло

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

В конце мы выберем узел с наиболее перспективной статистикой.

Алгоритм состоит из четырех этапов; давайте подробно рассмотрим их все.

3.1. Выбор

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

Идея состоит в том, чтобы продолжать выбирать оптимальные дочерние узлы, пока мы не достигнем конечного узла дерева. Хороший способ выбрать такой дочерний узел — использовать формулу UCT (верхняя доверительная граница, применяемая к деревьям): в которой

wi = количество побед после i-го хода ni = количество симуляций после i-го хода c = параметр исследования (теоретически равный √2) t = общее количество симуляций для родительского узла

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

3.2. Расширение

Когда он больше не может применять UCT для поиска узла-преемника, он расширяет игровое дерево, добавляя все возможные состояния из конечного узла.

3.3. Моделирование

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

3.4. Обратное распространение

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

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

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

4. Пробный прогон

Здесь узлы содержат статистику в виде общего количества посещений/счетов побед.

5. Реализация

Теперь давайте реализуем игру в крестики-нолики, используя алгоритм поиска по дереву Монте-Карло.

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

Хотя, чтобы сделать объяснение четким, нам, возможно, придется пропустить некоторые незначительные детали (не особенно связанные с MCTS), но вы всегда можете найти полную реализацию здесь.

Прежде всего, нам нужна базовая реализация классов Tree и Node, чтобы иметь функциональность поиска по дереву:

public class Node {
    State state;
    Node parent;
    List<Node> childArray;
    // setters and getters
}
public class Tree {
    Node root;
}

Так как каждый узел будет иметь определенное состояние проблемы, давайте также реализуем класс State:

public class State {
    Board board;
    int playerNo;
    int visitCount;
    double winScore;

    // copy constructor, getters, and setters

    public List<State> getAllPossibleStates() {
        // constructs a list of all possible states from current state
    }
    public void randomPlay() {
        /* get a list of all possible positions on the board and 
           play a random move */
    }
}

Теперь давайте реализуем класс MonteCarloTreeSearch, который будет отвечать за поиск следующего лучшего хода из данной игровой позиции:

public class MonteCarloTreeSearch {
    static final int WIN_SCORE = 10;
    int level;
    int opponent;

    public Board findNextMove(Board board, int playerNo) {
        // define an end time which will act as a terminating condition

        opponent = 3 - playerNo;
        Tree tree = new Tree();
        Node rootNode = tree.getRoot();
        rootNode.getState().setBoard(board);
        rootNode.getState().setPlayerNo(opponent);

        while (System.currentTimeMillis() < end) {
            Node promisingNode = selectPromisingNode(rootNode);
            if (promisingNode.getState().getBoard().checkStatus() 
              == Board.IN_PROGRESS) {
                expandNode(promisingNode);
            }
            Node nodeToExplore = promisingNode;
            if (promisingNode.getChildArray().size() > 0) {
                nodeToExplore = promisingNode.getRandomChildNode();
            }
            int playoutResult = simulateRandomPlayout(nodeToExplore);
            backPropogation(nodeToExplore, playoutResult);
        }

        Node winnerNode = rootNode.getChildWithMaxScore();
        tree.setRoot(winnerNode);
        return winnerNode.getState().getBoard();
    }
}

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

Теперь давайте реализуем методы для всех фаз.

Мы начнем с фазы выбора, которая также требует реализации UCT:

private Node selectPromisingNode(Node rootNode) {
    Node node = rootNode;
    while (node.getChildArray().size() != 0) {
        node = UCT.findBestNodeWithUCT(node);
    }
    return node;
}

public class UCT {
    public static double uctValue(
      int totalVisit, double nodeWinScore, int nodeVisit) {
        if (nodeVisit == 0) {
            return Integer.MAX_VALUE;
        }
        return ((double) nodeWinScore / (double) nodeVisit) 
          + 1.41 * Math.sqrt(Math.log(totalVisit) / (double) nodeVisit);
    }

    public static Node findBestNodeWithUCT(Node node) {
        int parentVisit = node.getState().getVisitCount();
        return Collections.max(
          node.getChildArray(),
          Comparator.comparing(c -> uctValue(parentVisit, 
            c.getState().getWinScore(), c.getState().getVisitCount())));
    }
}

private void expandNode(Node node) {
    List<State> possibleStates = node.getState().getAllPossibleStates();
    possibleStates.forEach(state -> {
        Node newNode = new Node(state);
        newNode.setParent(node);
        newNode.getState().setPlayerNo(node.getState().getOpponent());
        node.getChildArray().add(newNode);
    });
}

На этой фазе рекомендуется конечный узел, который следует расширить на этапе расширения:

private void backPropogation(Node nodeToExplore, int playerNo) {
    Node tempNode = nodeToExplore;
    while (tempNode != null) {
        tempNode.getState().incrementVisit();
        if (tempNode.getState().getPlayerNo() == playerNo) {
            tempNode.getState().addScore(WIN_SCORE);
        }
        tempNode = tempNode.getParent();
    }
}
private int simulateRandomPlayout(Node node) {
    Node tempNode = new Node(node);
    State tempState = tempNode.getState();
    int boardStatus = tempState.getBoard().checkStatus();
    if (boardStatus == opponent) {
        tempNode.getParent().getState().setWinScore(Integer.MIN_VALUE);
        return boardStatus;
    }
    while (boardStatus == Board.IN_PROGRESS) {
        tempState.togglePlayer();
        tempState.randomPlay();
        boardStatus = tempState.getBoard().checkStatus();
    }
    return boardStatus;
}

Далее, мы пишем код для выбора случайного узла и имитации случайного воспроизведения из него. Кроме того, у нас будет функция обновления для распространения оценки и количества посещений, начиная с листа к корню:

public class Board {
    int[][] boardValues;
    public static final int DEFAULT_BOARD_SIZE = 3;
    public static final int IN_PROGRESS = -1;
    public static final int DRAW = 0;
    public static final int P1 = 1;
    public static final int P2 = 2;
    
    // getters and setters
    public void performMove(int player, Position p) {
        this.totalMoves++;
        boardValues[p.getX()][p.getY()] = player;
    }

    public int checkStatus() {
        /* Evaluate whether the game is won and return winner.
           If it is draw return 0 else return -1 */         
    }

    public List<Position> getEmptyPositions() {
        int size = this.boardValues.length;
        List<Position> emptyPositions = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (boardValues[i][j] == 0)
                    emptyPositions.add(new Position(i, j));
            }
        }
        return emptyPositions;
    }
}

Теперь мы закончили с реализацией MCTS. Все, что нам нужно, — это конкретная реализация класса Board в крестиках-ноликах. Обратите внимание, что для того, чтобы играть в другие игры с нашей реализацией; Нам просто нужно изменить класс Board.

@Test
public void givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw() {
    Board board = new Board();
    int player = Board.P1;
    int totalMoves = Board.DEFAULT_BOARD_SIZE * Board.DEFAULT_BOARD_SIZE;
    for (int i = 0; i < totalMoves; i++) {
        board = mcts.findNextMove(board, player);
        if (board.checkStatus() != -1) {
            break;
        }
        player = 3 - player;
    }
    int winStatus = board.checkStatus();
 
    assertEquals(winStatus, Board.DRAW);
}

Мы только что внедрили ИИ, который невозможно победить в крестиках-ноликах. Давайте напишем единичный случай, который демонстрирует, что ИИ против ИИ всегда приводит к ничьей:

6. Преимущества

Это не обязательно требует каких-либо тактических знаний об игре. Общую реализацию MCTS можно повторно использовать для любое количество игр с небольшой модификацией. Фокусируется на узлах с более высокими шансами на победу в игре. Подходит для задач с высоким коэффициентом ветвления, поскольку не тратит вычисления на все возможные ветви. Алгоритм очень прост в реализации. Выполнение может быть остановлено в любой момент времени и он по-прежнему будет предлагать следующее лучшее состояние, вычисленное на данный момент

7. Недостаток

Если MCTS используется в своей базовой форме без каких-либо улучшений, он может не предложить разумных действий. Это может произойти, если узлы не посещаются должным образом, что приводит к неточным оценкам.

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

В методах, специфичных для предметной области, этап моделирования создает более реалистичные результаты, чем стохастическое моделирование. Хотя это требует знания конкретных игровых техник и правил.

8. Резюме

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