Сравнение стратегий игры 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 раз в одинаковых условиях.

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

ссылка на оригинал статьи https://habrahabr.ru/post/317370/