Загрузка...Как выиграть в змейку
Всех сожру, один останусь: или о том, как в slither io выиграть [видео]
SlitherIO уже успели назвать очередной интернет-сенсацией. Тут уж как посмотреть, конечно. Знавали мы сенсаций и покруче. Однако факт остается фактом: в эту внешне простенькую браузерную игрушку играет столько народу во всем мире, что до уровня симпатичненького такого хита она уже точно доросла. В этой связи, немного о том, как играть в эту игру и, самое главное, как в slither io выиграть.
Для тех, кто совсем еще не в курсе, короткий ликбез для начала.
Итак, в SlitherIO каждый игрок начинает совсем крошечным червячком (или змейкой, кому как удобнее). Сначала (первые секунд 30) всё предельно просто: надо ползать по игровому полю, кушать светящиеся шарики и расти. Чем больше червяк, тем лучше.
Но есть нюанс: в этой игре червячок, неудачно стукнувшись мордочкой о другого червячка, немедленно погибает, распадаясь на большие светящиеся шарики.
Их сразу же потребляют ближайшие конкуренты, поскольку такие шарики являются более ценными в энергетическом плане, и их поедание в значительной мере ускоряет рост персонажа.
Таким образом, в SlitherIO крутится надо очень грамотно: нужно и шариков побольше съесть, и попытаться как-то аккуратно и точно подставить бочок под удар соседу, чтобы схарчить то, что от него останется, и в то же время не разбиться самому. В общем, забот — выше крыши.
Получается, что slither io выиграть как бы и невозможно, зато при желании можно попробовать стать лучше всех. Кстати, рейтинг самых толстых и самых шустрых в игрушке тоже публикуется, и по заработанным топовыми геймерами очкам можно сразу понять, сколько и кого надо превратить в шарики, чтобы побыть немного, так сказать, на вершине пищевой цепочки^
Собственно, теперь несколько советов от тех, кто много достиг в попытке стать самым-самым в slither io. Итак:
юзаем карту SlitherIO
Поначалу игрок ее вообще не замечает, но карта ближайших окрестностей игрового поля в slither io все же есть, расположена она в правом нижнем углу экрана, и пользы от нее на самом деле немало.
К примеру, с ее помощью можно находить места, где крутится меньше других червяков, и где получится спокойно съесть больше шариков, меньше беспокоясь о собственной сохранности.
В таких «тихих заводях», подальше от насыщенного трафика центра карты, червячка откормить получается до весьма внушительных размеров. Правда, только если повезет не попасть на глаза более опытным геймерам, которые тоже пользуются картой, но исключительно с целью найти скрывающихся в таких местах любителей безопасно покушать.
загоняем и закольцовуем
Червяк, сумевший вырасти достаточно длинным, получает преимущество перед меньшими и тем более совсем маленькими конкурентами.
Он может просто обвиться кольцом вокруг своей добычи, и у той не останется другого пути, как от безысходности разбиться о тело хищника, став кучкой новых вкусных шариков. Да, тактика не самая гениальная, к тому же требует некоторой сноровки, но зато и эффект не заставит себя ждать.
стена поможет в slither io выиграть ситуацию
Свой звериный оскал «мирная» (как часто пишут в описании игрушки) конкуренция в SlitherIO вам продемонстрирует очень быстро. Потому соображать и действовать тоже приходится без лишних медлительности и жалости.
Но иногда вы будете замечать, что жертва, которую вы пытаетесь взять в кольцо, стремится не просто удрать, а целенаправленно старается завести вас в стену и/или разбиться о стену сама. Фишка — в том, что стена в игре тоже убивает, но иначе. В том смысле, что, стукнувшись о стену, червяк тоже погибает, и геймер начинает игру сначала.
Однако, разбившись о стену, червяк просто исчезает, не оставляя после себя шарики жадному конкуренту. Так что, стены могут помочь в slither io выиграть ситуацию: если не удается разбить о них врага и избавиться от угрозы, то можно разбиться самому, отомстив хищнику нулевым выигрышем.
скорость
Скорость движения червяка в игре можно увеличивать нажатием кнопки мышки. Но разгоняться надо умеючи, иначе «превышение» сразу же станет причиной столкновения и гибели. Тем не менее, обязательно надо научиться использовать свое преимущество в скорости.
Во-первых, быстрого и верткого червяка гораздо труднее поймать в кольцо, во-вторых, от стремительного и проворного хищника крайне трудно спастись.
Так что, скорость в slither io, как правило, только помогает. Но есть и ограничение: двигаясь в ускоренном режиме червячок худеет, точнее уменьшается. Медленно, но, как показывает практика, этого достаточно, чтобы игрок не увлекался «червячными гонками на низкой высоте».
Легендарную игру «Змейка» на Nokia 3310 удалось пройти до конца
Почти двадцать лет назад, в 2000-ом году, самым популярным кнопочным телефоном была Nokia 3310, обладающая очень большим запасом прочности, хорошей автономностью и множеством других положительных качеств, за которые миллионы людей продолжают вспоминать ее и по сей день. В нее была встроена игра «Змейка», которая впоследствии стала легендарной. В 2017 году финская корпорация HMD Global запустила в продажу новую версию телефона Nokia 3310, и в нее также оказалась встроена эта игра.
Суть игры «Змейка» в том, чтобы максимально увеличить размер змеи, но при этом добиться того, чтобы она не врезалась в свой длинный хвост. Жительнице России удалось пройти эту легендарную игру, причем на все у нее ушло всего 30 минут. Ранее сделать это казалось невозможным, но россияне то удалось. За счет этого удалось выяснить, чем же заканчивается эта видеоигра, когда свободного пространства для маневров больше нет.
Выяснилось, что пройти легендарную игру «Змейка» невозможно, потому как в самом конце змея сама врезается в свой хвост – другого варианта развития события просто нет. Максимальное количество очков, которое можно получить при прохождении данной игры на Nokia 3310 – 0781. Когда на экране телефона остается всего одна свободна клетка, еда для увеличения змеи перестает появляться, а как следствие – пройти игру до самого конца, чтобы змея заполнила все пространство на экране, невозможно.
Россиянка выразила разочарование в том, что компания HMD Global не предусмотрела возможность прохождения «Змейки» на Nokia 3310, посчитав, что пройти ее полностью никто не сможет. Хватило бы просто каких-то надписей со словами «Поздравляем, мы победили!». Увы, но ничего этого нет. Змея просто продолжает гнаться за своих хвостом до тех самых пор, пока игрок не совершит какую-то ошибку, после чего начинать весь процесс придется заново.
Недавно HMD Global представила новый «смартфон-банан» образца 2018 года, который получил широкую известность по фильму «Матрица».
Присоединяйтесь к нам в G o o g l e News , Twitter, Facebook, ВКонтакте, YouTube и RSS чтобы быть в курсе последних новостей из мира технологий будущего.
Большой разбор: как ИИ играет в змейку
Современные технологии против игры прошлого века.
Помните, раньше была такая игра — змейка? Она появилась в 70-х, и в неё играли на всём: от компьютеров и приставок до кнопочных телефонов. Например, если вы пропустили то время, это могло выглядеть вот так:
- Вы управляете змейкой, которая постоянно в движении, она может двигаться вверх, вниз, влево или вправо. На экране в случайном месте появляется клеточка — считайте, что это еда.
- Ваша задача — собрать как можно больше еды.
- Как только змейка съедает очередную клеточку с едой, в случайном месте появляется новая клетка. Также змейка удлиняется на одну клетку.
- Если змейка упрётся в стенку или сама в себя, то игра заканчивается.
В начале игры всё просто: поле пустое, змейка вольготно по нему ползает и жрёт. Но дальше змейка постепенно растёт, занимая всё большую площадь экрана, и в какой-то момент передвигаться становится суперсложно. И вот тогда нужна стратегия и ловкость.
Австралийский программист Эван, он же CodeBullet, научил искусственный интеллект играть в эту игру и сделал об этом видео:
Если вы знаете английский, просто смотрите и получайте удовольствие, а если нет — мы приготовили подробный разбор того, что происходит в ролике.
Начало: 5 разных алгоритмов
В самом начале Эван экспериментировал с нейросетью, чтобы найти лучший алгоритм для игры в змейку. В итоге у него получилось 5 разных алгоритмов, каждому из которых он дал своё имя. Они отличались стилем игры, поведением в разных ситуациях и результативностью.
Степан. Это одна из первых версий алгоритма, у которой есть одна характерная особенность: Стёпа любит двигаться по диагонали.
Несмотря на то, что кажется, что змейка делает всё правильно, это самая худшая версия нейронки, которая получилась у программиста. При этом умение Стёпки двигаться по диагонали — уникально, оно сильно пригодится в будущем.
Лена. Она умнее Стёпы, двигается более предсказуемо, а ещё у неё классно получается избегать столкновения с собой. Это важное умение для змейки, потому что если голова упрётся в хвост или в тело — игра закончится.
Лена отлично умеет выбираться из сложных ситуаций.
Миша. Быстрая, эффективная змейка почти без единого лишнего движения. Миша почти идеален, но этого недостаточно.
Коля. Умеет собирать много кусочков, но когда становится совсем длинным, то размер начинает ему мешать.
Сёма. Чемпион среди этих версий, потому что только он смог набрать 136 очков — больше, чем остальные кандидаты.
Собираем в одно целое
Можно было остановиться на Сёме, но Эван решил пойти дальше и подумал: «А что если объединить эти змейки в одну, чтобы вместе они работали максимально эффективно?»
Для этого программист сделал одну большую нейросеть, в которую поместил 5 змеек по такому алгоритму:
- Перед каждым следующим шагом каждая из пяти змеек говорит, как бы она поступила в этой ситуации.
- Отдельная нейросеть смотрит на варианты и выбирает лучший из них.
- Змейка делает шаг, и всё начинается сначала.
Смысл в том, чтобы использовать сильные стороны каждой змейки для наибольшего эффекта.
Добавляем цвета
Чтобы стороннему наблюдателю было понятно, что происходит на экране и о чём именно «думает» нейронка, Эван придумал раскрашивать змейку в разные цвета:
- зелёный означает, что змейка нашла очередной кусочек, который можно съесть, и это стало её целью;
- синий — змея предвидит, что скоро она будет двигаться к еде;
- белый — рядом со змеёй нет легкодоступных кусочков, и её задача — выжить и никуда не врезаться.
Теперь мы тоже можем понимать, какие решения принимает искусственный интеллект в каждой ситуации. Самое интересное, что иногда мы даже можем понять, какая из змеек сейчас взяла управление на себя.
Например, тут явно Степан. 
А вот тут Лена помогает Стёпе не врезаться в самого себя.
Появился синий цвет: это означает, что змейка видит еду и думает, как бы подобраться к ней поближе.
Даже тут виден кусочек Стёпы 🙂 
Новая змейка побила рекорд Сёмы, и даже с такой длиной она легко движется дальше. 
Начались первые проблемы: белый цвет означает, что змейке не до еды и нужно выбираться из такой ситуации. 
А вот отсюда змейка уже выбраться не сумеет, хотя путь для выхода у неё есть. Рекорд — 204 очка.
Запустим снова и проверим, получится ли побить этот рекорд:
200 очков и почти катастрофа, но змейка всё же нашла решение. Поразительно. 
Набрав 228 очков, змейка внезапно врезается в свой хвост, хотя места в середине достаточно для трёх таких змеек.
Рекорд побит, и, скорее всего, не в последний раз. С каждым запуском алгоритм становится умнее, и змейка допускает всё меньше и меньше ошибок.
Что дальше
Дальше как обычно — новые большие разборы, объяснение того, как работают нейросети и как это применить на практике. Лайк, подписка, все дела.
Как искусственный интеллект играет в «Змейку»
Рассказываем о нейросети, которая применяет глубокое обучение и обучение с подкреплением, чтобы играть в Змейку. Код на Github, разбор ошибок, демонстрации игры искусственного интеллекта и эксперименты над ним вы найдете под катом.
С тех пор, как я посмотрела документальный фильм Netflix об AlphaGo, я была очарована обучением с подкреплением. Такое обучение сравнимо с человеческим: вы видите что-то, делаете что-то и у ваших действий есть последствия. Хорошие или не очень. Вы учитесь на последствиях и корректируете действия. У обучения с подкреплением множество приложений: автономное вождение, робототехника, торговля, игры. Если обучение с подкреплением вам знакомо, пропустите следующие два раздела.
Обучение с подкреплением
Принцип простой. Агент учится через взаимодействие со средой. Он выбирает действие и получает отклик от среды в виде состояний (или наблюдений) и наград. Этот цикл продолжается постоянно или до состояния прерывания. Затем наступает новый эпизод. Схематично это выглядит так:
Цель агента — получить максимум наград за эпизод. Вначале обучения агент исследует среду: пробует разные действия в одном и том же состоянии. С течением обучения агент исследует всё меньше. Вместо этого он, основываясь на собственном опыте, выбирает действие, приносящее наибольшую награду.
Глубокое обучение с подкреплением
Глубокое обучение использует нейронные сети, чтобы из входных данных получать выходные. Всего один скрытый слой — и глубокое обучение может приближать любую функцию. Как это работает? Нейронная сеть — это слои с узлами. Первый слой — это слой входных данных. Скрытый второй слой преобразует данные с помощью весов и функции активации. Последний слой — это слой прогноза.
Как следует из названия, глубокое обучение с подкреплением — это комбинация глубокого обучения и обучения с подкреплением. Агент учится прогнозировать лучшее действие для данного состояния, используя состояния как входные данные, значения для действий как выходные данные и награды для настройки весов в правильном направлении. Давайте напишем Змейку с применением глубокого обучения с подкреплением.
Определяем действия, награды и состояния
Чтобы подготовить игру для агента, формализуем проблему. Определить действия просто. Агент может выбирать направление: вверх, вправо, вниз или влево. Награды и состояние пространства немного сложнее. Есть много решений и одно будет работать лучше, а другое хуже. Одно из них опишу ниже и давайте попробуем его.
Если Змейка подбирает яблоко, ее награда 10 баллов. Если Змейка умирает, отнимаем от награды 100 баллов. Чтобы помочь агенту, добавляем 1 балл, когда Змейка проходит близко к яблоку и отнимаем один балл, когда Змейка удаляется от яблока.
У состояния много вариантов. Можно взять координаты Змейки и яблока или направления к яблоку. Важно добавить расположение препятствий, то есть стен и тела Змейки, чтобы агент учился выживать. Ниже резюме действий, состояний и наград. Позже мы увидим, как корректировка состояния влияет на производительность.
Создаем среду и агента
Добавляя методы в программу Змейки, мы создаём среду обучения с подкреплением. Методы будут такими: reset(self) , step(self, action) и get_state(self) . Кроме того, нужно рассчитывать награду на каждом шаге агента. Посмотрите на run_game(self) .
Агент работает с сетью Deep Q, чтобы найти лучшие действия. Параметры модели ниже:
Если интересно посмотреть на код, вы найдёте его на GitHub.
Агент играет в Змейку
А теперь — ключевой вопрос! Научится ли агент играть? Понаблюдаем, как он взаимодействует со средой. Ниже первые игры. Агент ничего не понимает:
Первое яблоко! Но по-прежнему выглядит так, будто нейросеть не знает, что делает.
Находит первое яблоко… и чуть позже ударяется о стену. Начало четырнадцатой игры:
Агент учится: его путь к яблоку не самый короткий, но он находит яблоко. Ниже тридцатая игра:
После всего 30 игр Змейка избегает столкновений с самой собой и находит быстрый путь к яблоку.
Поиграем с пространством
Может быть, возможно изменить пространство состояний и достичь похожей или лучшей производительности. Ниже возможные варианты.
- Без направлений: не сообщать агенту направления, в которых движется Змейка.
- Состояние с координатами: замени положение яблока (вверх, вправо, вниз и / или влево) координатами яблока (x, y) и змеи (x, y). Значения координат находятся на шкале от 0 до 1.
- Состояние «направление 0 или 1».
- Состояние «только стены»: сообщает только о том, есть ли стена. Но не о том, где находится тело: внизу, наверху, справа или слева.
Ниже графики производительности разных состояний:
Найдем пространство, ускоряющее обучение. График показывает средние достижения последних 12 игр с разными состояниями.
Понятно, что когда пространство состояний имеет направления, агент учится быстро, достигая наилучших результатов. Но пространство с координатами лучше. Может быть, можно достичь лучших результатов, дольше тренируя сеть. Причиной медленного обучения может быть число возможных состояний: 20⁴*2⁴*4 = 1,024,000. Поле 20 на 20, 64 варианта для препятствий и 4 варианта текущего направления. Для исходного пространства вариантов 3²*2⁴*4 = 576. Это более чем в 1700 раз меньше, чем 1,024,000 и, конечно, влияет на обучение.
Поиграем с наградами
Есть ли лучшая внутренняя логика награждения? Напоминаю, Змейка награждается так:
Первая ошибка. Хождение по кругу
Что, если изменить -1 на +1? Это может замедлить обучение, но в конце концов Змейка не умирает. И это очень важно для игры. Агент быстро учится избегать смерти.
На одном временном отрезке агент получает один балл за выживание.
Вторая ошибка. Удар о стену
Изменим количество баллов за прохождение около яблока на -1. Награду за само яблоко установим в 100 баллов. Что произойдет? Агент получает штраф за каждое движение, поэтому двигается к яблоку максимально быстро. Так может случиться, но есть и другой вариант.
ИИ проходит по ближайшей стене, чтобы минимизировать потери.
Нужно только 30 игр. Секрет искусственного интеллекта — опыт предыдущих игр, который учитывается, чтобы нейросеть училась быстрее. На каждом обычном шаге выполняется ряд шагов переигрывания (параметр batch_size ). Это так хорошо работает потому, что для данной пары действия и состояния разница в награде и следующем состоянии небольшая.
Ошибка №3. Нет опыта
Опыт действительно так важен? Давайте уберём его. И возьмём награду за яблоко в 100 баллов. Ниже агент без опыта, сыгравший 2500 игр.
Хотя агент сыграл 2500 (!) игр, в змейку он не играет. Игра быстро заканчивается. Иначе 10 000 игр заняли бы дни. После 3000 игру у нас только 3 яблока. После 10 000 игр яблок по-прежнему 3. Это удача или результат обучения?
Действительно, опыт очень помогает. Хотя бы опыт, учитывающий награды и тип пространства. Как много нужно переигрываний на шаг? Ответ может удивить. Чтобы ответить на этот вопрос, поиграем с параметром batch_size. В исходном эксперименте он установлен в 500. Обзор результатов с разным опытом:
200 игр с разным опытом: 1 игра (опыта нет), 2 и 4. Среднее за 20 игр.
Даже с опытом в 2 игры агент уже учится играть. В графе вы видите влияние batch_size , та же производительность достигается на 100 игр, если вместо 2 используется 4. Решение в статье дает результат. Агент учится играть в Змейку и достигает хороших результатов, собирая от 40 до 60 яблок за 50 игр.
Внимательный читатель может сказать: максимум яблок в змейке — 399. Почему ИИ не выигрывает? Разница между 60 и 399, в сущности, небольшая. И это верно. И здесь есть проблема: Змейка не избегает столкновений при замыкании на себя.
Интересный способ решить проблему — использовать CNN для поля игры. Так ИИ может увидеть всю игру, а не только ближайшие препятствия. Он сможет распознавать места, которые нужно обойти, чтобы победить.
Получить востребованную профессию с нуля или Level Up по навыкам и зарплате, можно, пройдя онлайн-курсы SkillFactory:
Искусственный интеллект для змейки. Часть 1: Кратчайший/длиннейший путь, Гамильтонов цикл
Рейтинг: 32
В этой статье я хочу показать различные подходы к решению классической игры Змейка (Источник идеи статьи). Думаю, правила и цель игры всем известны.
1. Кратчайший путь. Поиск в ширину (Breadth-first search) Вики
Представим поле игры в виде графа. Каждая ячейка поля связана как минимум с 2-мя соседями. Таким образом, перебирая соседей можно найти ячейку с «едой». А после восстановить путь по которому мы до нее дошли.
Поиск в ширину — один из методов обхода графа. Заключается в том, что сначала рассматриваются все подчиненные узлы одного уровня, а после все подчиненные подчиненных и т.д. Под узлом понимается адрес ячейки со ссылкой на «Родителя» (ячейку через которую мы добрались до узла).
Примерный алгоритм действий:
- Создать пустой стек и поместить в него узел-источник
- Пока стек не пустой извлекать по одному узлу с вершины стека
- Проверить не является ли текущий узел целевым. Если да, то завершить поиск.
- Перебрать все подчиненные узлы, которые еще не были просмотрены. Добавить их в конец стека и пометить как просмотренные.
Алгоритм отлично работает до тех пор пока «хвост» змеи не начинает перекрывать кратчайший путь.
Серым цветом выделен рассчитанный путь.
2. Поиск в глубину (Depth-first search) Вики
Другой способ обхода графа, который ,как правило, будет приводить к более запутанному и сложному пути.
Поиск в глубину отличается тем, что сначала рассматриваются максимально далекие подчиненные текущего узла.
Отличие алгоритма от поиска в ширину будет минимальным: на шаге 2 берем узел не с вершины, а со дна стека.
3. Длиннейший путь
Если наша цель максимизировать количество очков, то можно удлинить путь к еде включая в него максимальное число соседних узлов.
Для этого получим кратчайший путь (поиском в ширину) и будем рассматривать каждые 2 узла пути. Если есть возможность, то включаем в путь 2 соседних.Повторяем упражнение пока расширение возможно.
Результат увеличился, тем не менее, хвост все еще продолжает мешать.
4. Гамильтонов цикл Вики
Гамильтонов цикл — замкнутый цикл, который проходит через каждую вершину графа по одному разу.
Если нас не волнует количество шагов, то можно посчитать длиннейший путь не к еде, а к хвосту. Т.к. длиннейший путь проходит по большинству ячеек поля, то еда будет съедена по пути, не зависимо от ее расположения.
В зависимости от расположения змеи могут образовываться недостижимые ячейки, поэтому, строго говоря, данный алгоритм не соответствует определению Гамильтонова цикла.
5. Гамильтонов цикл 2
Самый простой алгоритм из описанных, обладает 100% эффективностью и не требует никаких расчетов.
Подойдет для любого прямоугольного поля на котором нет препятствий.
Если нас действительно не волнует число шагов, то можно просто ходить по зацикленному пути:
Обработка протестирована на 8.3.12.1595, 8.3.12.1855
