Будьте ленивы и держите это простым

  1. Легенда о Ленивых
  2. суббота
  3. Воскресенье
  4. понедельник
  5. вторник
  6. среда
  7. Четверг
  8. пятница

CodinGame провела конкурс кодирования «Фантастические звери» в ноябре 2016 года. Сейчас игра доступно для игры ,

Легенда о Ленивых

Любой, кто обсуждал со мной какое-то время в чате, должен был узнать печальную правду обо мне: я ленивый . Я тоже не очень амбициозен. Итак, во время соревнований по кодированию я обычно хочу две вещи:

  1. Получить достойное звание
    Не обязательно великолепно, но, по крайней мере, достигнет Лиги Легенд или 100 лучших игроков. Все, что выше этого, было бы приятным сюрпризом, но я, вероятно, не упущу из-за этого.
  2. Потратьте как можно меньше времени
    Помимо того, что я профессиональный разработчик, у меня есть семейная жизнь, которую я хотел бы сохранить. Таким образом, количество времени, которое я могу перевести на CodinGame, относительно ограничено.

Последнее является причиной, по которой я не пробую генетические алгоритмы, Монте-Карло или что-то в этом роде, даже если у меня достаточно опыта и опыта для этого. Я действительно написал небольшой генетический алгоритм еще на втором курсе инженерной школы 20 лет назад ...

Итак, что мне осталось? Эвристика, простые идеи, более или менее грубые приближения. Они не дадут идеальных результатов, иногда они могут даже ужасно потерпеть неудачу, но дело в том, что они будут работать достаточно хорошо для того, чего я хочу достичь .

Еще одно преимущество эвристики заключается в том, что, поскольку я не собираюсь моделировать весь игровой движок, меня не волнуют проблемы с производительностью, поэтому я могу использовать все высокоуровневые помощники моего языка (контейнеры, алгоритмы сортировки и поиска и т. Д.) который в противном случае может быть слишком неэффективным для быстрого моделирования. Это помогает быстро и ясно выражать простые идеи в моем коде.

Вот мои основные ключи к лени:

  1. Работайте с очень простыми идеями. Избегайте редких ситуаций и сосредоточьтесь на самых частых.
  2. Реализуйте только одну идею за раз. Завершите его, прежде чем переходить к другому, и всегда оставляйте текущее задание в готовом рабочем состоянии.
  3. Кодируйте немного, но кодируйте немного каждый день конкурса, чтобы быть в курсе событий; немного легче поддерживать хорошее звание, которое вы получаете на раннем этапе, чем восстановить его, когда есть много игроков.
  4. Делай как можно меньше. Начните рефакторинг или расширение дизайна только тогда, когда это необходимо для текущей идеи.
  5. Не беспокойтесь о времени выполнения или использовании памяти. Я могу позволить себе раздутые структуры данных и неэффективный дизайн, если он выполняет свою работу быстро.
  6. Тусоваться в чате, обсуждать идеи с другими. Вы можете получить очень хороший совет за очень небольшую плату.

По общему признанию, ключи # 4 и # 5 рискуют оставить вас с довольно уродливым кодом. Опыт поможет вам лучше их применять и в то же время поддерживать ваш код в приемлемом состоянии.

В качестве иллюстрации, вот краткий обзор того, как прошел мой конкурс Fantastic Bits.

суббота

Перво-наперво, я пишу небольшую структуру данных, чтобы сохранить весь ввод и любую другую информацию, которая мне понадобится. В соответствии с ключом № 5 я просто собираю все вместе в единую структуру и использую только необходимые биты в зависимости от контекста, игнорируя остальное - один размер подходит всем. Аналогично, я составляю единый глобальный список объектов, к которым я могу обращаться из любого места кода.

Теперь ключ № 1 предлагает два очень простых действия: если у игрока есть snaffle, он должен попытаться забить, а если нет, он должен попытаться получить его как можно быстрее. И это все. Я вообще не рассматриваю оппонентов или то, что мои игроки могут быть нацелены на тот же самый снаффл. Позже будет достаточно времени, чтобы добавить сложность, если первоначальная идея не работает достаточно хорошо. Итак, вот псевдокод для этих основных идей.

