Лог жизни

Видимо, пришла пора признать, что на CodinGame я сделал всё, что мог, и пора возвращаться к работе над MLFW. Тем более, что сегодня познакомился с человеком, который заинтересовался моей идеей делать движок сообщества.
По соревнованию задача-минимум выполнена: в серебряную лигу я прошёл совершенно без проблем. До "золота", видимо, уже не дойду: сейчас болтаюсь в районе 130 места в серебряной лиге (и где-то 430 в общем зачёте), и нет никаких новых идей в плане улучшения уже имеющегося алгоритма или новых стратегий. Правда, там как-то странно работает подсчёт: если долго не отправлять новые версии алгоритма, то позиция постепенно может немного вырасти. Но вряд ли этого хватит для прохождения в «золото».
Так что по сути, самое главное качественное улучшение — это я стал писать код для игр быстрее. Тот алгоритм, который дал мне этот результат, сделал за три дня, а не сидел все десять, как раньше. Потом только экспериментировал с другими стратегиями, оказавшимися менее удачными, и незначительно доработал его вчера, улучшив игру с несколькими базами.
Но в любом случае, самое главное я получил: удовольствие от решения интересной задачи!

Сегодня на CodinGame придумал и реализовал уже пятую по счёту стратегию игры. Она получилась эффективнее, чем две предыдущих, (и при этом сам алгоритм очень прост и красив). Но когда я провёл испытания в противостоянии с боссом серебряной лиги, оказалось, что она проигрывает ему гораздо чаще, чем вторая: 3:9 против 6:6. Но если сыграть против своего же кода разными стратегиями, то, наоборот, пятая чаще выигрывает с минимальным перевесом.
Конечно, главным показателем должна стать эффективность против всех игроков вообще. Но проблема в том, что её сложно померить: разбросы огромные. Вчера, например, днём поднялся до примерно 360 места, а вечером тот же код оставался на 700—800 позициях. Я тогда решил, что откатился из-за того, что за день другие игроки так сильно улучшили код. Но утром следующего дня тот же самый алгоритм оказался на 296 месте! Как говорится, и как тут оценить эффективность… Ещё есть подозрение, что иногда глючит сам CodinGame, так как периодически начинает выдавать сообщение, что моя программа не дала результат за отведённое время. Хотя если страницу обновить и перезапустить игру в том же режиме, всё срабатывает как надо. Возможно, просто не хватает памяти для запуска интерпретатора Python. Эх, сесть что ли и переписать самую удачную стратегию на PHP? Заодно и результат в пределах конкретного языка улучшу (на PHP выше меня в рейтинге около десятка человек), это тоже влияет на итоговые очки.
Ещё есть мысль сделать гибридный алгоритм. Я заметил, что пятая стратегия хорошо играет на очень маленьких картах. Соответственно на них использовать её, на более больших — модифицированный вариант второго. Но всё опять упирается в проверку эффективности…

Вчера зарегистрировался на новом конкурсе CodinGame. Долго не мог определиться, стоит ли ради него отвлекаться от разработки MLFW. С одной стороны, раз отвлёкшись, сложно вернуться. С другой — сейчас всё равно период, когда плохо представляю, что именно делать дальше. В итоге решил сделать то же, что и в 2021 году: выйти хотя бы в серебряную лигу, а дальше — как пойдёт, но не устраивать себе бессонных ночей с одержимостью, как это было в 2018—2019 годах.
Но вчера день оказался какой-то неэффективный: кое-как вник в условия конкурса, но не написал ни одной строчки кода. Занялся этим только сегодня, и то как-то весьма неспешно. Но зато понял, что изучение алгоритмов зря не прошло: сам подход существенно поменялся. Хотя и сама конкурсная задача тоже стала сложнее. Раньше я в бронзовую лигу выходил легко (однажды даже написал код, который сразу проскочил и первый, и второй дивизион дубовой). А сегодня писал и отлаживал код весь день. Из второй дубовой вышел после первой же отправки, а вот в первой с тем же кодом даже до середины не поднялся. Правда, там и существенные изменения в условиях игры происходят: появляются новые правила и более жёсткие ограничения. В общем, судя по всему, завтра придётся код основательно переписывать. Заодно и в плане оформления улучшу… Правда, не знаю, хватит ли времени: кроме этого, собирались с отцом съездить на новую квартиру.

