Игра в 2048 с минимаксным алгоритмом
Как представить состояние игры 2048 года
И как это сделать объектно-ориентированным способом
В последней статье о решении этой игры я показал на концептуальном уровне, как алгоритм минимакса может быть применен к решению игры 2048. Но чтобы воплотить эти идеи в жизнь, нам нужен способ представления состояния игры и выполнения операций над ним. Я решил сделать это объектно-ориентированным способом, используя класс, который я назвал Grid. Этот класс хранит состояние игры и предлагает нам методы, необходимые для дальнейшей реализации минимаксного алгоритма (в следующей статье).
Если вы пропустили мою предыдущую статью, вот она:
Теперь приступим к реализации класса Grid в Python.
Внутри класса Grid мы будем хранить состояние игры в виде матрицы с номерами тайлов в ней, а там, где у нас есть пустые квадраты, мы будем держать 0. В Python мы будем использовать для этого список списков и сохраним его в атрибут matrix класса Grid.
Пример этого представления показан ниже:
В нашей реализации нам нужно будет немного передать эту матрицу; мы получим его из одного объекта Grid, затем используем его для создания другого объекта Grid и т. д. Итак, чтобы избежать побочных эффектов, которые могут возникнуть при передаче его по ссылке, мы будем использовать функцию deepcopy(), поэтому нам нужно импортировать ее. Еще одна вещь, которую мы будем импортировать, - это Tuple и List из typing; это потому, что мы будем использовать подсказки типа.
from copy import deepcopy from typing import Tuple, List
Самое простое, с чего мы можем начать, - это создать методы для установки и получения атрибута matrix класса. Затем мы создадим метод размещения плитки на доске; для этого мы просто установим соответствующий элемент матрицы на номер плитки. Параметры входной строки / столбца имеют индекс 1, поэтому нам нужно вычесть 1; номер плитки присваивается как есть.
Затем мы определим метод __init__(), который будет просто устанавливать атрибут матрицы.
Для минимаксного алгоритма нам нужно будет проверить Grid объектов на равенство. Мы будем считать 2 Grid объекта равными, если матрицы двух объектов одинаковы, и для этого воспользуемся __eq__() магическим методом. Мы перебираем все элементы двух матриц, и как только мы обнаруживаем несоответствие, мы возвращаем False, в противном случае в конце возвращается True.
Далее мы создаем служебный метод. Этот метод позволяет оценить, насколько хороша наша игровая сетка. Для этого может быть много возможных вариантов, но здесь мы используем следующую метрику (как описано в предыдущей статье): суммировать все элементы матрицы и разделить на количество ненулевых элементов.
Следующий фрагмент кода немного сложен. Нам нужно проверить, может ли Макс сделать одно из следующих движений: вверх, вниз, влево, вправо. Код для каждого из этих ходов очень похож, поэтому я объясню только один из этих ходов: вверх, который реализован в методе .canMoveUp().
Когда мы хотим сделать движение «вверх», все может измениться только по вертикали. Между разными столбцами доски нет взаимодействия. Итак, мы можем запускать код независимо для каждого столбца.
Мы можем сделать это в цикле for:
И нам не обязательно проверять все столбцы. Как только мы встречаем столбец, который позволяет что-то изменить при движении «вверх», мы возвращаем True. Если такого столбца нет, мы возвращаем False в конце.
Для каждого столбца мы делаем следующее: начинаем снизу и движемся вверх, пока не встретим непустой (›0) элемент. После того, как мы увидим такой элемент, как мы можем узнать, меняет ли движение «вверх» что-то в этом столбце? Две возможные вещи могут привести к изменению: либо есть пустой квадрат, по которому может перемещаться тайл, либо есть 2 одинаковых соседних тайла.
В качестве примера:
Выделенный ниже код отвечает за поиск самого нижнего непустого элемента:
Выделенный ниже фрагмент кода возвращает True, как только находит пустой квадрат, в который можно переместить плитку, или возможное слияние двух плиток.
Ниже приведен код всех этих методов, которые работают аналогично методу .canMoveUp().
Нам понадобится метод, который возвращает доступные ходы для Max и Min. Для Макса это будет подмножество движений: вверх, вниз, влево, вправо. Мы представим эти ходы целыми числами; с каждым направлением будет связано целое число:
- Up = 0
- Вниз = 1
- Слева = 2
- Вправо = 3
В методе .getAvailableMovesForMax() мы проверяем, можем ли мы двигаться в каждом из этих направлений, используя наши ранее созданные методы, и в случае, если результат верен для направления, мы добавляем соответствующее целое число в список, который мы вернем в конце метод.
Метод .getAvailableMovesForMin() вернется, перекрестное произведение между набором пустых мест в сетке и набором {2, 4}. Это возвращаемое значение будет списком кортежей в форме (строка, столбец, плитка), где строка и столбец - координаты пустых ячеек с индексом 1, а фрагмент - одно из {2, 4}.
.getChildren() принимает параметр, который может иметь значение «max» или «min», и возвращает соответствующие ходы, используя один из двух предыдущих методов. Это ходы, которые приводят к игровым состояниям детей в дереве минимаксного алгоритма.
Для минимаксного алгоритма нам нужен способ определения, является ли состояние игры терминальным. Как я уже говорил в предыдущей статье, мы будем считать состояние игры терминальным, если нет доступных ходов или достигается определенная глубина. Но проверку условия глубины было бы легче выполнить внутри самого алгоритма минимакса, а не внутри этого класса. Итак, методом .isTerminal() мы будем проверять только, есть ли доступные ходы для Max или Min. Простой способ сделать это - использовать .getAvailableMovesForMin() или .getAvailableMovesForMax(), чтобы вернуть список со всеми ходами, и если он пуст, вернуть True, в противном случае - False. Но более эффективный способ - вернуть False, как только мы «увидим» доступный ход, и в конце, если False не было возвращено, вернуть True.
Метод .isGameOver() - это просто сокращение для .isTerminal(who=”max”), и он будет использоваться как конечное условие в нашем цикле решения игры (в следующей статье).
Приведенные ниже методы предназначены для выполнения одного из движений вверх, вниз, влево, вправо. На этот раз мы действительно делаем эти движения, а не просто проверяем, можно ли их сделать. Код для каждого направления движения похож, поэтому я объясню только движение вверх.
Подъем можно сделать независимо для каждого столбца. У нас будет цикл for, который выполняет итерацию по столбцам. Для каждого столбца мы инициализируем переменные w и k равными 0. w содержит местоположение следующей операции записи. k сохраняет значение плитки последней обнаруженной непустой ячейки.
Алгоритм работает следующим образом:
А вот пример того, как это работает для данного столбца:
Ниже приведен код со всеми 4 методами: .up(), .down(), .left(), .right():
Затем мы создаем оболочку вокруг вышеуказанных 4 методов и называем ее .move(), которая перемещается в направлении, заданном в качестве параметра.
Еще нам понадобится «обратный» метод хода. .move() принимает в качестве параметра код направления и затем выполняет перемещение. Теперь нам нужен метод, который принимает в качестве параметра другой объект Grid, который считается прямым потомком при вызове .move() и возвращает код направления, сгенерировавший этот параметр. Назовем этот метод .getMoveTo().
Этот метод работает путем создания копий текущего объекта, а затем поочередного вызова .up(), .down(), .left(), .right() этих копий и проверки на равенство параметру метода. И если равенство истинно, мы возвращаем соответствующий код направления.
Ниже приведен полный код класса Grid:
И это все для этой статьи. В следующем (последнее около 2048 года и минимаксе) мы увидим, как мы можем управлять игровой доской веб-версии этой игры, реализовать алгоритм минимакса и наблюдать, как он играет лучше нас (... или, по крайней мере, лучше чем я).
Надеюсь, эта информация была для вас полезной, и спасибо за внимание!
Эта статья также размещена на моем собственном сайте здесь. Не стесняйтесь смотреть!
