Новая игра 2048

[GraNiNi]

Новое улучшение - 1230.

[GraNiNi]

Еще немного: 1252

[GraNiNi]

Еще улучшение: 1376

[GraNiNi]

Новое улучшение: 1420


Методом тыка нашел удобную для себя стратегию.
Играю как в Тетрис.
Появляющиеся квадраты опускаю вниз, чтобы они там сливались. Если готовых к слиянию по вертикали нет, то перемещаю по горизонтали вправо или влево, выбирая наиболее удачный вариант для последующего слияния вниз.
Игра быстрая, 1-3 мин почти не думая.
Когда переваливаю за 1000 (было больше 10 раз), то тогда торможу и начинаю думать внимательнее, куда выгоднее смещать.

[photon]

1494

[GraNiNi]

Обновил: 1702

[Mikhail_K]

dimkadimon
А вот вопрос: если кто-то случайно забредёт на сайт Вашей игры, поиграет и поставит какой-то рекорд, как он мог бы об этом дать знать? Ваших контактов на сайте игры я не увидел. Кажется, стоит написать там что-то вроде: если вы поставили рекорд, напишите об этом вот сюда, приложив скриншот экрана "Game Over" с поставленным рекордом (по-моему, хорошая традиция), и попадёте в таблицу рекордов.
Можно при этом сократить таблицу до первых десяти или пятнадцати пунктов. Тогда такие обращения вряд ли будут частыми.

[rockclimber]

У меня новых рекордов нет.
Но я попробовал написать программу, которая будет играть сама.
Изначально идея была научить играть нейросеть, и уж нейросеть-то утрет всем носы. Но, поскольку сам я этого не умею, то я быстро накидал на джаве REST API сервис, который делает ходы, и воспользовался опцией "звонок другу". Идея была в том, что "друг" сделает все остальное (научит нейросеть, как отправлять ходы на мой "сервер" и получать результат оттуда). Кончилось тем, что делать пришлось все самому, но под чутким руководством.
Пока было две попытки. Первая - решение методом Монте-Карло (то есть моя программа делает случайные ходы, смотрит, что получится, и выбирает лучшие). Результат (после прогонов нескольких тысяч игр): среднее количество очков - около 670, лучший результат - порядка 2700.
Пробовал добавлять разные элементы обсуждавшихся в топике стратегий. Результаты:
Избегать "шахматной" расстановки плиток - никакого эффекта.
Избегать ходов в одну сторону (то есть одно основное направление, два дополнительных, а в четвертом направлении - не ходить) - никакого эффекта.
Плитка с максимальным числом должна быть с краю - удивительно, но эффект есть! Поднимает среднее с 630 - 635 до 665 - 670.
Первые несколько ходов просто ходить по кругу - эффекта нет, но первые 6 кругов (24 хода) не дают никакого отрицательного эффекта, зато экономят время на расчеты.

Теперь пилю минимакс. Пока есть один небольшой баг, никак не могу выловить. Из-за этого игра не доигрывается до конца. Но почти всегда доигрывает до 400 - 500 очков (прежде, чем возникает баг), так что я верю в результат.

Если кому интересно пообсуждать алгоритмы, могу написать подробности и поделиться кодом. Можно даже отдельный топик создать.

Есть еще идея для стратегии, как играть "вручную". Нужно собирать плитки в группы по цвету. Группой считаются плитки одного цвета, если они граничат друг с другом по горизонтали или по диагонали. Ходы нужно делать в направлении, которое минимизирует число групп. Если есть две плитки одного цвета и равного номинала, желательно их соединять. Но вообще лучше вкладывать все в одну плитку.

[kotenok gav]

kotenok gav в сообщении #1527801 писал(а):

420 набрал.

-- 01 авг 2021, 13:57 --

532.

-- 01 авг 2021, 14:07 --

656. Вот как раз трёхсдвиговая стратегия хорошо помогает.

736. Нашёл новую стратегию, кажется (которую, однако, очень сложно удерживать, и она ломается довольно быстро) - собирать оранжевые и синие квадраты в разных столбцах/строках. В идеале два столбца для тех и два для тех, и удерживать это. И столбцы одного цвета должны быть соседними, да.

-- 12 сен 2021, 14:56 --