Продолжаю участвовать в конкурсе на CodinGame. Вчера открылась серебряная лига, куда я сразу же прошёл. А вот дальше откатился на 1200-1300 места и ничего не мог с этим поделать. Два дня ломал голову, что же улучшить в алгоритме, почему такие плохие результаты. Потом стал сравнивать свои действия и действия противника на первых ходах (у меня до 6-ого хода последовательность действий закодирована жёстко) и обнаружил, что даже когда я пытаюсь дублировать действия противника один в один, это не получается. Стал разбираться и обнаружил глупейшую ошибку. У меня проверка возможности совершить то или иное действие была сделана криво: количество sun points (очков действий) проверялось на строго больше, а не больше или равно. Как только это исправил, сразу же подпрыгнул до 860 места.
А вообще, недавно подумалось, что CodinGame — это один из немногих сохранившихся кусочков старого Интернета. Во-первых, все общаются под Сетевыми именами. А у многих ещё на автарах персонажи старых компьютерных игр (видел даже Rockmanа у кого-то). Во-вторых, техноэлитизм: положение в иерархии на сайте определяется через интеллектуальные показатели: знание алгоритмов, умение писать код и находить решение, а технически безграмотным там делать нечего. Ну и в-третьих, практически сведена к минимуму коммерческая составляющая, что спасает сообщество от деградации.

В четверг днём успел сделать ещё один небольшой шаг в плане поддержки IndieWeb — написал код для endpoint discovery.
А потом начался конкурс на CodinGame! Задача про засев леса меня очень порадовала! Как и ожидалось, в бронзовую лигу я поднялся в тот же вечер, буквально с двух commitов (точнее, на CodinGame правильнее называть их submitами), написав совершенно простенький алгоритм. А вот дальше немного замедлился. Попытался было написать алгоритм, играющий перебором, но при большой глубине поиска нарывался на таймаут, а при маленькой — оказался на 1700-ых местах из 4000.
Сегодня решил попробовать другой подход. Написал код с набором стратегий, где выбор между ними осуществляется по набору фиксированных правил. Сразу результат улучшился: сначала 1200-ое место, потом, после пары мелких правок, поднялся до 1000 позиции. Но всё равно код не самым оптимальным образом играет в самом начале, и продолжаю думать, что с этим делать. Но бота бронзовой лиги вроде обыгрывает без проблем, так что, скорее всего, в серебряную лигу тоже без проблем поднимусь.

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

Опять участвую в конкурсе на CodinGame под названием Code a la Mode. На этот раз задача достаточно необычная: нужно не пытаться обыграть второго игрока, а вместе с ним показать более хороший результат, чем этот же игрок в паре с третьим. При этом вторым игроком управляет алгоритм, о котором ничего не известно, кроме возможности наблюдать уже выполненные его действия.
Конкурс длится 10 дней, причем первые полдня я частично пропустил, не вспомнив о нем своевременно. Потом дело шло весьма медленно: в пятницу я только-только разобрался с условиями, в субботу набросал пробный вариант простого, достаточно жестко закодированного алгоритма, но так и не решился его протестировать (как всегда, внутренне сопротивляюсь первому запуску и связанному с ним разочарованию). В воскресенье все же собрался. Как это ни странно, заработало достаточно быстро, из третьей «дубовой» лиги я вышел с первой попытки, из второй — после некоторых достаточно быстрых доделок. Вот с первой пришлось повозиться: добавились новые правила, которые существенно изменили ситуацию.
В итоге получилось как всегда: засиделся до 5 утра, но смог подняться только до 4 места. Решил лечь спать, а утром обнаружил, что все же прошел в бронзовую лигу. Наскоро добавил в алгоритм несколько «костылей» для обработки тех правил, которые добавились при переходе, и сумел подняться до 240 места. Теперь вот думаю, что лучше: попытаться доделать уже существующий алгоритм, заменив «костыли» на нормальную обработку одной ситуации, и посмотреть, что будет (по идее, этого окажется достаточно, чтобы прорваться в серебряную лигу), или садиться писать новый, более гибкий, который пришел мне в голову вчера вечером.
Кстати, впервые мне удалось подняться в бронзовую до открытия серебряной (если не считать одного двухэтапного конкурса).

