CodinGame: я в золотой лиге
Вот и все, конкурс Code a la Mode на CodinGame закончился. Мне удалось совершить качественный скачок! Впервые поднялся в золотую лигу и существенно улучшил результат как в абсолютных, так и в относительных показателях. Итог — 326 место из 1548. Кроме этого, впервые применил алгоритм поиска вширь, а не вглубь, для построения пути. Почему-то раньше мне он казался намного более сложным, хотя потом оказалось, что реализуется он элементарно на основе банального списка, работающего в режиме очереди, без всяких рекурсий (видимо, сказались стереотипы, оставшиеся со времен изучения Pascal и C, где нужно было заниматься реализацией списков самостоятельно). Кроме этого, реализовал один относительно новый для себя подход, который прежде в этих конкурсах не использовал: построение своего рода «виртуальной программы».
Что любопытно, в этом конкурсе я участвовал как-то лениво. Самый первый «жесткий» алгоритм сделал только на третий день. Как это ни странно, его вполне хватило, чтобы подняться в «бронзу» до 24 места. Впрочем, если бы я его адаптировал для последнего типа заказов (TARTS), которые появились в бронзовой лиге, то вышел бы и в серебро.
А потом до четверга не было вообще никаких продвижений. В четверг более-менее серьезно засел за написание более «умного» кода, но только в субботу его закончил, и потом еще весь вечер ушел на отладку. Но сначала результат разочаровал: 42 место в бронзе, хуже, чем у «жесткого». После нескольких доработок удалось повысить позиции до первой десятки, но дальше — никак. Потом добавил одно упрощение: вместо анализа того, что есть на столах, код просто запоминал, куда он сбрасывал незаконченное блюдо, а потом забирал его обратно. И после этого произошел качественный скачок. Когда я сделал submit кода, он еще на 50% игр вышел на первое место (обычно это случается на последних 80-90%), я перешел в серебряную лигу и там тоже сразу оказался достаточно высоко: в районе 40-ой позиции (точно не помню). После некоторых мелких доработок удалось подняться на второе место, но вот бота серебряной лиги победить не получалось. Тут возник сложный выбор: либо довести до ума ту часть кода, которая анализирует столы с блюдами, либо сначала поэкспериментировать с алгоримтмом выбора заказов. Я выбрал второе и после небольших доделок все же прорвался в золотую лигу!
Но вот там алгоритм быстро уперся в предел своих возможностей: примерно 200-ая позиция. Я стал пытаться сделать некоторые мелкие усовершенствования, но эффект был незначителен, так как не понимал, за счет чего другие игроки проявляют себя лучше, что нужно добавить в алгоритм. Потом выявил один баг с расчетом дистанций, но и это помогло не сильно.
Было еще несколько идей, что можно сделать: рекурсивный поиск лучшего пути при разном порядке сбора компонентов вместо «жадного» алгоритма, который хватал то, что было ближе всего в данный момент, довести до ума тот самый алгоритм анализа столов, а также исправить ситуацию, когда мой персонаж берет блюдо, а потом снова ставит его на стол, так как для второго компонента тоже нужны свободные руки, но голова уже не соображала от слова совсем, сказывалась и эмоциональная перегрузка от прорыва, и поздняя ночь, и просто усталость. Поэтому я так и не стал их реализовывать, а взял ту версию, которая показала лучшие результаты, добавил туда пару мелких правок и сделал финальный submit где-то в районе 3:30. И первый раз за все время участия в конкурсах не сидел до последнего, а лег спать как обычно.
Еще тогда же, вечером, пришла в голову мысль, какой вообще должна быть идеальная тактика: один персонаж работает только верхней линии, другой — только на нижней, а все передачи компонентов идут через центральный стол. В этом случае значительно сокращается время на пробег вверх/вниз. Но как реализовать такое в случае, если поведение второго игрока непредсказуемо, пока за пределами моих возможностей.
Тем не менее, конкурсом я очень доволен! Жаль только, что самые интересные идеи пришли в голову слишком поздно. В принципе, их можно было бы реализовать, когда появится multiplayer-версия, но, скорее всего, к тому времени опять снесет потоком жизни, и будет не до этого… Все-таки конкурс своей ограниченностью во времени создает гораздо большую мотивацию, чем просто решение задачи в режиме multiplayerа. Отличный пример того, о чем я писал некоторое время о планах и дефиците времени.
Что любопытно, в этом конкурсе я участвовал как-то лениво. Самый первый «жесткий» алгоритм сделал только на третий день. Как это ни странно, его вполне хватило, чтобы подняться в «бронзу» до 24 места. Впрочем, если бы я его адаптировал для последнего типа заказов (TARTS), которые появились в бронзовой лиге, то вышел бы и в серебро.
А потом до четверга не было вообще никаких продвижений. В четверг более-менее серьезно засел за написание более «умного» кода, но только в субботу его закончил, и потом еще весь вечер ушел на отладку. Но сначала результат разочаровал: 42 место в бронзе, хуже, чем у «жесткого». После нескольких доработок удалось повысить позиции до первой десятки, но дальше — никак. Потом добавил одно упрощение: вместо анализа того, что есть на столах, код просто запоминал, куда он сбрасывал незаконченное блюдо, а потом забирал его обратно. И после этого произошел качественный скачок. Когда я сделал submit кода, он еще на 50% игр вышел на первое место (обычно это случается на последних 80-90%), я перешел в серебряную лигу и там тоже сразу оказался достаточно высоко: в районе 40-ой позиции (точно не помню). После некоторых мелких доработок удалось подняться на второе место, но вот бота серебряной лиги победить не получалось. Тут возник сложный выбор: либо довести до ума ту часть кода, которая анализирует столы с блюдами, либо сначала поэкспериментировать с алгоримтмом выбора заказов. Я выбрал второе и после небольших доделок все же прорвался в золотую лигу!
Но вот там алгоритм быстро уперся в предел своих возможностей: примерно 200-ая позиция. Я стал пытаться сделать некоторые мелкие усовершенствования, но эффект был незначителен, так как не понимал, за счет чего другие игроки проявляют себя лучше, что нужно добавить в алгоритм. Потом выявил один баг с расчетом дистанций, но и это помогло не сильно.
Было еще несколько идей, что можно сделать: рекурсивный поиск лучшего пути при разном порядке сбора компонентов вместо «жадного» алгоритма, который хватал то, что было ближе всего в данный момент, довести до ума тот самый алгоритм анализа столов, а также исправить ситуацию, когда мой персонаж берет блюдо, а потом снова ставит его на стол, так как для второго компонента тоже нужны свободные руки, но голова уже не соображала от слова совсем, сказывалась и эмоциональная перегрузка от прорыва, и поздняя ночь, и просто усталость. Поэтому я так и не стал их реализовывать, а взял ту версию, которая показала лучшие результаты, добавил туда пару мелких правок и сделал финальный submit где-то в районе 3:30. И первый раз за все время участия в конкурсах не сидел до последнего, а лег спать как обычно.
Еще тогда же, вечером, пришла в голову мысль, какой вообще должна быть идеальная тактика: один персонаж работает только верхней линии, другой — только на нижней, а все передачи компонентов идут через центральный стол. В этом случае значительно сокращается время на пробег вверх/вниз. Но как реализовать такое в случае, если поведение второго игрока непредсказуемо, пока за пределами моих возможностей.
Тем не менее, конкурсом я очень доволен! Жаль только, что самые интересные идеи пришли в голову слишком поздно. В принципе, их можно было бы реализовать, когда появится multiplayer-версия, но, скорее всего, к тому времени опять снесет потоком жизни, и будет не до этого… Все-таки конкурс своей ограниченностью во времени создает гораздо большую мотивацию, чем просто решение задачи в режиме multiplayerа. Отличный пример того, о чем я писал некоторое время о планах и дефиците времени.
https://vk.com/wall-176084509_21540