Программирование простых алгоритмов игры в 2048 на Python

Очень много туториалов и примеров того, как написать копию игры 2048 на всех языках, но программирование алгоритмов для этой игры — задача не менее интересная. Продвинутые алгоритмы сводятся к машинному обучению Reinforcement Learning или методу Монте-Карло, но ведь написать хороший простой алгоритм без машинного обучения — интересная задача и не только для начинающих программистов

TLDR: В этой статье мы рассмотрим, как на языке Python реализовать и запустить на портале code2048ga.me одну из простых стратегий для игры 2048 — приоритетную стратегию

Договоримся, что будем писать стратегии в следующем виде — это будет функция make_choice, которая принимает на вход двухмерный массив — состояние игрового поля и возвращает ответ — строку “LEFT”, “RIGHT”, “UP”, “DOWN” — направление движения

Случайная стратегия

Самая простая стратегия игры — совершать случайные свайпы и надеяться на чудо. Случайная стратегия интересна нам как эталон для сравнения, с ней мы будем сравнивать наши другие стратегии

import random
def make_choice(matrix):
    return random.choice(["LEFT", "RIGHT", "UP", "DOWN"])

Random strategy as is

Оценим успехи этой стратегии

Запустим стратегию на 100 играх. Среднее количество очков, набираемых случайной стратегией колеблется в пределах 700–800 очков, лишь немногие запуски набирают более 1500 очков. Максимально достигаемая в случайной стратегии плитка имеет как правило значение 64 или 128, очень редко достигается плитка 256, а часть игр даже закончилась с максимальным значением плитки 32

Приоритетная стратегия

Очень простая эвристика сможет нам помочь достигнуть большего. Давайте выберем два приоритетных направления — одно по вертикали и одно по горизонтали. Если теперь мы будем стараться использовать эти направления во всех подходящих ситуациях— самые крупные плитки будут скапливаться в одном из углов и (теоретически) легче соединяться в более крупные.

Высокоуровневая логика такой стратегии очень проста — формируем список направлений и на каждом ходу идем по списку, определяем возможен ли ход в указанном направлении и если да — возвращаем его как ответ, Например, так будет выглядить приоритетная стратегия для списка направлений [“DOWN”, “RIGHT”, “UP”, “LEFT”]

Как реализовать такую стратегию?

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

Приступим!

Свайп одной строки

Начнем очень издалека — напишем функцию для свайпа одной строки игрового поля влево. Функция должна получать строку и возвращать ее состояние после свайпа (пример на рисунке ниже)

Свайп одной строки происходит в два этапа.

1. Первый шаг — мы “выдавливаем” все пустые клетки в конец строки

2. Далее при необходимости “склеиваем” две соседние клетки с одинаковыми значениями в одну. Важно учитывать, что согласно правилам, одна клетка за один ход “склеивается” лишь единожды, поэтому строка [2, 2, 2, 2] перейдет в строку [4, 4, 0, 0], а не в строку [8, 0, 0, 0]

Примерный код функции, принимающий на вход строку и возвращающий строку после свайпа, написан ниже

def row_left_swipe(row):
    # stage 0: check if the row is non-empty
    if sum(row) == 0:
        return row
 
    # stage 1: remove zeroes
    new_row = []
    for i in range(4):
        if row[i] != 0:
        new_row.append(row[i]) 
    
    new_row += [0] * (4 — len(new_row))
 
    # stage 2: merging tiles
    for i in range(3):
       if new_row[i] == new_row[i + 1]:
          new_row[i] = new_row[i] * 2
          new_row.pop(i + 1)
          new_row.append(0)
 
    return new_row

Рассмотрим код подробнее. Первым делом проверяем, не пустая ли нам пришла строка ([0, 0, 0, 0]), если да, то возвращаем ее же

Далее первый этап — создаем новый список new_row и помещаем в него все ненулевые элементы из оригинального списка. После “дополняем” его нулями до длины 4.

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

Свайп игрового поля

Теперь от одной строки перейдем ко всему полю

Легко при помощи написанной выше функции row_left_swipe сделать свайп влево уже не только для строки, но и для всего игрового поля. Если представлять, что игровое поле — это матрица 4х4, то функция для свайпа всего поля влево будет выглядить так:

def swipe_left(matrix):
    for i in range(4):
        matrix[i] = row_left_swipe(matrix[i])
 
    return matrix

Но что, если нам нужен свайп не влево, а в любом другом направлении — вниз, вправо, вверх?

Рассмотрим, например, свайп вправо

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

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

Шаг 1: поворачиваем поле дважды против часовой стрелки

Шаг 2: при помощи функции swipe_left, которую задали выше, делаем свайп влево перевернутого поля

Шаг 3: возвращаем все назад — делаем два полных поворота против часовой стрелки

Можем убедиться, что результаты совпали

Аналогичным образом можно сделать свайп вниз и вверх, для этого нужно поворачивать поле на 1 полный оборот для свайпа вниз или на 3 полных оборота для свайпа вверх. Предлагаю вам убедиться в этом самим.

Итак, функцию для свайпа зададим как функцию, которая принимает матрицу игрового поля и направления свайпа. Для начала создадим словарь соответствия rotate_count— сколько поворотов туда и назад нужно совершить для свайпа и после напишем непосредственно функцию swipe используя написанную выше функцию свайпа влево swipe_left