Вчера после долгих поисков нашел на CodinGame задачу, которую легко можно было решить с помощью bash-скрипта. Все-таки сколько я, оказывается, о bash не знаю! В частности, не знал, что там можно использовать массивы, правда, с крайне неудобным синтаксисом. Потом тут же решил легкую задачку на C++ (заодно понял, что ощутим его подзабыл, в отличие от чистого C, на котором хотя бы иногда что-то пишу). В результате до достижения Babylon Tower, которое дают за решение задач на 15 разных языках программирования, осталось использовать всего один язык программирования. Им, как и планировалось, стал Kotlin, изучением которого я хотел заняться уже давно, но, как всегда, бессознательное протестовало против планов, поэтому вместо него стал писать на Lua и Ruby.
Требовалось решить задачу, которая сначала казалась предельно простой: найти минимальное N при котором a^N оказывается меньше N!. Казалось бы, достаточно пройтись циклом, и решение будет найдено. Но я не учел одного: того, что тесты для решения содержали весьма большие числа (такие,что N уходил за тысячу). И для подсчета «в лоб» попросту не хватало разрядности чисел (тем более в Kotlin, как и в Java, максимальная разрядность для чисел с плавающей точкой — 64 бита, а не 80).
Пришлось включать мозг и искать обходное решение. Оно нашлось довольно быстро. Сначала я решил попытаться получить результат через аппроксимацию факториала. Но увы, аппроксимация есть аппроксимация: N находилось с точностью до нескольких соседних чисел. По сути дела, ее можно было использовать как верхнюю оценку N, и дальше уменьшать его, проверяя выполнение неравенства на каждом шаге. Но как проверить неравенство, если и справа и слева значение вылезает за пределы допустимого? Поломав голову, вспомнил совет, когда-то давно виденный на Хабре: работать не с самими числами, а с их логарифмами. Тут я сообразил, что нужно взять логарифм от факториала можно посчитать как сумму логарифмов отдельных множителей. А с другой частью — все и того проще: N*ln(A).
Как только я это реализовал, программа тут же заработала как надо, и я получил долгожданное достижение Babylon Tower (впервые о нем я начал думать еще с лета, если не раньше).

Сегодня закончился конкурс A*Craft на CodinGame. В отличие от предыдущих, он длился всего два с половиной дня и был не на игры, а на оптимизацию: нужно было расставить стрелки на карте так, чтобы сделать суммарный путь роботов по ней максимальным. Я занял 150-ое место из 2456! (Правда, примерно последние 500 участников — те, кто зарегистрировался, но даже не попытался прислать хоть какой-то код, и поэтому получившие 0 очков.) Это гораздо лучший показатель, чем во всех предыдущих конкурсах. Если считать в относительных показателях, то до этого мне максимум удавалось подняться до 84%, а в этот раз — до 93%, что близко к моему верхнему порогу амбициозности!
И это несмотря на то, что толком на конкурс не настроился, и до воскресенья подходил к нему как-то лениво. Впрочем, задачи по оптимизации даются мне проще сами по себе. Кроме того, код был основан примерно на том же рекурсивном алгоритме, который я впервые пытался применить еще в Code of Ctulu. Написал я его достаточно быстро, но потом обнаружился какой-то совершенно непонятный баг, на борьбу с которым ушла половина воскресенья. А причина оказалась банальной: я дважды использовал одно и то же имя result в одной функции, но подразумевая при этом две совершенно разных переменных: одну для поиска максимума, вторую — для хранения значения, которое будет возвращено из функции. В результате вместо максимума возвращался последний результат.
Из-за этого я только вечером воскресенья обнаружил, что хотя алгоритм хорошо справляется с картами из узких длинных коридоров, но дает довольно посредственные результаты на картах с большими смежными областями. Для таких карт я задумал было еще один алгоритм с совершенно другим подходом, но так его и не реализовал. Во-первых, не хватало времени, чтобы тщательно его обдумать и вытащить из зоны неуверенности. Во-вторых, нашел один случай, когда первый алгоритм (который рекурсивный) давал неоптимальный результат. Сначала казалось, что ошибка простая и ее удастся устранить быстро. Но все оказалось не так: я провозился с ней до глубокой ночи. А потом выяснилось, что ошибка действительно примитивная: я забываю вызвать .copy() при рекурсивном вызове функции, в результате чего вместо копии карты для поиска на следующем шаге передается ее исходный вариант и результаты поиска пути в разных направлениях начинают влиять друг на друга. Странно, что на остальных картах это работало! Причем выяснилось, что если на каждом шаге создавать копию карты, это занимает много времени, и в итоге на многих тестах начинается вылет по таймауту. Пришлось применить «костыльное» решение: написать условие, по которому принимается решение, делать копию или нет.
Поэтому вместо второго алгоритма сделал простую проверку: если карта с большими смежными областями, и роботов много, то для последних строить путь только до ближайшей уже размещенной стрелки. И, как это ни странно, это дало определенный результат: вместо 5400 очков, которые я набирал изначально, стало получаться 5700! А вот исправление того бага с копией дало всего лишь жалких 17 очков (впрочем, их оказалось достаточно, чтобы подняться еще на несколько мест).
Но вообще, наверное, надо было писать не на Python, а на PHP. Там и код быстрее выполняется (если в PHP 7), и копии массивов создаются автоматически (так что я бы не возился полдня с первым багом и, может быть, успел бы и второй алгоритм реализовать), причем в режиме copy-on-write, что тоже дало бы неплохую оптимизацию. Но увы, нельзя применять в качестве ключей для хеша связки из нескольких значений (то, что в Python называется tuples). Впрочем, при желании это можно было бы легко обойти.
Но в любом случае, я доволен результатом!

