Комментарии 21
35584 получилось в браузере
Не так интересен общий счёт как максимальная плитка.
И вот тут никак не удаётся добраться до 32768 :(
Методом Монте-Карло, судя по всему, даже вдвое меньшая плитка 16k недостижима.
Вручную некоторые маньяки (в том числе и с хабра) достигали и более высоких результатов чем 32k, выкладывая плиточки змейкой. Но я даже боюсь подумать сколько часов нужно убить на это. Лично у меня рекорд 4096, дальше я скучаю и бросаю игру.
Если же речи об ИИ, то с помощью minimax и expectimax можно достигать максимально возможных результатов. Эти способы тоже разберём в ближайшее время.
Вручную некоторые маньяки (в том числе и с хабра) достигали и более высоких результатов чем 32k, выкладывая плиточки змейкой. Но я даже боюсь подумать сколько часов нужно убить на это. Лично у меня рекорд 4096, дальше я скучаю и бросаю игру.
Если же речи об ИИ, то с помощью minimax и expectimax можно достигать максимально возможных результатов. Эти способы тоже разберём в ближайшее время.
В опции игры когда 1 последний ход можно было отменить — я руками набирал плитку 131072, но с 7й попытки вроде (если бы можно было отменять несколько то и 1й всегда можно), месяц на 8й примерно :)
Пруф
А сколько времени уходит на один сеанс подобного марафона?
По моему опыту примерно месяц катания на метро:)
Тоже делал когда то максимальную плитку.
Тоже делал когда то максимальную плитку.
Хочу уточнить — это каждый день, при поездке на работу и обратно приходилось начинать заново каждый раз? И как-то раз — хоп — удалось собрать максимум?
Или же Вы действовали обдуманно и не спеша, приостанавливая игру когда прибываете к месту назначения и затем с этой позиции продолжая играть в следующей поездке? И таким образом, одна-единственная игра длилась почти месяц?
Или же Вы действовали обдуманно и не спеша, приостанавливая игру когда прибываете к месту назначения и затем с этой позиции продолжая играть в следующей поездке? И таким образом, одна-единственная игра длилась почти месяц?
Нет, нет! Конечно, прогресс сохранялся.
Месяц это по протяженности. А само время игры как именно игры — гораздо меньше.
Но оценить в часах очень сложно. Все таки, иногда я не играл, а дремал или играл в другие игры или читал.
На самом деле если чуть потренироваться, думаю за пол дня можно сделать максимальную плитку. Но добить максимум очков как у voted это сильно сложнее.
Еще нюанс — возникают плитки 2 или 4. Так вот если в неправильный момент возникли плитки 2 и 4 (вместо двух четверок!), то максимальное количество очков не получается. Поэтому без UNDO никак. Или же начинать сначала.
Месяц это по протяженности. А само время игры как именно игры — гораздо меньше.
Но оценить в часах очень сложно. Все таки, иногда я не играл, а дремал или играл в другие игры или читал.
На самом деле если чуть потренироваться, думаю за пол дня можно сделать максимальную плитку. Но добить максимум очков как у voted это сильно сложнее.
Еще нюанс — возникают плитки 2 или 4. Так вот если в неправильный момент возникли плитки 2 и 4 (вместо двух четверок!), то максимальное количество очков не получается. Поэтому без UNDO никак. Или же начинать сначала.
Это «с продолжением».
Посчитайте для примера, если взять тупо ход в секунду, сколько их уйдёт на набор хотя бы плитки 64К.
Реально несколько дней в транспорте.
Я добирался до состояния («змейкой») [64К, 16К, 8К, 4К, 2К, 512, 256, 64, 32, 16, 8] с пустыми клетками, это примерно 1,35 млн. очков. Но дальше — перешел на езду за рулём и на 2048 забил.
Играю методом заполнения «змейкой», с ходами только в трёх направлениях.
Посчитайте для примера, если взять тупо ход в секунду, сколько их уйдёт на набор хотя бы плитки 64К.
Реально несколько дней в транспорте.
Я добирался до состояния («змейкой») [64К, 16К, 8К, 4К, 2К, 512, 256, 64, 32, 16, 8] с пустыми клетками, это примерно 1,35 млн. очков. Но дальше — перешел на езду за рулём и на 2048 забил.
Играю методом заполнения «змейкой», с ходами только в трёх направлениях.
На эту конкретно попытку ушло месяца 2 или 3, по 1-3 часа в день игры, прогресс сохранялся, в это время я за утренним кофе ленту FB не просматривал, играл в транспорте (игра не требует инета), когда ждал в каких то очередях, ну и само собой вместо чтения в туалете :)
Почему-то за три прогона ИИ ни разу не воспользовался оптимальной стратегией — загнать максимальную плитку в один из углов и выстраивать остальные змейкой
Потому что в данном случае эта стратегия не запрограммирована.
Монте-Карло вообще «недальновидный» метод. Его философия — нахапать побольше очков здесь и сейчас, не заботясь о том, что с увеличением значения максимальной плитки в произвольном месте поля — схлопывать всё сложнее и сложнее. Поэтому и достигается планка 4096, выше которой в Монте-Карло прыгнуть почти никогда нельзя.
Метод минимакса, который будет разобран в следующей хабрастатье действует уже стратегически, держа самую жирную плитку в углу и стагивая к ней плитки поменьше с обеих сторон. Это ещё не пресловутая «змейка», но уже нечто похожее на неё.
А потом мы дойдём до expectimax, которому хоть и не указывается прямо собирать «змейкой», но который интуитивно выходит именно на неё. Этот метод способен собрать максимально возможное количество на поле.
Можно сказать, что мы разберём эти методы ИИ в порядке возрастания их интеллектуальности — от самого топорного (Монте-Карло — это почти брутфорс) к наиболее изощрённому.
Монте-Карло вообще «недальновидный» метод. Его философия — нахапать побольше очков здесь и сейчас, не заботясь о том, что с увеличением значения максимальной плитки в произвольном месте поля — схлопывать всё сложнее и сложнее. Поэтому и достигается планка 4096, выше которой в Монте-Карло прыгнуть почти никогда нельзя.
Метод минимакса, который будет разобран в следующей хабрастатье действует уже стратегически, держа самую жирную плитку в углу и стагивая к ней плитки поменьше с обеих сторон. Это ещё не пресловутая «змейка», но уже нечто похожее на неё.
А потом мы дойдём до expectimax, которому хоть и не указывается прямо собирать «змейкой», но который интуитивно выходит именно на неё. Этот метод способен собрать максимально возможное количество на поле.
Можно сказать, что мы разберём эти методы ИИ в порядке возрастания их интеллектуальности — от самого топорного (Монте-Карло — это почти брутфорс) к наиболее изощрённому.
Почему-то после прочтения захотелось попробовать реализовать нечто похожее, но на генетических алгоритмах. Но что-то мне подсказывает, что через минут 15 это желание пройдет :)
Энтузиазм может сойти на нет, если будете с нуля писать 2048 а уже потом писать обучение. Если сэкономите силы и не допустите преждевременного перегорания — т.е. найдёте и разберетесь уже в какой-либо готовой реализации 2048 и сразу приступите к своему алгоритму, то есть вероятность что запала хватит довести дело до конца.
В качестве уже реально выбираемого хода выбирается тот начальный ход, который показал наибольший средний результат.
В игре новые плитки выпадают случайным образом. А для Монте-Карло все прогоны должны идти по одной и той же последовательности плиток, так?
Смотрите, как это происходит.
Возникла некая позиция. Нужно решить какой сделать ход. Варианта 4: вверх, вниз, влево и вправо.
ИИ просчитывает (не совершает реально в игре, а именно просчитывает) вариант: «делаем ход — вверх». Затем, когда он сделал этот ход, в этом варианте в случайном порядке порождает случайную новую плитку, потом делает случайный ход в любом направлении, снова рождает случайную плитку, потом снова случайный ход, потом снова генерирует плитку и т.д. до тех пор пока не проиграет. Фиксируется количество набранных очков.
Так повторяется 100 раз (и каждый раз, ввиду рандомности последующих ходов и генерации плиток в произвольных местах — это уникальный ход игры). ИИ получает некое среднее количество очков, если он ходит первым ходом «вверх».
Всё это делается и для оставшихся трёх направлений для первого хода из заданной позиции — вниз, влево, вправо. В итоге для каждого из четырёх направлений у ИИ есть статистика сколько в среднем набирается очков если сделать первый ход в одном из четырёх возможных направлений (последующие ходы и генерации плиток происходят случайно). ИИ выбирает тот ход, который показал наилучшее среднее и делает этот ход в реальной игре.
Возникла некая позиция. Нужно решить какой сделать ход. Варианта 4: вверх, вниз, влево и вправо.
ИИ просчитывает (не совершает реально в игре, а именно просчитывает) вариант: «делаем ход — вверх». Затем, когда он сделал этот ход, в этом варианте в случайном порядке порождает случайную новую плитку, потом делает случайный ход в любом направлении, снова рождает случайную плитку, потом снова случайный ход, потом снова генерирует плитку и т.д. до тех пор пока не проиграет. Фиксируется количество набранных очков.
Так повторяется 100 раз (и каждый раз, ввиду рандомности последующих ходов и генерации плиток в произвольных местах — это уникальный ход игры). ИИ получает некое среднее количество очков, если он ходит первым ходом «вверх».
Всё это делается и для оставшихся трёх направлений для первого хода из заданной позиции — вниз, влево, вправо. В итоге для каждого из четырёх направлений у ИИ есть статистика сколько в среднем набирается очков если сделать первый ход в одном из четырёх возможных направлений (последующие ходы и генерации плиток происходят случайно). ИИ выбирает тот ход, который показал наилучшее среднее и делает этот ход в реальной игре.
Я ступил, всегда же выпадает двойка, поэтому входные данные никак не меняются.
А есть ли такой метод Монте-Карло для поиска в дереве, где в прогоне не надо доигрывать до конца? Чтобы прорабатывать определённые ветки, а не брутфорсить.
А есть ли такой метод Монте-Карло для поиска в дереве, где в прогоне не надо доигрывать до конца? Чтобы прорабатывать определённые ветки, а не брутфорсить.
>>> всегда же выпадает двойка, поэтому входные данные никак не меняются
«Двойка» бывает не всегда, в 10% случаев выпадает «четвёрка». Кроме того, новая плитка может возникнуть в любом пустом месте поля и от этого существенно зависит ход игры. Но это и не важно. В методе Монте-Карло по большому счёту просто собирается статистика: если в текущей позиции сделать первый ход «вверх» («вниз», «влево», «вправо»), последующие ходы и генерация новых плиток — как угодно — то сколько в среднем набирается очков.
>>> А есть ли такой метод Монте-Карло для поиска в дереве, где в прогоне не надо доигрывать до конца? Чтобы прорабатывать определённые ветки, а не брутфорсить.
В принципе, следующие методы — minimax и expectimax, как раз на эту тему. Там, по большому счёту, тоже случайно генерируются последующие ходы для заданного первого хода, но при этом решительно отсекаются явно невыгодные ответвления в дереве вариантов.
«Двойка» бывает не всегда, в 10% случаев выпадает «четвёрка». Кроме того, новая плитка может возникнуть в любом пустом месте поля и от этого существенно зависит ход игры. Но это и не важно. В методе Монте-Карло по большому счёту просто собирается статистика: если в текущей позиции сделать первый ход «вверх» («вниз», «влево», «вправо»), последующие ходы и генерация новых плиток — как угодно — то сколько в среднем набирается очков.
>>> А есть ли такой метод Монте-Карло для поиска в дереве, где в прогоне не надо доигрывать до конца? Чтобы прорабатывать определённые ветки, а не брутфорсить.
В принципе, следующие методы — minimax и expectimax, как раз на эту тему. Там, по большому счёту, тоже случайно генерируются последующие ходы для заданного первого хода, но при этом решительно отсекаются явно невыгодные ответвления в дереве вариантов.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
ИИ и 2048. Часть 1: Метод Монте-Карло