Руководство для начинающих по ИИ и написанию собственного бота для игры 2048

Оглавление этой статьи:

Введение в тему ИИ
Описание и анализ игры 2048
Первые шаги по написанию бота, например. реализация импорта данных и ввода с клавиатуры
Жадный подход к проблеме
Обновление нашего алгоритма и теории минимаксных деревьев
Добавление эвристики для улучшения оценки
Стратегии оптимизации и альфа-бета-сокращение
Заключение темы

Введение в тему ИИ

Искусственный интеллект — одно из самых развивающихся направлений в ИТ-индустрии. Это просто интеллект, демонстрируемый машинами, в отличие от естественного интеллекта, демонстрируемого людьми и другими животными. За последние несколько лет тема получила массовую популяризацию. Бьюсь об заклад, вы уже слышали об автономных автомобилях, роботах для повседневного использования и многом другом. Это не только упрощает нашу жизнь, но и позволяет делать дела быстрее, качественнее и с гораздо большей вероятностью успеха. Теория игр — одна из самых первых областей, с которой столкнулся искусственный интеллект, и в этой статье я объясню самые основы создания собственного бота.

Описание и анализ игры 2048

2048 — это однопользовательская игра-головоломка с раздвижными блоками, разработанная итальянским веб-разработчиком Габриэле Чирулли. Основная цель игры состоит в том, чтобы перемещать пронумерованные плитки по сетке, чтобы объединить их и создать плитку с номером 2048. Игра стала вирусным хитом и завоевала мировую популярность.

Несмотря на то, что правила кажутся простыми, получение плитки 2048 может оказаться довольно сложной задачей. Я настоятельно рекомендую поиграть в игру самостоятельно, прежде чем писать бота. Это может дать вам некоторые идеи о том, как подойти к проблеме, и, кроме того, эта игра просто очень забавная. Вы можете воспроизвести ее здесь.

Вот некоторые наблюдения, которые помогут нам создать нашу игровую стратегию:

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

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

Первые шаги по написанию бота

Чтобы начать писать нашего бота, нам нужно выбрать правильный язык программирования. Я использовал Python 3.6. Возможно, это не самый быстрый и оптимальный выбор, но лично мне удобно писать в нем. Язык интуитивно понятен, имеет простой синтаксис и множество полезных библиотек.

Когда вы освоили язык, наша следующая забота — импорт данных. Мой подход к этой проблеме довольно прямолинеен и прост. Я использую библиотеку подушек, чтобы сделать скриншот экрана, а затем преобразовать его в оттенки серого. Каждое значение имеет свою собственную плитку с определенным цветом, поэтому это позволяет мне определить, какое значение оно содержит. Чтобы это произошло, нам сначала нужны координаты для каждой плитки на доске. Для этого я использую библиотеку pyautogui. Вот действительно простой код для этого:

import pyautogui

while True:
    print(pyautogui.displayMousePosition())

Он покажет координаты вашего курсора.

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

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

# Printing gray scale values for every point in Coords class
# coordsArray is just an array of coordinates 
def printGrayscale():
    image = ImageGrab.grab()
    image = ImageOps.grayscale(image)
    
    for i in range(4):
        row = []
        for j in range(4):
            row.append(image.getpixel(Coords.coordsArray[i*4 + j]))
        print(row)

Следующее, что нужно сделать, это реализовать ключевой ввод. Я просто использовал функцию в библиотеке pyautogiu. Код действительно прост:

# Constant values representing directions
UP = 100
DOWN = 101
LEFT = 102
RIGHT = 103
# Performing move
def performMove(move):
    if move == UP:
        print("Going UP")
        pyautogui.keyDown('up')
        pyautogui.keyUp('up')
    if move == DOWN:
        print("Going DOWN")
        pyautogui.keyDown('down')
        pyautogui.keyUp('down')
    if move == LEFT:
        print("Going LEFT")
        pyautogui.keyDown('left')
        pyautogui.keyUp('left')
    if move == RIGHT:
        print("Going RIGHT")
        pyautogui.keyDown('right')
        pyautogui.keyUp('right')

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

Жадный подход к проблеме

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

scoreGrid = [50,  30,  20,  20,
             30,  20,  15,  15,
             15,   5,   0,   0,
             -5,  -5, -10, -15]

Чтобы рассчитать наш счет, вам просто нужно суммировать произведения весов и значений плитки для каждой занятой плитки на доске. Формально наша оценка:

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

Я сам пробовал несколько вариантов, когда начинал этот проект, и набрал лучший результат (даже выиграл один или два раза) с увеличением веса в форме змеи. Это выглядит так (4^^3 означает 4³ и т. д.):

scoreGrid = [4^^15, 4^^14, 4^^13, 4^^12,
             4^^8,  4^^9,  4^^10, 4^^11,
             4^^7,  4^^6,  4^^5,  4^^4,
             4^^0,  4^^1,  4^^2,  4^^3]

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

Обновление нашего алгоритма и теории минимаксных деревьев

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

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

Теперь перейдем к самому алгоритму. Два игрока участвуют в игре, называемой MIN и MAX. Игрок MAX пытается получить максимально возможное количество очков, а MIN пытается получить минимально возможное количество очков, то есть MIN и MAX пытаются действовать друг против друга. Общий процесс алгоритма Минимакса выглядит следующим образом:

Шаг 1. Сгенерируйте все дерево игры, начиная с текущей позиции игры и заканчивая конечными состояниями. Для крестиков-ноликов наше игровое дерево будет выглядеть так:

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

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

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

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

Псевдокод для этого алгоритма так же прост, как и его идея:

function minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

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

Добавление эвристики для улучшения оценки

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

Эвристика пустых плиток:

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

Эвристика гладкости:

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

Эвристика монотонности:

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

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

Стратегии оптимизации и альфа-бета-сокращение

Мы обновили нашу функцию полезности некоторыми причудливыми эвристиками, поэтому пришло время оптимизировать алгоритм MiniMax. Самым большим недостатком текущего состояния алгоритма является потребление памяти и времени. Мы рассмотрим алгоритм сокращения Alpha-Beta, который является известным способом увеличения размера дерева MiniMax.

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

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

Бета: Точно так же это лучший выбор для MIN, и это должно быть наименьшее возможное значение.

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

Шаг 1: инициализируйте альфа = -∞ и бета = ∞ как наихудшие возможные случаи. Условием для обрезки узла является то, что альфа становится больше или равна бета.

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

Шаг 3. Перенесите эти значения альфы и беты в дочерний узел слева. Из значения полезности терминального состояния мы будем обновлять значения альфа и бета. Пока не выполнено условие обрезки, оставляем все как есть.

Вот псевдокод для этого алгоритма:

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if α ≥ β then
                break (* β cut-off *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if α ≥ β then
                break (* α cut-off *)
        return value
(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

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

Заключение темы

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

Ссылки: