[Из песочницы] Сравнение стратегий игры 2048
2048 — игра появившаяся в 2014ом году и быстро ставшая популярной убивалкой времени. Простые правила игры только подталкивают игроков к созданию клонов, ботов и выигрышных стратегий. В том числе и на Хабре. (Клон, бот, стратегия) В этой статье рассказывается про удобный инструмент оценки стратегий игры и примеры его работы на нескольких ботах.
Сам инструмент состоит из трёх частей. Первая — это движок на C++. С ним можно играть и вручную в консоли. Работает он по следующему алгоритму:
Выбирает две случайные ячейки на игровом поле, размещает в каждой из них по двойке и выводит координаты этих ячеек.
Пока игрок не сделает тупиковый ход (ход после которого игровое поле не меняется) движок выполняет цикл:
- Прочитать ход игрока.
- Выполнить этот ход на игровом поле.
- Вывести координату ячейки в которой появилось новое случайное значение (двойка или четвёрка) и само это значение.
- По окончанию игры выводит количество ходов, счёт и время игры в миллисекундах.
Для симуляции игрового поля движок использует класс из board.hpp. Объявление этого класса с комментариями.
template 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 random(); // Возвращает координаты пустой ячейки в которой появилась случайная 2 или 4
void out() const; // Выводит содержимое матрицы a. Выполняется при вызове move(0)
unsigned score = 0; // Счёт
bool deadlock = false; // Изменилось ли поле после последнего хода
static std::mt19937 rand; // Генератор случайных чисел
std::array,n> a; // Матрица хранящая содержимое каждой ячейки поля
public:
A(); //
std::vector init(); // Вызывается в самом начале и возвращает координаты двух ячеек с двойками
std::vector 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
Комментарии (4)
SystemXFiles
12 декабря 2016 в 10:18
0↑
↓
А почему бы не добавить еще других ботов, которые анализируют ситуацию иначе?
К примеру я обычно играю так:
- Выбираем направление стандартное (к примеру вниз).
- Делаем ходы в стандартном направлении.
- Если сделать ход более не можем, то делаем наиболее выгодный ход перпендикулярно стандартному направлению (в моем примере это влево или вправо) и переходим ко 2-ому пункту.
Такая стратегия давала хороший результат при минимуме размышлений.
12 декабря 2016 в 11:10
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-
SystemXFiles
12 декабря 2016 в 11:33 (комментарий был изменён)
0↑
↓
Хах, спасибо =) Немного неожиданный результат.
Интересно уже, а какая схема самая оптимальная (даже если в плане размышлений не учень удобна)?
Просто 4-ый вариант, что представлен в статье, кажется слегка недоработанным.Что будет, если научить такой вариант наперед проверять (моделировать «в уме») вероятность исхода, например:
- Есть вероятность тупика (и к примеру вычисляется численная вероятность такого исхода).
- Таблица вероятностей различных схлапываний фигур.
Т.е. позволить боту размышлять и выбирать оптимальный вариант с учетом возможного будущего?
saluev
12 декабря 2016 в 10:18
0↑
↓
Было бы ещё интересно на вероятностные распределения очков посмотреть.
