Code of Ctulu: мои итоги очередного конкурса
В течение этого заезда на дачу почти все время я активно занимался программированием. Сначала я реализовал одну свою давнюю идею, о которой более подробно напишу через пару дней. А в среду зашел на CodinGame и увидел, что там идет очередной конкурс. Хотя к тому времени прошла уже половина отведенного времени (конкурсы длятся по десять дней обычно), я все же решил попробовать участвовать. Не столько даже ради рейтинга, сколько ради опыта.
Конкурс назывался Code of Ktulu. Сюжет задачи, которую предстояло решить, был такой: четверо исследователей проникли в лабиринт Ктулху и потревожили его сон. Ктулху стал посылать против них своих прислужников, вызывающих ужас и постепенно сводящих с ума. Цель заключалась в том, чтобы управляя одним из исследователей, продержаться дольше остальных. Но каких-либо способов активной борьбы с монстрами не предусмотрено, поэтому нужно было придумать алгоритм, который позволял как можно дольше убегать по лабиринту. При этом здоровье (точнее, величина, называемая sanity) там понемногу убывает при каждом ходе, но если держаться группой, то медленее, чем по одиночке.
На первый взгляд кажется, что решать такую задачу нужно с помощью алгоритмов, аналогичных шахматным: просчитывать возможные варианты развития событий на несколько ходов вперед, отсекая заведомо бесперспективные варианты, и затем выбирать лучший. И начал писать код. Но прежде я никогда ничем подобным не занимался, равно как и алгоритмами поиска путей в лабиринтах, поэтому на продумывание и написание программы ушло два дня. Только к пятнице я получил нечто законченное. Зашел на сайт, запустил, и вдруг обнаружил, что мой персонаж без видимых причин дохнет через несколько ходов. Сначала не мог понять, что происходит. Потом выяснилось, что там очень жесткие ограничения на время, за которое программа должна произвести расчет и дать ответ: секунда для первого хода и по 50 мс на все последующие. И мой алгоримт в это время просто не укладывался. Я попытался переделать расчеты так, чтобы они использовали библиотеку NumPY, в надежде, что это ускорит работу, но эффект был незначительный. В какой-то момент я заметался, не зная, что делать, так как перекладывать написанный алгоритм на C, Go или какой-то еще компилируемый язык не хотелось (да и не факт, что это помогло бы). Потом решил действовать иначе: сел и быстро, буквально за 15 минут, набросал другую программу, которая была гораздо примитивнее: она находила ближайшего монстра и строила маршрут, который позволял его обойти по самой длинной траектории.
Как это ни странно, такой простенькой программы хватило для того, чтобы сразу же проскочить все три «дубовые» лиги (Wooden league), и подняться примерно на сотое место из 280 в бронзовой. Но на этом его возможности были исчерпаны: при переходе в следующую лигу меняются правила, в частности, появился новый вид монстров с другим способом атаки, против которых этот алгоритм оказался неэффективен.
Что делать дальше, было непонятно. Но потом я вспомнил, как для другой игры использовал подход, который называю «гравитационным»: каждому объекту приписывается некое числовое значение, характеризующее желательность взаимодействия с ним, которое уменьшается с расстоянием, а дальше считается сумма воздействий на точку, где находится игрок, от всех объектов и происходит движение по градиенту. За субботу и начало воскресенья я сделал такой алгоритм. Но увы, когда запустил, ждало разочарование: сначала алгоритм показал даже худшие результаты, чем предыдущий — 170 место во все той же бронзовой лиге. Я стал разбираться, в чем дело. Обнаружил несколько глупых багов (например, путаницу координат x и y), а также то, что в пограничных ситуациях мой персонаж начинает метаться из стороны в сторону. Я там делал так, что выбор, куда идти, зависел от того, где находится ближайший монстр: если далеко, то идти к ближайшему глобальному максимум на карте, если ближе — искать локальный максимум в окрестности заданного размера (или величину, которая меньше него на значение не более N, но при этом находится ближе), если совсем близко — то выбирать клетку с наибольшим значением для следующего хода. Оказалось, что метания вызваны тем, что средний и последний варианты дают противоречивые результаты.
Где-то к 23 часам воскресенья я со всем этим более-менее разобрался. И вот после одного из запусков режима тестирования «все против всех в данной лиге», наступил момент когда мой алгоритм поднялся вроде бы на первое место, но увы, не удержался там, и когда все бои завершились, откатился где-то к первой десятке. Я начал играться с настройками некоторых параметров (например, радиусов, где применяются разные способы принятия решения), пытаться добавить мелкие доработки, но становилось только хуже: из первой десятки стал падать в первую сотню. Где-то часам к четырем я откатил все изменения, поизучал ситуации, в которых этот алгоритм проигрывает, и понял, что иногда он принимает решение идти «на таран» на монстра тогда, когда в этом нет никакой необходимости. Думать, как это исправить на уровне алгоритма, уже не было времени (конкурс заканчивался в 11 утра в понедельник), поэтому поступил так: взял тот предыдущий алгоритм избегания противника, и стал использовать его в тех случаях, когда у моего персонажа есть куда отступать (то есть нет окружения со всех сторон). Результаты улучшились: я стал устойчиво попадать на второе место в своей лиге. Но на первом месте там стоит бот, сделаный самими разработчиками игры, а условием прохода в следующую лигу являтся именно победа над ним. А вот этого никак и не получалось.
Каких-либо идей, что еще можно добработать за оставшиеся несколько часов, не было. Все, что оставалось делать — это играться с несколькими глобальными параметрами, например, радиусами, от которых зависит способ принятия решения или коэффициентом, который влиял на то, насколько алгоритму будет важно находиться рядом с другими игроками. Но увы, каждая проверка кода в режиме «все против всех» занимает достаточно большой промежуток времени (порядка 5—10 минут в зависимости от загруженности сервера). И где-то часам к шести я начал приходить к выводу, что все бесполезно, и уже собирался было идти спать. Но постоянно говорил себе «сейчас попробую еще вот такое сочетание показателей, и пойду». Но потом хотелось проверить другое сочетание, за ним еще одно, и так длилось примерно до 8 часов утра. Тогда, запустив в очередной раз просчет, я почти сразу обратил внимание, что результаты на этот раз вроде бы лучше: подъем в таблице идет быстрее. Когда было посчитано около 70% всех игр, я оказался на первом месте. Но такое случалось уже не первый раз, и я знал, что это бывает обманчиво. Так и вышло: когда расчет дошел где-то до 84-85%, я снова сполз на второе. В районе 90% снова началась серия побед, снова — первое место, но было понятно, что оно очень и очень непрочно. И вот до окончания расчетов оставалось всего 4 игры. Две из них заканчиваются поражениями (причем по-моему, на четвертом месте). Я ожидаю, что вот-вот в любую минуту упаду на вторую строчку таблицы, но нет, все еще первый. И остается еще две игры. И обе заканчиваются полной победой! Есть, есть серебрянная лига!
Дальше я дождался, когда определится моя позиция в серебряной лиге. В ней я казался примерно 230 место из примерно 570. На этом я и решил закончить, пойти отсыпаться и приходить в себя.
В общем, впечатление о конкурсе у меня двоякое. С одной стороны, это интересно, и заставляет пробовать новое и лучше изучать то, что уже знаю (так, например, сейчас бы я совершенно иначе сделал алгоритм расчета пути по лабиринту, и, скорее всего, не имел бы проблем с таймаутом), с другой — слишком уж затратно в эмоциональном и физическом плане. Кроме того, когда я занят конкурсом, начинают вставать другие дела (тот же freelance), что тоже несколько напрягает. Кроме того, я чуть было из-за этого конкурса не пропустил очередные задания КСИ. Еще прихожу к выводу, что мне имеет смысл поучаствовать в Clash of Code — программировании небольших задач на скорость на том же CodinGame, чтобы приучить себя не думать долго при написании кода и реже лазить в справочники по стандартным функциям, больше полагаться на свою память.
Конкурс назывался Code of Ktulu. Сюжет задачи, которую предстояло решить, был такой: четверо исследователей проникли в лабиринт Ктулху и потревожили его сон. Ктулху стал посылать против них своих прислужников, вызывающих ужас и постепенно сводящих с ума. Цель заключалась в том, чтобы управляя одним из исследователей, продержаться дольше остальных. Но каких-либо способов активной борьбы с монстрами не предусмотрено, поэтому нужно было придумать алгоритм, который позволял как можно дольше убегать по лабиринту. При этом здоровье (точнее, величина, называемая sanity) там понемногу убывает при каждом ходе, но если держаться группой, то медленее, чем по одиночке.
На первый взгляд кажется, что решать такую задачу нужно с помощью алгоритмов, аналогичных шахматным: просчитывать возможные варианты развития событий на несколько ходов вперед, отсекая заведомо бесперспективные варианты, и затем выбирать лучший. И начал писать код. Но прежде я никогда ничем подобным не занимался, равно как и алгоритмами поиска путей в лабиринтах, поэтому на продумывание и написание программы ушло два дня. Только к пятнице я получил нечто законченное. Зашел на сайт, запустил, и вдруг обнаружил, что мой персонаж без видимых причин дохнет через несколько ходов. Сначала не мог понять, что происходит. Потом выяснилось, что там очень жесткие ограничения на время, за которое программа должна произвести расчет и дать ответ: секунда для первого хода и по 50 мс на все последующие. И мой алгоримт в это время просто не укладывался. Я попытался переделать расчеты так, чтобы они использовали библиотеку NumPY, в надежде, что это ускорит работу, но эффект был незначительный. В какой-то момент я заметался, не зная, что делать, так как перекладывать написанный алгоритм на C, Go или какой-то еще компилируемый язык не хотелось (да и не факт, что это помогло бы). Потом решил действовать иначе: сел и быстро, буквально за 15 минут, набросал другую программу, которая была гораздо примитивнее: она находила ближайшего монстра и строила маршрут, который позволял его обойти по самой длинной траектории.
Как это ни странно, такой простенькой программы хватило для того, чтобы сразу же проскочить все три «дубовые» лиги (Wooden league), и подняться примерно на сотое место из 280 в бронзовой. Но на этом его возможности были исчерпаны: при переходе в следующую лигу меняются правила, в частности, появился новый вид монстров с другим способом атаки, против которых этот алгоритм оказался неэффективен.
Что делать дальше, было непонятно. Но потом я вспомнил, как для другой игры использовал подход, который называю «гравитационным»: каждому объекту приписывается некое числовое значение, характеризующее желательность взаимодействия с ним, которое уменьшается с расстоянием, а дальше считается сумма воздействий на точку, где находится игрок, от всех объектов и происходит движение по градиенту. За субботу и начало воскресенья я сделал такой алгоритм. Но увы, когда запустил, ждало разочарование: сначала алгоритм показал даже худшие результаты, чем предыдущий — 170 место во все той же бронзовой лиге. Я стал разбираться, в чем дело. Обнаружил несколько глупых багов (например, путаницу координат x и y), а также то, что в пограничных ситуациях мой персонаж начинает метаться из стороны в сторону. Я там делал так, что выбор, куда идти, зависел от того, где находится ближайший монстр: если далеко, то идти к ближайшему глобальному максимум на карте, если ближе — искать локальный максимум в окрестности заданного размера (или величину, которая меньше него на значение не более N, но при этом находится ближе), если совсем близко — то выбирать клетку с наибольшим значением для следующего хода. Оказалось, что метания вызваны тем, что средний и последний варианты дают противоречивые результаты.
Где-то к 23 часам воскресенья я со всем этим более-менее разобрался. И вот после одного из запусков режима тестирования «все против всех в данной лиге», наступил момент когда мой алгоритм поднялся вроде бы на первое место, но увы, не удержался там, и когда все бои завершились, откатился где-то к первой десятке. Я начал играться с настройками некоторых параметров (например, радиусов, где применяются разные способы принятия решения), пытаться добавить мелкие доработки, но становилось только хуже: из первой десятки стал падать в первую сотню. Где-то часам к четырем я откатил все изменения, поизучал ситуации, в которых этот алгоритм проигрывает, и понял, что иногда он принимает решение идти «на таран» на монстра тогда, когда в этом нет никакой необходимости. Думать, как это исправить на уровне алгоритма, уже не было времени (конкурс заканчивался в 11 утра в понедельник), поэтому поступил так: взял тот предыдущий алгоритм избегания противника, и стал использовать его в тех случаях, когда у моего персонажа есть куда отступать (то есть нет окружения со всех сторон). Результаты улучшились: я стал устойчиво попадать на второе место в своей лиге. Но на первом месте там стоит бот, сделаный самими разработчиками игры, а условием прохода в следующую лигу являтся именно победа над ним. А вот этого никак и не получалось.
Каких-либо идей, что еще можно добработать за оставшиеся несколько часов, не было. Все, что оставалось делать — это играться с несколькими глобальными параметрами, например, радиусами, от которых зависит способ принятия решения или коэффициентом, который влиял на то, насколько алгоритму будет важно находиться рядом с другими игроками. Но увы, каждая проверка кода в режиме «все против всех» занимает достаточно большой промежуток времени (порядка 5—10 минут в зависимости от загруженности сервера). И где-то часам к шести я начал приходить к выводу, что все бесполезно, и уже собирался было идти спать. Но постоянно говорил себе «сейчас попробую еще вот такое сочетание показателей, и пойду». Но потом хотелось проверить другое сочетание, за ним еще одно, и так длилось примерно до 8 часов утра. Тогда, запустив в очередной раз просчет, я почти сразу обратил внимание, что результаты на этот раз вроде бы лучше: подъем в таблице идет быстрее. Когда было посчитано около 70% всех игр, я оказался на первом месте. Но такое случалось уже не первый раз, и я знал, что это бывает обманчиво. Так и вышло: когда расчет дошел где-то до 84-85%, я снова сполз на второе. В районе 90% снова началась серия побед, снова — первое место, но было понятно, что оно очень и очень непрочно. И вот до окончания расчетов оставалось всего 4 игры. Две из них заканчиваются поражениями (причем по-моему, на четвертом месте). Я ожидаю, что вот-вот в любую минуту упаду на вторую строчку таблицы, но нет, все еще первый. И остается еще две игры. И обе заканчиваются полной победой! Есть, есть серебрянная лига!
Дальше я дождался, когда определится моя позиция в серебряной лиге. В ней я казался примерно 230 место из примерно 570. На этом я и решил закончить, пойти отсыпаться и приходить в себя.
В общем, впечатление о конкурсе у меня двоякое. С одной стороны, это интересно, и заставляет пробовать новое и лучше изучать то, что уже знаю (так, например, сейчас бы я совершенно иначе сделал алгоритм расчета пути по лабиринту, и, скорее всего, не имел бы проблем с таймаутом), с другой — слишком уж затратно в эмоциональном и физическом плане. Кроме того, когда я занят конкурсом, начинают вставать другие дела (тот же freelance), что тоже несколько напрягает. Кроме того, я чуть было из-за этого конкурса не пропустил очередные задания КСИ. Еще прихожу к выводу, что мне имеет смысл поучаствовать в Clash of Code — программировании небольших задач на скорость на том же CodinGame, чтобы приучить себя не думать долго при написании кода и реже лазить в справочники по стандартным функциям, больше полагаться на свою память.