для каждого выполненного игрока = ложь, если у игрока есть бросок снаффла в центр цели при максимальной мощности, выполненной = истина, если не выполнено, найдите ближайший к игроку снаффл, переместитесь на позицию снаффла при максимальной тяге

Опытные игроки сразу увидят, насколько это неточно. Однако он достаточно точен, чтобы немедленно победить босса Лиги Вуд 2. Также обратите внимание, что «найти ближайшего к игроку игрока» немного больше, чем то, что вы можете найти в самых первых сольных головоломках CodinGame, таких как Спуск определенно не высокое волшебство.

Вуд 1 Лига вводит бладжеров. В соответствии с ключом № 3, я решил просто игнорировать их, пока они не станут неприятностью. Все, что я добавляю, - это проверка в моем поиске snaffle для части MOVE, чтобы убедиться, что я проверяю только сущности snaffle. Этого достаточно, чтобы перейти в Бронзу. На данный момент я закодировал не более 20 минут.

Воскресенье

Переходя к использованию заклинаний. Ленивый ключ № 2 говорит, что нужно начинать с одного заклинания. Ленивый ключ # 1 заставляет меня отказаться от Obliviate (так как я игнорирую бладжеры и другие столкновения), Petrificus (не вписывается в мою нынешнюю логику партитуры или погони) и Flipendo (кажется, что для получения права может потребоваться некоторая математика) ). Поэтому я иду на Accio и использую его, чтобы украсть оскорбления у противника.

Я предполагаю, что противник также собирается преследовать ближайший к нему осколок. Я даже решаю сопоставить противоположных игроков, поэтому у меня есть только один противник, вместо того, чтобы проверять обоих. Конечно, есть некоторая минимальная работа: «snaffle, ближайший к игроку», становится факторизованной функцией. Я также добавляю небольшие элементы бухгалтерского учета, такие как счетчики маны и заклинаний, а также «целевой» флаг в структуре сущностей, чтобы гарантировать, что каждый волшебник будет обрабатывать разные блоки.

для каждого выполненного игрока = false, если игрок имеет бросок в центр цели с максимальной силой выполнено = true, если не выполнено, и мана> = 20, и игрок не получил асьо в течение последних 6 ходов, а точнее - ближайший к «соответствующему» противнику (0 <-> 2, 1 <-> 3) мана - = 20 выполнено = true, если не выполнено, найдите ближайший к игроку снафф, переместитесь в положение снаффла при максимальной тяге

Это новое представление идет прямо в топ-100 бронзы. Меньше часа кода пока.

понедельник

Мой бот потерял сотни мест за одну ночь. Утром я просто немного подправил свой текущий код, заменив «матч» оппонента реальным циклом над оппонентами и сохранив целевой ориентир, ближайший к моему игроку (10 минут).

Днем я начну с некоторого быстрого рефакторинга, заменив мой код «найди ближайшего игрока» фактической сортировкой всего списка игроков по расстоянию до игрока (эй, помни Конные скачки ?). Теперь я могу реализовать базовое использование Flipendo: начиная с ближайшего объекта, я проверяю, может ли его выстрел попасть в цель, и, если это невозможно, я проверяю следующий и так далее.

Ключ № 1: Это делается с очень простой проверкой выравнивания. Является ли ссора между мной и целью? Линия между мной и Снаффлом проходит между стойками ворот? Вычисление линии - математика для средней школы, или ее можно легко найти. Все еще ничего сложного.

для каждого игрока выполнено = ложь [код броска], если не выполнено, и мана> = 20, и игрок не бросал флиппо в течение последних 3 ходов для каждого snaffle (в порядке увеличения расстояния от игрока), если snaffle не находится между игроком и целью, продолжайте вычислительную линию между игроком и snaffle, если линия пересекает линию ворот между сообщениями flipendo snaffle mana = mana - 20 done = true break [новый код accio] [код движения]

