Есть серебряная лига на CodinGame!
И всё-таки я это сделал — прошёл в серебряную лигу в очередном соревновании в CodinGame. Изначально, учитывая то, что первые дни соревнования попали на поездку в Светлогорск, да и вообще образ жизни сейчас слишком уж хаотичный, я решил, что после возвращения выделю пару дней и выйду в бронзовую лигу и буду считать приемлемым результатом.
Но, как всегда, всё пошло не так. Во-первых, долго не мог начать. Во-вторых, в CodinGame в деревянных лигах, рассчитанных на совсем начинающих, раскрываются не все правила, а только самые основы игры. Поэтому прочитав упрощённые правила, я решил, что это игра на мультиагентную оптимизацию. Там нужно управлять троллями так, чтобы собрать как можно больше ресурсов — фруктов, которые периодически появляются на деревьях.
Я написал алгоритм, где каждый тролль был state machine, прошёл во вторую деревянную лигу, и тут обнаружилось, что всё не так, как я ожидал. Я думал, что на следующих уровнях будут просто давать нескольких троллей, плюс из некоторых моментов в описании можно было предположить, что появится возможность рубить деревья. Но всё оказалось сложнее. Во-первых, во второй лиге обнаружилась возможность сажать деревья в выбранных местах, во-вторых, оказалось, что изначально всегда даётся только один тролль, а остальных нужно порождать явно, тратя на это ресурсы. Причём каждая характеристика тролля зависит от определённого вида фруктов.
И тут я оказался перед сложным выбором: переписывать алгоритм полностью с учётом этих новых факторов или нет. С одной стороны, из-за всех этих переездов и недосыпов последних дней никак не получалось сесть и спокойно сосредоточиться, и я боялся не успеть сделать вообще ничего. С другой, имеющийся алгоритм был рассчитан на то, чтобы минимизировать время пробега до деревьев, и совершенно не учитывал их тип и потребности в тех или иных видах ресурсов, чтобы создать нового тролля.
Был момент, когда я даже думал, что так и застряну в деревянной лиге (что для меня было бы позором — лучше уж вообще не участвовать). Но потом оказалось, что во-первых, на старте игры даётся небольшой случайный набор ресурсов, дающий возможность создать одного или даже двух троллей. А во-вторых, в моём алгоритме нашлось несколько багов. Исправив их, я прорвался в бронзовую лигу, причём оказался где-то на 120 месте (тогда это было примерно 25% от начала).
Забегая вперёд, скажу, что алгоритм в целом был неплох, и его хватило, чтобы подняться до почти середины серебряной лиги. Но путь туда был непростой. Поднявшись в бронзу, я нашёл ещё один баг, а потом (вчерашней ночью) стал срочно дописывать алгоритм поиска пути в ширину. Сложного в нём ничего нет, но почему-то на обычном Pyhtonовском list он нормально не работал — зацикливался, пришлось прибегнуть к совету ИИ и заменить list на Deque из collections. После этого я оказался в первой десятке бронзовой лиги.
Всё утро думал, что делать дальше. Пытался играться с максимальным количеством троллей, скорректировал расчёт времени появления новых фруктов (при переходе в бронзу он усложнился), но без толку: прорваться в «серебро» никак не получалось. В какой-то момент даже хотел сдаваться, решив, что без переписывания уже ничего не сделать. К тому же у противников попались алгоритмы, которые в начале раунда просто аккуратно высаживали деревья всех типов возле вражеской базы, и потом собирали с них фрукты, не бегая через всю карту. И эти алгоритмы обходили мой в 3-4 раза! Я даже недоумевал, как они при этом остаются в бронзовой лиге.
Но потом решил реализовать свою начальную идею — создавать отдельного тролля-деструктивщика, который не собирает ресурсы, а бежит на вражескую базу и вырубает вокруг неё всё, до чего сможет дотянуться. И это сработало! Со второй попытки я оказался в серебряной лиге, причём не на последних местах, а поднялся чуть ниже её середины. Правда, сам момент перехода так и не увидел из-за того, что запустил расчёт и пошёл на сходку Tellы, о которой напишу отдельно. Обнаружил, что прорвался только задним числом, когда вернулся за компьютер. И ещё оказалось, что алгоритмы с посадками к наличию тролля-деструктивщика совершенно неустойчивы: они начинают тратить ресурсы на восстановление срубленных деревьев, но не не успевают вырасти, потому что их снова срубают, и такой алгоритм заканчивает игру с околонулевым результатом. Видимо, поэтому и остаются в «бронзе».
После всего этого я решил, что с меня достаточно — соревнование закончится завтра ранним утром, в «золото» я уже точно не прорвусь (для этого нужно переписывать алгоритм полностью), а проводить ещё одну бессонную ночь ради попыток улучшить результат на несколько десятков позиций нет ни сил, ни желания.
Но тем не менее, очень доволен тем, что после долгого перерыва снова принял участие в CodinGame! В первый момент было ощущение, что «мозги скрипят», т.е. соображаю с трудом, но потом, что называется, вработался. Ещё удивительным открытием стало то, что до серебряной лиги можно дойти даже на алгоритме, который не учитывает чуть ли не половину второстепенных игровых факторов (например, расположение деревьев около воды, что ускоряет рост, возможность добывать железо вместо фруктов, дефицит тех или иных видов ресурсов в данный момент, действия противника). А ещё снова убедился, что нужно не только читать условие, но и запускать ту заглушку кода, которая даётся в начале игры, чтобы лучше понять игровую механику, а потом — писать максимально примитивный код, который может решить задачу хоть как-то. Его обычно хватает, чтобы пройти до бронзы. А уже там, видя полную картину со всеми правилами, придумывать нормальный алгоритм. Что ж, будем надеяться, что учту это в следующей игре!
И ещё одним открытием для меня стало то, что в условиях соревнований сочетание фокуса на одной задаче с дефицитностью времени меня реально мотивирует. Поясню, что на CodinGame можно писать код для нескольких десятков подобных игр и вне соревнований, но обычно бывает так: в условиях свободного выбора я смотрю на список игр, думаю «этим как-то не хочется заниматься, тем — тоже», и в итоге не делаю вообще ничего. А когда выбирать не надо, потому что всё внимание сфокусировано на игре, по которой идут соревнования, такой проблемы не возникает. Эх, надо бы как-нибудь научиться это и в своих делах применять!