Pull to refresh

Максимум в 2048

Algorithms *
Awaiting invitation
Вирус 2048 прошёл отлично по всему офису и явно притормозил выпуск продукта.
Как обычно, задача решалась в несколько этапов и постепенно усложнялась.

image
История создания бота. Или как набрать 4096.


1. Получить выигрыш.

Сходу больше 512 получить никому не удалось. Достаточно быстро все разделились на 2 группы:
* писать бота,
* решать ручками.

Алгоритмы.
а) по возможности двигать вниз, потом вправо, если не получилось влево, если опять не получилось, то вверх.
алгоритм обычно набирал 256-512.
Тем временем появилась новая стратегия собирать одинаковые значения по диагонали и потом быстро их схлопывать. Руками получалось набрать 512-1024.
image

б) складывать минимальные числа. т.е. если есть двойки — складывать их.
существенного улучшения не получилось. В итоге максимальный результат 512.

в) освобождать максимальное количество клеток.
сильно лучше не стало. В среднем всё те же 256-512, но максимальный результат 1024.

* Тем временем удалось ручками по «змейке» набрать 2048.

г) Весовая функция.
Поправив кучу багов. И выстави весовую функцию змейкой:

1 128 256 32768
2 64 512 16384
4 32 1024 8192
8 16 2048 4096

бот начал регулярно набирать 1024.

д) Комбинации движений + весовая функция.
Оставили весовую функцию и стали просчитывать на 2 движения вперед.
Появление новых цифр ботом не учитывались.
С первой попытки бот набрал 2048.
Победа.

2. Получить максимум.
Отключили в игре ограничение на остановку по достижению 2048.

var actuate = GameManager.prototype.actuate;
GameManager.prototype.actuate = function() {
this.won = false;
return actuate.apply(this, arguments);
}


Бот достаточно быстро достиг 4096. Изначально 4096 отображалось вылезая за пределы квадрата.
Спасибо автору за оперативность. Поправил стиль 4096, сделал специальную кнопку «keep going» для продолжения игры.

e) Предсказание появления.
Боту добавили возможность осознавать что где-то появится 2 или 4. Это сильно улучшило работу в критичных позициях, когда остается 2-3 свободных клетки.
Частота набора 4096 выросла на 30-40%.

г) Добавили возможность выбора глубины прогнозирования, упростили матрицу весов.
После экспериментов глубина предсказания 3 дала наилучшие результаты.

После всех правок бот играет явно лучше человека.

Один из лучших скриншотов.
image

Посмотреть работу бота (включается по нажатию play)

Код бота

Битва за 8096 продолжается.
Tags:
Hubs:
You can’t comment this post because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author’s username will be hidden by an alias.