Главная

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

2016-12-12 в 6:13, admin, рубрики: 2048, c++, python, Алгоритмы, игры, стратегии

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

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

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

Выбирает две случайные ячейки на игровом поле, размещает в каждой из них по двойке и выводит координаты этих ячеек.
Пока игрок не сделает тупиковый ход (ход после которого игровое поле не меняется) движок выполняет цикл:
1. Прочитать ход игрока.
2. Выполнить этот ход на игровом поле.
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)