Сравнение стратегий игры 2048

2048 — игра появившаяся в 2014ом году и быстро ставшая популярной убивалкой времени. Простые правила игры только подталкивают игроков к созданию клонов, ботов и выигрышных стратегий. В том числе и на Хабре. (Клон, бот, стратегия) В этой статье рассказывается про удобный инструмент оценки стратегий игры и примеры его работы на нескольких ботах.


Скриншот игры



Сам инструмент состоит из трёх частей. Первая — это движок на C++. С ним можно играть и вручную в консоли. Работает он по следующему алгоритму:


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


  2. Пока игрок не сделает тупиковый ход (ход после которого игровое поле не меняется) движок выполняет цикл:


    1. Прочитать ход игрока.
    2. Выполнить этот ход на игровом поле.
    3. Вывести координату ячейки в которой появилось новое случайное значение (двойка или четвёрка) и само это значение.

  3. По окончанию игры выводит количество ходов, счёт и время игры в миллисекундах.

Для симуляции игрового поля движок использует класс из board.hpp. Объявление этого класса с комментариями.


template<int n> class A{                  // Игровое поле размером n
private:
    int left_adder(int&, int);            // 16 функций необходимых для работы функции move
    int left_compressor(int&, int);       // Внутри классов нельзя создавать namespace
    int left_move_row(int);               // Была попытка создать 4 вложенных класса
    int left_move();                      // с четырьмя статическими функциями в каждом,
    int right_adder(int&, int);           // но заметных преимуществ в таком решении не было
    int right_compressor(int&, int);      //
    int right_move_row(int);              //
    int right_move();                     //
    int up_adder(int&, int);              //
    int up_compressor(int&, int);         //
    int up_move_column(int);              //
    int up_move();                        //
    int down_adder(int&, int);            //
    int down_compressor(int&, int);       //
    int down_move_column(int);            //
    int down_move();                      //
    std::pair<int,int> random();          // Возвращает координаты пустой ячейки в которой появилась случайная 2 или 4
    void out() const;                     // Выводит содержимое матрицы a. Выполняется при вызове move(0)
    unsigned score = 0;                   // Счёт
    bool deadlock = false;                // Изменилось ли поле после последнего хода
    static std::mt19937 rand;             // Генератор случайных чисел
    std::array<std::array<int,n>,n> a;    // Матрица хранящая содержимое каждой ячейки поля
public:
    A();                                  //
    std::vector<int> init();              // Вызывается в самом начале и возвращает координаты двух ячеек с двойками
    std::vector<int> move(int);           // Делает ход
    unsigned get_score() const;           // Возвращает счёт
};

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


И третья часть — это простой bash-скрипт, который "соединяет" первых два компонента и выводит статистику в читаемом виде.


Примеры ботов


Все 4 бота написаны на питоне при помощь модуля board и отличаются только оценочной функцией. В оценочную функцию передаётся один аргумент — текущее состояние игрового поля. Для определения доступных ходов у игрового поля есть метод deadlock. С движком общается функция main.


1. Случайный выбор


Бот делает случайный доступный ход. Этот бот сделан, только чтобы сравнить его эффективность с эффективностью остальных ботов.


Средний результат: 1250


Исходный код
import random
import board

def f(a):
    l = [1, 2, 3, 4]
    ans = random.choice(l)
    while a.deadlock(ans) and l != []:
        ans = random.choice(l)
        del l[l.index(ans)]
    if l == [] and a.deadlock(ans):
        ans = 0
    return ans

board.main(f)

2. Перемещения по кругу


Первым своим ходом бот делает ход вверх, а потом выбирает следующий ход по часовой стрелке пропуская тупиковые.


Средний результат: 2900


Исходный код
import board

def f(a):
    global h
    ans = h % 4 + 1
    while a.deadlock(ans) and ans != h:
        ans = ans % 4 + 1
    h = ans
    return h

h = 0
board.main(f)

3. Всё в один угол


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


Средний результат: 3900


Исходный код
import board