Что касается другой начальной эвристики, этот код Flipendo очень грубый и не проверяет возможные препятствия, не учитывает радиус или скорость объектов и т. Д. Тем не менее, он оказывается достаточно хорошим для большинства случаев выравнивания, и это подача достигает около # 70 до открытия Silver.

Тем не менее, он оказывается достаточно хорошим для большинства случаев выравнивания, и это подача достигает около # 70 до открытия Silver

Пример Флипендо

Ключ № 6: В тот вечер в чате Gadzy.fr упоминает, что носили снафл, наследуют скорость волшебника. Эта скорость добавляется к вектору броска, чтобы вычислить следующую позицию snaffle, поэтому ее следует вычитать из цели при броске, чтобы убедиться, что цель является центром цели. Хотя на самом деле мне это не нужно, эта дополнительная точность достигается практически бесплатно, так что попытка не повредит.

бросить в центр цели на максимальной мощности

становится

бросок к центру цели за вычетом скорости, на максимальной мощности

На самом деле, это простое изменение дает мне право попасть в топ-20 Silver, что составляет в общей сложности менее 90 минут кода.

вторник

Мой бот все еще стоит на твердом месте № 24 по утрам, намного выше, чем я ожидал. Это определенно золотой материал, по крайней мере, поэтому мое единственное изменение в этот день происходит по тем же линиям, что и накануне вечером: 5-секундное изменение, учитывающее скорость перемещения при движении, так что волшебник нацелится туда, где будет находиться объект. а не где это:

переместиться в положение снаффла с максимальной тягой

в свою очередь становится:

двигаться в положение снаффла плюс скорость при максимальной тяге

Это также, где начинает проявляться нестабильность в процессе ранжирования, так как теперь в середине доски находится большой буфер схожих ИИ. Два последовательных представления одного и того же кода могут заканчиваться где-то между 50 и менее 200, поэтому теперь необходимо несколько предложений для оценки действительности любого изменения или восстановления ранга, аналогичного предыдущему.

среда

Этот день обычно для меня работа и семья, поэтому ничего особенного не произойдет до открытия Gold, когда я все еще вхожу в топ-50.

Четверг

Я до сих пор около 70 в Золоте по утрам. По опыту этого может быть недостаточно для продвижения в Legend. Я хотел бы получить по крайней мере рейтинг 50 лучших перед открытием лиги.

Я расширяю свой код Flipendo, чтобы добавить подпрыгивание от верхней и нижней стенок. Это немного сложнее, но не намного. Убедитесь, что линия игрока-перехватчика пересекает верхнюю или нижнюю стенки, прежде чем достигнуть левой или правой стен. Инвертировать вертикальный компонент линии. Проверьте, проходит ли эта новая линия, начиная с этой точки пересечения, цель. Как и в случае с другими моими эвристиками, это не учитывает радиус сущности, но все же дает хорошие результаты, хотя я иногда получаю впечатляющие отскоки от ворот цели.

Я также добавляю Петрификуса к осколкам, которые выглядят так, будто они собираются забить против меня. Все еще просто и приблизительно: переместите snaffle на его текущую скорость и трение за 3 оборота, и проверьте окончательное положение.

для каждого игрока сделано = ложь [код броска] [код флипендо, теперь с отскоками] [код АЧИО], если не выполнено, и мана> = 10 для каждого snaffle (упорядочено по увеличению расстояния от моей собственной цели), то snaffle собирается забить Петрификус мана = мана - 10 перерывов [код движения] для каждого игрока сделано = ложь [код броска] [код флипендо, теперь с отскоками] [код АЧИО], если не выполнено, и мана> = 10 для каждого snaffle (упорядочено по увеличению расстояния от моей собственной цели), то snaffle собирается забить Петрификус мана = мана - 10 перерывов [код движения]

Пример Петрифика

Сейчас все определенно сложнее, и все больше игроков продолжают приходить в золото. Несколько последовательных представлений (и, возможно, несколько удачных победных полос) необходимы, прежде чем я в конечном итоге вернусь в топ-100. Тем не менее, не более двух часов кода.