Для этого должно выполняться минимум два условия: 1) начальные квадраты отстоят на две клетки или три друг от друга по одной из осей, и 2) как можно быстрее должны появиться по одному квадратику в каждом столбце (и они должны быть разными, по типу 3-6-2-4). Тогда выходит удерживать стратегию довольно долго.

[Mikhail_K]

kotenok gav в сообщении #1531360 писал(а):

736. Нашёл новую стратегию, кажется (которую, однако, очень сложно удерживать, и она ломается довольно быстро) - собирать оранжевые и синие квадраты в разных столбцах/строках.

Ну да, я тоже так стараюсь делать, когда получается.

[dimkadimon]

GraNiNi в сообщении #1531005 писал(а):

Обновил: 1702

Отлично!

-- 13.09.2021, 11:32 --

Mikhail_K в сообщении #1531290 писал(а):

Кажется, стоит написать там что-то вроде: если вы поставили рекорд, напишите об этом вот сюда, приложив скриншот экрана "Game Over" с поставленным рекордом (по-моему, хорошая традиция), и попадёте в таблицу рекордов.

Хорошая идея. Только страшно свой емайл всем показывать из за спамма.

-- 13.09.2021, 11:37 --

rockclimber
Очень интересно, спасибо! Я тоже пытался сделать бота с Монте Карло. Перед каждым ходом он играл много продолжений позиции и выбирал ход который достигает наибольшее среднее количество очков. После недели таких игр, бот достиг 3060. Я заметил что бот играет лучше если использовать только 3 направления (четвертое только если нет выхода). Вот тут побольше информации: https://puzzling.stackexchange.com/ques ... oured-2048

Мне интересно как можно сделать бота сильнее. Про минимакс не думал, но идея хорошая. Только не понимаю как у вас получается искать все дерево минимакса если оно растет так быстро? Опишите подробнее пожалуйста.

[Mikhail_K]

dimkadimon в сообщении #1531442 писал(а):

Хорошая идея. Только страшно свой емайл всем показывать из за спамма.

Не знаю, например мой e-mail указан много где в общем доступе. Спам, конечно, идёт тоннами, но весь фильтруется в автоматическом режиме моей Яндекс почтой. И никаких проблем нет.

Ну или можете поставить на сайт игры ссылку на эту тему на dxdy и, может быть, на другие площадки, где люди могут написать о поставленном рекорде.

[rockclimber]

dimkadimon в сообщении #1531442 писал(а):

Только не понимаю как у вас получается искать все дерево минимакса если оно растет так быстро?

А у меня и не получается. Сначала я просто запустил построение дерева с выводом отладочной информации, чтобы посмотреть на динамику роста. Через какое-то время программа упала с ошибкой "Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded". Я позапускал несколько раз, поставил на глаз лимит роста 12 000 000 узлов в дереве решений. Это 3 - 4 уровня, иногда 5, ближе к концу игры - до 11 - 12. В минимаксе еще нужна функция оценки состояния, чтобы выбирать ходы, - у меня это пока просто сумма набранных очков. Начинаю с ходов по кругу (6 кругов, или 24 хода). Пока этого достаточно. На один ход уходит примерно несколько секунд. Примерно до 20 - 30 секунд, если размер дерева получается близким к лимиту в 12 миллионов узлов.

[dimkadimon]

rockclimber в сообщении #1531451 писал(а):

"Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded"

Можно попробовать использовать больше памяти в Java через параметры -Xms и -Xmx. Но думаю рано или поздно все равно будет слишком много узлов. Можно еще не все узлы хранить, а только через раз, правда тогда пропадет гарантия оптимальности минимакса.

-- 13.09.2021, 16:32 --

Mikhail_K
Добавил ссылку на мой емайл. Посмотрим сколько новых рекордов появится.

[rockclimber]

Я и сам догадался, что можно разрешить виртуальной машине использовать больше памяти, только смысла мало. На 24-м ходу число возможных вариантов обычно варьируется от 30 до 60. Соответственно, если у меня есть 10 000 000 узлов (я прикинул на глаз, это порядка 200 - 300 мегабайт), нет смысла увеличивать память. Во-первых, на следующий уровень мне нужно будет от 30 до 60 раз больше памяти, от 6 до 18 ГБ примерно. Во-вторых, если 10 000 000 узлов генерируется порядка минуты, следующий уровень потребует получаса расчетов.
Может быть потом, когда отлажу алгоритм и оптимизирую немного, можно будет попробовать.