def f(a):
    global h
    if h == 1:
        l = [2, 1]
    else:
        l = [1, 2]
    l += [4, 3, 0]
    while a.deadlock(l[0]) and l[0] != 0:
        l = l[1:]
    h = l[0]
    return h

h = 0
board.main(f)

4. Максимум очков


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


Средний результат: 4000


Исходный код
import board

def f(a):
    max = 0
    ans = 0
    for i in range(1, 5):
        if not a.deadlock(i):
            b = a.copy()
            t = b.move(i)
            if (t >= max):
                ans = i
                max = t
    return ans

board.main(f)

Статистика


Все боты проверялись 1000 раз в одинаковых условиях.


Номер бота Средн. шаги Мин. шаги Макс. шаги Средн. cчёт Мин. счёт Макс. счёт Средн. время Мин. время Макс. время
1 131 50 266 1259 240 3216 90 60 242
2 233 57 647 2885 292 11296 108 52 234
3 311 98 859 3905 740 14700 155 78 363
4 317 70 826 4027 412 13292 776 116 2692

Все исходники на Github

Поделиться публикацией

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 7

    0

    А почему бы не добавить еще других ботов, которые анализируют ситуацию иначе?


    К примеру я обычно играю так:


    1. Выбираем направление стандартное (к примеру вниз).
    2. Делаем ходы в стандартном направлении.
    3. Если сделать ход более не можем, то делаем наиболее выгодный ход перпендикулярно стандартному направлению (в моем примере это влево или вправо) и переходим ко 2-ому пункту.

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

      0
      А почему бы не добавить еще других ботов, которые анализируют ситуацию иначе?

      Будет много простых ботов с разными алгоритмами и примерно одинаковым результатом. Я тестировал пять вариантов третьего бота т.к. он показывал слишком маленький результат по сравнению с четвёртым. Для сложных ботов где есть дерево ходов на котором можно реализовать хотя бы минмакс у питона не хватает производительности. И сам код написан неэффективно. Для этого нужно писать бота на С++. А для этого нужно переписывать класс поля или наследовать новый. Всё это сложно, долго и тянет на отдельную статью.


      К примеру я обычно играю так:

      Исходный код
      import board
      
      def choice_best(a, x, y):
          b = a.copy()
          s1 = b.move(x)
          b = a.copy()
          s2 = b.move(y)
          if s1 > s2:
              return x
          else:
              return y
      
      def f(a):
          ans = 3
          if not a.deadlock(ans):
              return ans
          else:
              ans = choice_best(a, 2, 4)
              if not a.deadlock(ans):
                  return ans
              elif not a.deadlock(list({2, 4} - {ans})[0]):
                  return list({2, 4} - {ans})[0]
              elif not a.deadlock(1):
                  return 1
              else:
                  return 0
      
      board.main(f)

      Тестировал только 100 раз и на более загруженной системе. Средний результат где-то между вторым и третьим ботом.


      Результат
      Average:
          Steps: 281  Score: 3428 Time: 233
      Min:
          Steps: 76   Score: 520  Time: 82
      Max:
          Steps: 589  Score: 8640 Time: 552
        0

        Хах, спасибо =) Немного неожиданный результат.


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


        Что будет, если научить такой вариант наперед проверять (моделировать "в уме") вероятность исхода, например:


        1. Есть вероятность тупика (и к примеру вычисляется численная вероятность такого исхода).
        2. Таблица вероятностей различных схлапываний фигур.

        Т.е. позволить боту размышлять и выбирать оптимальный вариант с учетом возможного будущего?

          +1
          Можно будет диссертацию писать, вот что будет.
            0

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


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

      0
      Было бы ещё интересно на вероятностные распределения очков посмотреть.
        +1
        Оказалось, что datawrapper не умеет сохранять картинки. Пришлось импровизировать чтобы заново всё не переделывать. Если есть желание самому визуализацию сделать, то могу полную статистику скинуть.
        Бот 1


        Бот 2


        Бот 3


        Бот 4


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

      Самое читаемое