пятница

Это день, когда мне нужно занять место в топ-50, но сейчас я на # 130. У меня нет времени на полный пересмотр или придумывание совершенно новых, изменяющих игру идей, поэтому я стараюсь избавиться от некоторых худших приближений по разумной цене.

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

Время для простого рефакторинга: вместо того, чтобы выводить команды сразу для каждого игрока по очереди, я теперь сохраняю командную строку в структуре своей сущности и выводю все команды в одном пакете в конце хода. Это позволяет мне инвертировать общую структуру моего алгоритма, проталкивая цикл внешнего игрока внутри каждого блока действий. Вместо

для каждого игрока сделано = ложь [код броска] [код флипендо] [код асьо] [код петрификуса] [код хода]

Теперь у меня есть

[бросить код для обоих игроков] [код flipendo для обоих игроков] [код accio для обоих игроков] [код petrificus для обоих игроков] [код хода для обоих игроков] выходные команды

Теперь для каждого из блоков Flipendo, Accio и Move я проверяю возможности обоих игроков, назначаю команду лучшему и повторяю, пока у обоих игроков не будет чего-то делать, или пока не будут выполнены какие-либо интересные действия.

Например, для Flipendo я реорганизую существующую проверку «прямая линия или отскок» в отдельной функции для получения «наилучшего кандидата сальто», и соответствующий код блока теперь выглядит следующим образом:

в то время как мана> = 20 и по крайней мере один игрок не имеет назначенной команды, собирать лучших кандидатов в флипендо для каждого игрока, у которого еще нет команды и нет флипендо в течение последних 3 ходов, если нет кандидатов на перерыв, назначьте команду флипендо игроку, ближайшему к его целевой мане = мана - 20

При этом заклинания кажутся немного более эффективными, мои игроки оказываются на пути друг друга гораздо реже, и мне удается вернуться немного ниже # 100 - все еще недостаточно хорошо. Посмотрев еще несколько реплеев, где я проигрываю против игроков с более низким рейтингом (это довольно вредно в начале процесса ранжирования), я получаю еще пару идей, которые можно легко и быстро исправить.

Во-первых, мой код движения всегда предполагает, что снаффл будет продолжать двигаться в своем текущем направлении, но это определенно неправильно, когда противник переносит снаффл. Предполагая, что в таком случае противник будет бросать стрелу прямо в мою цель, и, соответственно, компенсируя свою цель, я должен лучше перехватывать броски противника.

Второй заключается в том, что большинство ИИ нацелены на середину цели, поэтому игроки, как правило, сталкиваются с центральной частью поля и бросают осколки друг в друга. Поэтому я стараюсь бросать в несколько разных местах, в зависимости от того, где мой игрок расположен вертикально.

Будучи немного ограниченным временем, я не пытаюсь оценивать эти последние изменения отдельно, а просто представляю одну версию с этими двумя изменениями, связанными вместе. Моя вторая заявка заканчивает свой рейтинг на # 25, менее чем через 4 часа после открытия Лиги Легенд. Вероятно, это произошло из-за довольно удачной серии побед, и она медленно стекала в течение дня. Когда открывается Лига Легенд, я все еще в топ-50, чуть выше точки входа в Bossdemort.

После этого у меня не было времени на соревнования в выходные, в то время как другие игроки продолжали улучшать свой код, и я наконец-то занял 137 место из 156 игроков в Легендарной лиге и 2399 игроков в целом.

Каким бы несовершенным и неточным он ни был, этот довольно простой и быстро написанный код (4 часа в неделю, это всего 30 минут в день) все же смог получить достаточно хороший рейтинг и, по крайней мере, попасть в Legend… не бойся, ты можешь сделать то же самое в следующий раз!

В заключение отметим, что это может быть даже возможностью выучить один из менее распространенных языков. У вас может даже быть реальный шанс закончить сначала для этого языка!

Играть в фантастические звери

Итак, что мне осталось?
Является ли ссора между мной и целью?
Линия между мной и Снаффлом проходит между стойками ворот?