Прошлое воскресенье и понедельник я провел в очень подавленном состоянии. На конкурсе CodinGame дела шли очень плохо: несмотря на все мои попытки усовершенствовать алгоритм, я скатывался все ниже и ниже в рейтинге, и никак не мог понять, почему это происходит. Вроде ошибок нет, алгоритм играет нормально, а я все равно раз за разом проигрываю. Еще и чата узнал, что есть люди, которые вообще написали полноценный симулятор этой игры у себя на компьютере и провели на нем моделирование множества игр, на основании чего для каждой карты определили коэффициент ее полезности. Стало ясно, что с моим простеньким алгоритмом выбора карт с такими тягаться не по силам.
Попробовал даже быстро написать новый вариант (уже пятый по счету), но и в нем результаты отличались не сильно. Во вторник я прекратил все эти попытки, а стал искать среди уже отправленных версий те, на которых мне еще удавалось подняться хотя бы до середины лиги. И в итоге нашел такую, которая позволила снова подпрыгнуть до 202 места. Среда и четверг ушли на испытание в этой версии некоторых идей, которые возникли в воскресенье и понедельник. Еще я пытался поиграться с функцией выбора карт на этапе начальной раздачи. Но все было безрезультатно: либо изменения были несущественны, либо наоборот, я начинал падать вниз. Кроме того, так и оставался вопрос с тем багом, про который я уже писал. Почему-то при его наличии результаты получались в разы лучше, чем при его отсутствии, хотя с точки зрения здравого смысла должно было быть все наоборот. Еще пытался изучить статистику и понять, на каких именно раскладах я проигрываю, но все что удалось — это сделать предположение, что проигрыши идут на раскладах, где guard-карт мало, а противник набирает много «тяжелых» карт.
Наконец, наступил последний день конкурса — пятница. Тут мне пришло в голову (опять же, под влиянием чата) применить метод Монте-Карло, то есть выбирать ход случайно, моделировать возможный ответ противника, исходя из соображения, что он будет бить только в guard-карты и моего игрока, и оценивать результат, выбирая в итоге тот, у которого оценка оказалась лучшей. На удивление быстро я переделал под него свой старый код, но увы, такой подход тоже оказался совершенно безрезультатным: я по-прежнему оказывался на дне серебряной лиги.
Вообще, если в предыдущих конкурсах было понятно, что делать, как играть, чтобы выиграть, но у меня не хватало знаний описать это математически и закодировать, то в этом — все наоборот. Я мог написать практически любую стратегию, но никак не мог понять, как вообще надо играть, чтобы выигрывать. В частности, как именно происходит захват стратегической инициативы, когда у одной из сторон на столе оказывает на три или более карт больше, после чего дальнеший ход игры, фактически, предрешен. А не понимая этого, я мог делать функцию оценки только вслепую из общих соображений типа «health points и показатели карт на столе моего игрока должны давать плюс, health points и карты противника — минус». И, судя по всему, главный недостаток моего алгоритма заключался в том, что слишком часто он решал выложить новую карту вместо того, чтобы бить в противника. И еще я не учел ассиметричности игры, того, что оказавшись вторым по очередности хода, нужно играть иначе, чем первым (хотя как именно «иначе» — не понимаю до сих пор). Из-за этого у меня было много результатов, когда я у одного и того же противника первым игроком выигрываю, вторым — проигрываю.
Еще непростой выбор был в конце между двумя версиями кода, одна из которых была хорошо протестирована, а другая — меньше, но вроде бы давала лучший результат. В итоге менее чем за минуту я все же выбрал вторую. И вроде бы не прогадал: 203 место в серебряной лиге, 590-ое в общем зачете. То есть с небольшой погрешностью повторил свои результаты предыдущих конкурсов.
В общем, что можно сказать в итоге: переписал код целых семь раз, получил массу опыта и интересных идей, попробовал делать то, о чем прежде имел весьма смутные представления, впервые стал целенаправленно применять функциональный подход и оценил его преимущества, да и вообще стал чувствовать себя в Python так же уверенно, как и в PHP. Но увы, в плане результатов я ожидал все же большего…