rotate_count = {
    "LEFT": 0,
    "UP": 3,
    "RIGHT": 2,
    "DOWN": 1
}
def swipe(matrix, direction):
    rotates = rotate_count[direction]
    
    for i in range(rotates):
        matrix = rotate_ccw(matrix)
        
    matrix = swipe_left(matrix)
    
    for i in range(rotates):
        matrix = rotate_cw(matrix)
        
    return matrix

Единственное, что осталось за кадром — как именно совершать повороты матрицы по и против часовой стрелки — функции rotate_ccw и rotate_cw, которые мы использовали выше (названия функций расшифровываются так: rotate — поворот, ccw — counterclockwize — против часовой стрелки, cw —clockwize — по часовой стрелке)

Реализуем поворот против часовой стрелки (в корректности этой в целом несложной функции предлагаю убедиться самостоятельно):

def rotate_ccw(matrix):
    new_matrix = [[0] * 4 for i in range(4)]
    
    for row in range(4):
        for col in range(4):
            new_matrix[col][3 - row] = matrix[row][col]
    return new_matrix

Обратите внимание на инициализацию new_matrix — эта с виду сложная строка просто создает пустой двухмерный массив 4х4. Фактически, она эквивалентна строке ниже:

new_matrix = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

… далее “хитро”, но не очень эффективно зададим поворот по часовой стрелке как трижды поворот против:

def rotate_cw(matrix):
    for i in range(3):
        matrix = rotate_ccw(matrix)
    return matrix

Теперь мы умеем делать свайп игрового поля в любом направлении

Проверка возможности хода и итоговый алгоритм

После всех подготовительных работ, наконец, перейдем к алгоритму

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

Высокоуровневый код функции алгоритма make_choice будет выглядить вот так:

def make_choice(matrix):
    # let's try to stack the biggest value in the down right corner
    prioritize_directions = ["DOWN", "RIGHT", "UP", "LEFT"]
  
    for direction in prioritize_directions:
        if is_move_is_possible(matrix, direction):
            return direction

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

Единственное, что нам осталось реализовать, это функцию is_move_is_possible — проверку возможности хода по направлению. Реализуем эту функцию очень легко — будем смотреть, изменилось ли состояние поля после имитации хода: если изменилось — ход возможен, иначе ход невозможен

def is_move_is_possible(matrix, direction):
    return matrix != swipe(matrix, direction)

Ниже приведен полный код алгоритма со всеми вспомогательными функциями, доступный для проверки и запуска на code2048ga.me

def row_left_swipe(row):
    # stage 0: check if the row is non-empty
    if sum(row) == 0:
        return row
    
    # stage 1: remove zeroes
    new_row = []
    for i in range(4):
        if row[i] != 0:
           new_row.append(row[i]) 
    new_row += [0] * (4 - len(new_row))
    
    # stage 2: merging tiles
    for i in range(3):
        if new_row[i] == new_row[i + 1]:
            new_row[i] = new_row[i] * 2
            new_row.pop(i + 1)
            new_row.append(0)
            
    return new_row
    
            
def swipe_left(matrix):
    for i in range(4):
        matrix[i] = row_left_swipe(matrix[i])
    
    return matrix
def rotate_ccw(matrix):
    new_matrix = [[0] * 4 for i in range(4)]
    
    for row in range(4):
        for col in range(4):
            new_matrix[col][3 - row] = matrix[row][col]
    return new_matrix
    
    
def rotate_cw(matrix):
    for i in range(3):
        matrix = rotate_ccw(matrix)
    return matrix
    
    
rotate_count = {
    "LEFT": 0,
    "UP": 3,
    "RIGHT": 2,
    "DOWN": 1
}
def swipe(matrix, direction):
    rotates = rotate_count[direction]
    
    for i in range(rotates):
        matrix = rotate_ccw(matrix)
        
    matrix = swipe_left(matrix)
    
    for i in range(rotates):
        matrix = rotate_cw(matrix)
        
    return matrix
def is_move_is_possible(matrix, direction):
    return matrix != swipe(matrix, direction)
def make_choice(matrix):
    # let's try to stack the biggest value in the down right corner
    prioritize_directions = ["DOWN", "RIGHT", "UP", "LEFT"]
  
    for direction in prioritize_directions:
        if is_move_is_possible(matrix, direction):
            return direction

Анализ эффективности алгоритма

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

Видим, что как правило “приоритетная” стратегия достигает максимального значения плитки 64 или 128, а в нескольких случаях ей даже удалось собрать плитку 512. Что касается количества игровых очков — значение колеблется в границах от 1000 до 4000, некоторые запуски заканчивались на значении в 5–6 тысяч очков

Как видим, работает стабильно лучше рандома :)

Эта стратегия не является самой оптимальной и даже ее можно улучшить, например при помощи добавления “жадности” — возможно, я напишу об этом в следующих статьях. Любые ваши эксперименты по усовершенствованию алгоритма можно проводить на платформе code2048ga.me, автором которой я являюсь

Буду рад ответить на все вопросы в комментариях. Если вам понравился эта статья или в целом проект code2048ga.me — я буду особенно благодарен, если вы купите мне кофе