2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Новая игра 2048
Сообщение29.08.2021, 15:57 


01/04/08
2720
Новое улучшение - 1230.
Изображение

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение31.08.2021, 20:05 


01/04/08
2720
Еще немного: 1252

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение01.09.2021, 23:00 


01/04/08
2720
Еще улучшение: 1376

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение02.09.2021, 20:45 


01/04/08
2720
Новое улучшение: 1420
Изображение

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

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение04.09.2021, 01:56 
Экс-модератор
Аватара пользователя


23/12/05
12046
1494 :roll:

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение08.09.2021, 20:30 


01/04/08
2720
Обновил: 1702

Изображение

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение11.09.2021, 14:03 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение11.09.2021, 22:53 
Заслуженный участник


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

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

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

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

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение12.09.2021, 08:18 


21/05/16
4292
Аделаида
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). Тогда выходит удерживать стратегию довольно долго.

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение12.09.2021, 18:38 
Заслуженный участник
Аватара пользователя


26/01/14
4601
kotenok gav в сообщении #1531360 писал(а):
736. Нашёл новую стратегию, кажется (которую, однако, очень сложно удерживать, и она ломается довольно быстро) - собирать оранжевые и синие квадраты в разных столбцах/строках.
Ну да, я тоже так стараюсь делать, когда получается.

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение13.09.2021, 05:45 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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

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

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение13.09.2021, 08:02 
Заслуженный участник
Аватара пользователя


26/01/14
4601
dimkadimon в сообщении #1531442 писал(а):
Хорошая идея. Только страшно свой емайл всем показывать из за спамма.
Не знаю, например мой e-mail указан много где в общем доступе. Спам, конечно, идёт тоннами, но весь фильтруется в автоматическом режиме моей Яндекс почтой. И никаких проблем нет.

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

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение13.09.2021, 10:23 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
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 миллионов узлов.

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение13.09.2021, 10:28 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
rockclimber в сообщении #1531451 писал(а):
"Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded"

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

-- 13.09.2021, 16:32 --

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

 Профиль  
                  
 
 Re: Новая игра 2048
Сообщение13.09.2021, 10:54 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 88 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group