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







Номер бота Середн. кроки Хв. кроки Макс. кроки Середн. рахунок Хв. рахунок Макс. рахунок Середн. час Хв. час Макс. час 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
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.