Category: история

ICFPC 2019

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

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

Очень любопытно посмотреть, чего ты стоишь. В голове-то ты мог много себе про себя нафантазировать, а тут вот объективная реальность, ладдер, и ты либо можешь компьютер заставить делать что ты хочешь, либо не можешь. Никаких «если бы», никаких «возможно, наверное, мне кажется». Мы довольно посредственно выступили (на момент закрытия 29 место из 142 участвовавших, в лучший свой момент были на пятом).

Исторический скриншот. Дальше мы сильно сдали
Исторический скриншот. Дальше мы сильно сдали

Участвовали втроем, я в первый раз. Как я понял, средний размер команды ~5 человек, не редкость и восемь встретить. Втроем у нас довольно хорошо делились области ответственности, было бы больше появился бы организационный оверхед (как мне кажется). Восемь человек я бы вообще офигел менеджить и вообще ничего бы не написал, наверное. С другой стороны, больше рук – можно попробовать больше подходов. Можно вложиться в инфрастуктуру. Наверное.

Задача достаточно нетривиальная, чтобы решить ее до конца было в принципе невозможно. Но и не супер-сложная, чтобы как-то ее решить можно было бы даже иногда и руками (ну, самые простые примеры). Как правило это значит перебор вариантов в каком-то NP-полном поле, соревнование эвристик.

Собери бонусы, закрась лабиринт
Собери бонусы, закрась лабиринт

Clojure, несмотря на все плюсы языка высокого уровня и быстрого iteration time, по ощущениям подошла довольно плохо. Потому что все упирается в перформанс. Можно сколько угодно рассуждать про «глобальные оптимизации против локальных», ненавидеть байтоебство, мыслить как стратег с высоты птичьего полета и гордиться тем, что не знаешь, как устроен компьютер, но это все и в императивных языках можно делать. Они же не отнимают способности мыслить и планировать. Да, механика записи мысли чуть более многословна, ну зато оно того стоит. Плюс за три дня вы разницы может и не заметите даже. А вот по перформансу заметите, еще как. Как ни крути, а команда, которая обсчитает за условное время X в два раза больше вариантов, чем ее конкурент, будет в топе выше. КАК НИ КРУТИ. Больше здесь строго лучше. Либо больше итераций, больше вариантов попробовать, либо решения будут более глубокими, а значит и очков принесут больше.

ICFPC это как раз такой случай, когда лучше чуть больше устать но получить программу которая будет нагружать процессор по делу, а не только мусор за юзером подбирать. К тому же, как ни странно, старые императивные языки может и не очень легко позволяют до энтерпрайзных масштабов раздувать программы, но что-что а бегать по массивам и мутировать структуры они похлеще функциональных могут. Ирония – соревнование приурочено к конференции по функциональному программированию, а побеждают в нем все стабильнее C++ и императивщина.

Выглядит красиво, жаль вся эта мощь обслуживает всякое говно вроде lazy sequences, primitive boxing, high-order functions вместо того, чтобы решать задачу
Выглядит красиво, жаль вся эта мощь обслуживает всякое говно вроде lazy sequences, primitive boxing, high-order functions вместо того, чтобы решать задачу

Сейчас я думаю, что даже если бы мы выбрали просто Java с unboxed примитивами и примитивными массивами, было бы качественно лучше. C++/OCaml/Rust может быть дали бы еще 1,5-2 раза прирост, но это уже не изменило бы ситуацию качественно. Но может и нет, цифры так, с потолка.

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

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

Кстати, многие ошибки, которые все-таки у нас были, были связаны с подстановкой переменной того же типа, где никакая система типов бы никого не спасла. Ну оно и не удивительно, когда у тебя большая часть программы, процентов 90, гоняет инты направо и налево. Это же алгоритмы.

не с этого хакатона, но смысл такой же
не с этого хакатона, но смысл такой же

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

лабиринты, генерируемые нашим алгоритмом, имели хорошо узнаваемый вид
лабиринты, генерируемые нашим алгоритмом, имели хорошо узнаваемый вид

Очень важна базовая гигиена. Ну там код неиспользуемый удалять, переменные нормально называть, на функции разбивать нормально где нужно, не писать по два-три раза почти одно и то же, если уже написано. Казалось бы, тоже — хакатон, вы через три дня все это выкините, так ли это важно? Вот оказалось что да. Потому что там где в обычном проекте косяки может через полгода-год всплывут, здесь если ты что-то поленился, коллега уже через полчаса об это споткнется. Причем споткнется обязательно, потому что кода мало и все используют всё постоянно. Так что лучше пять минут потерять, но поправить самому, пока контекст у тебя в голове, чем заставить коллег тебя материть и тебя же дергать. Чисто по времени выгоднее. Несмотря на.

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

Визуализатор организаторов
Визуализатор организаторов
ух как же меня бесило выбирать эти файлы каждый раз!
ух как же меня бесило выбирать эти файлы каждый раз!

Самое большое, чего там не хватало — пошагового реплея, перемотки назад и вперед, ну и доп информацию тоже иногда хочется какую-то вывести. Как разбился лабиринт, что думает бот, такое. Я написал в какой-то момент простой визуализатор через println и clear screen, он даже мультики показывал типа, но хотелось бы чего-то более удобного и универсального.

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

Приходить надо было подготовленным. У ребят, например, из контура, была инфраструктура заготовлена: сервера, гоняющие задачи, сбор ответов, дашборд, сравнение. Мы этого, конечно, не знали, у нас в лучшем случае запустил программу на ноуте — в терминал вывалился результат. Пик инфраструктуры.

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

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

Как правильно распределять силы я пока не понял. Я выложился по максимуму в первый день (до 6 утра, на следующий встал в 11) чтобы как можно больше впихнуть в Lightning Round (первые 24 часа). В результате весь второй день был как в тумане и работалось как на автопилоте. В третий зашли нормально, я переписал алгоритм даже, но тоже было очень тяжело. Возможно, здоровый сон каждый день (ну ок, кроме последнего) суммарно дал бы больше эффективности за три дня, чем такое.

Перерыв на обед
Перерыв на обед

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

Тактика

Добрый день, с вами Тонский и рубрика «внезапные озарения по гейм-дизайну, о которых никто не просил».

Да, я все продолжаю залипать на стримы по Героям и делать далекоидущие выводы. Вот что меня какое-то время удивляло: герои 3 и 5 вышли давно, сообщество с тех пор их оценило, погоняло в хвост и в гриву и понаписало патчей и «турнирных» правил, которые делают игру в целом более честной и терпимой. Причем меняется многое — и баланс, и интерфейс, и сетевой код, юниты и герои вводятся и запрещаются. Но что никогда не трогают так это ИИ. И это меня удивляло — почему?

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

Это было во-первых. Во-вторых, тактический ИИ в героях, который как раз руководит этими нейтральными стеками, довольно тупой. То есть он прямолинейный, предсказуемый, не просчитывает вперед, не строит стратегии или даже плана на битву, совершает из-за этого совсем локально-как-бы-оптимальные-но-уже-на-следующем-ходу-кошмарные ходы. Если сравнить с шахматами, то это примерно уровень «на каждом ходу брать самую дорогую фигуру или двигаться к ней», все. Казалось бы, в чем интерес? Почему это не фиксят, сделать лучше такого даже стараться особо не надо. Значит оно так специально.

Ну и получается что да. Я еще один пример приведу, игра Into the Breach. Такая игра необычная, в которой ты не то что не пытаешься предсказать, как поступил бы «достаточно рациональный противник», в ней следующий ход противника прямо явно вываливается на тебя как часть ситуации. То есть на каждом ходу тебе просто показывают, что будет делать враг. А в чем тогда игра? Игра в том, чтобы обладая этой информацией, сыграть так, что бы у него ничего не вышло. Предотвратить этот самый предсказанный ход, по возможности, на 100%. То есть это такой пазл, в котором, во-первых, ситуация очень несимметричная и к противнику совсем нечестная, а во-вторых, вероятности отсутствуют как класс. Будущее просчитывается, RNG не мешает. И это вполне играбельно и очень даже интересно, зазасывает.

Ну и возвращаясь к героям, штука в том, что тактически Герои как раз такая же игра, хотя может она себя так и не осозновала. Главный шик — зная предсказуемую модель поведения противника, максимально абьюзить ее и получить с этого непропорциональное преимущество. Выманить врага из стен замка, где ему, стратегически, гораздо лучше. Заставить медленный юнит гонять по полю за быстрым, пока лучники его обстреливают. Подойти на столько, чтобы ударить первым. Подставить маленький отряд, чтобы потом безболезненно врубиться большим. Взять юнита ради права первого хода. Заманить на мины. Встать между камнями, чтобы кони не подошли. Обманом растратить ману. Это все вполне тактические задачи, искать решение которых (и находить) вполне себе особый вид удовольствия. Удачно подобранная конфигурация армии (иногда вплоть до плюс-минус одного юнита) кардинально меняет ситуацию и может разносить совсем неожиданные по размеру армии, если придумать как. Герои, как в них играют сейчас, и есть игра про это.

А если ИИ был бы умнее, битвы очень быстро перестали бы быть тактическими и скорее стали бы соревнованием у кого армия толще. Сильный нападает на слабого, слабый обходит сильных. Ну или классика геймдизайна, камень-ножницы-бумага, выбирай то что контрит врага, угадал — будешь в шоколаде, нет — извиняй, дорогой. Не то чтобы таких игр не бывает — бывает, конечно, и не то чтобы они неинтересны — очень даже интересны, но по-своему, по-другому. Если ты любишь тактику, то в стратегических героев ты бы уже не стал играть.

Ну и второй момент — для мультиплеера, конечно, важна симметричность условий для всех. Но герои — игра принципиально не мультиплеерная, и некий дисбаланс в битве умный ты—тупой компьютер, в общем-то, и составляет геймплей. Так что симметричность не очень-то и нужна, и даже с полной информацией о будущем игроку остается о чем подумать. Играть так может быть даже интереснее. Более того, если себе в этом признаться заранее, много новых возможностей для дизайна боев откроется.

усы2

Голые короли IT

Моя программистская карьера началась бесхитростно — там, куда взяли. Взяли делать бэкенд на Джаве. Ладно. Все равно я не знал, о чем надо мечтать. Потом немножно Питона. Распределенные системы. Erlang. Щепотка Perl-а. Последние два года программирую интерфейсы. Расчет был, конечно, что я приду на все готовое — разберусь и пойду дальше. Как бы не так. Готового, на самом деле, нигде не было. Всегда превозмогание. Молодая индустрия. Ладно. Но вот странно, как люди этого не ощущают. Есть метания. Мода. И люди прям всей головой и сердцем отдаются. Может, это только у самых шумных, конечно, но каждое новое веяние как последнее. Не хватает какой-то скромности, умеренного энтузиазма.

Я помню энтузиазм по поводу XML-я. Потом тот же энтузиазм по поводу Java-аннотаций. Я еще думал: окей, мы пишем по-другому, но пишем-то то же самое. Неужели это может чью-то жизнь изменить? Верили, что может.

Hibernate помню, и эти убойные аргументы: а что если мы базу данных захотим поменять? И все верили, и шли на поводу, и полностью всё приложение переписывали, лишь бы не было SQL-я. Да, трудно становилось через какое-то время, и начиналась борьба не за код, а за выживание, с самим Хибернейтом. Но никто трезво на это не смотрел, казалось, что если проблемы, это мы недопонимаем и надо еще бороться. Естественно, консультанты, рекомендации, best practices.

Помню, как мечтали о JavaEE, и я тоже мечтал. Оказалось, что это тот же Хибернейт, только нужно еще раз все переделать. Переделать, чтобы получилось так же. Наивные были, молодые. О чем больше всего говорят, то и используем. Смешно — где сейчас Хибернейт, а где SQL, да?

Помню безумие вокруг Inversion of Control, помню как читал гайд к Guice, в котором писали: «сейчас мы вам объясним, как надо писать программы. Скорее всего, вы обнаружите во время рефакторинга, что одно тянет за собой другое, и чтобы внедрить IoC, вам понадобится переписать весь код. This is a good thing». Это this is a good thing очень въелось мне в память, я отчетливо в тот момент почувствовал, что нас всех дурят. Но где было мое смутное ощущение, и где лидеры индустрии. Оказалось, лидеры тоже бывают голые.

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

Или вот: в ООП меня очень смущал вопрос «Paper.writeWith(Pen) или Pen.writeOn(Paper)». Тогда мне казалось, что ООП пригодно для всего, пóлно, следовательно правильный ответ существует, просто я не до конца разобрался, и нужно напрячься. Сейчас я расслабился, вижу, что у каждой концепции есть границы, когда что-то в нее не лезет, это проблемы концепции, а не того, что в нее запихивают. Это нормально. Даже если очень хочется быть адвокатом какой-то идеи, честность, хотя бы перед собой, важнее. Не надо мутить воду. Если функция удобнее класса — берите функцию. В этом больше честности и смысла, чем в следовании OOP-way. Нет никакого OOP-way. Нет никакого Java-way, Ruby-way, NodeJS-way, FP-way, microservice-way, Docker-way, не надо приносить им жертвы. Концепция это инструмент, а не религия или образ мысли. И не надо доставать ключи из словарей через Promise.

Но крестовый поход длится и по сей день. Концепции новые, адвокаты все такие же. Читал на днях:

How do you approach this problem with Rx? Well, to start with, (almost) everything can be a stream. That’s the Rx mantra.

Then we will have created a beast called “metastream”: a stream of streams. Don’t panic yet. A metastream is a stream where each emitted value is yet another stream.

Flatmap is not a “fix” and metastreams are not a bug, these are really the tools for dealing with asynchronous responses in Rx.

Сравните с гораздо более адекватным:

Note: It is usually best to use signals as little as possible. When it comes to writing nice modular code, you should primarily use normal functions and values. If you find yourself stuck with a signal of signals, ask yourself “how can I model this explicitly with functions and values?”

Вот человек тоже адекватно пишет (лучше всю статью прочитать) про то, что если вы придумали асинхронный IO, то как его не маскируй, получится не очень:

People in the Node community have realized that callbacks are a pain for a long time, and have looked around for solutions. One technique that gets a bunch of people excited is promises, which you may also know by their rapper name “futures”.

But, honestly, it’s like the difference between being punched in the gut versus punched in the privates. Less painful, yes, but I don’t think anyone should really get thrilled about the value proposition.

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

усы2

О пользе чистых начал

Тут в Гугл Плюсе Евгений Охотников сетует, что наработки 80–90-х годов нельзя переиспользовать в вебе:

Ну вот, допустим, кто-то 20-ть лет назад сделал движок текстового или графического редактора. Не суть важно, на C++, Eiffel, Java или Delphi. Для десктопа, понятное дело, т.к. Web тогда только зарождался. Какое-то время этот движок был актуальным и мог быть портирован под разные платформы путем адаптации GUI-библиотеки (или же путем написания слоя между движком и конкретной GUI-библиотекой).

Но с окончательной победой Web-приложений над здравым смыслом (т.е. где-то лет 10 назад по моим субъективным наблюдениям), у разработчиков такого движка встал бы серьезный вопрос: а как все имеющиеся наработки портировать под Web? В котором на клиенте нормально живет только JS, а технологии обмена информацией между клиентом и сервером где-то на уровне каменного века? :)

Кроме как путем серьезнейшей переделки потрохов не получится, имхо. Что, как мне представляется, хорошо видно на примере MS Office, который вышел в Web относительно недавно. И где потребовалось много времени и сил на то, чтобы переиспользовать старый код в Office 365, дописав к нему новых клиентов (своих для каждой платформы).

Все так, но это скорее хорошо, чем плохо.

Любая система рано или поздно упирается в локальный максимум, из которого уже не может выбраться эволюционным путем. Интерфейсы в 80-х мало кто понимал. Отчаянное время. Но и сейчас мы далеки от конечного равновесия: никто не обещает, что через пять лет все опять кардинально не поменяется. Мы пока просто не знаем, как должны выглядеть интерфейсы, программы, да и вообще компьютеры. Делать ставку на долгую поддержку в такой период глупо — наследственность тянет через себя не только хорошие вещи, но и давно неактуальные, а также откровенно плохие. Если вы знакомы с современным Фотошопом, в этом видео видно, откуда растут уши у его многочисленных странностей: Undo по Cmd+Shift+Z, кнопки Preview в эффектах, дурацкие модальные окошки с No pixels selected. Все они прожили по 25 лет.

Чем дольше существует система, тем сильнее обостряется конфликт между новыми потребностями и грузом прошлого. Кода много, его невыгодно переадаптировать, репутация питается только былыми заслугами, программа переходит в режим доживания. Становится выгодно начать с чистого листа. Так за последние 5 лет появились легкие и современные альтернативы Адоби: Скетч, Пиксельматор. Из ниоткуда. Но их экономика понятна: полное переписывание это всегда улучшение минимум на порядок. Новые программы удобнее и актуальнее.

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

Возникает чисто практический вопрос: разве это не безумная прорва работы, сделать что-то хотя бы минимально ценное для пользователя, тот же графический пакет или текстовый редактор? Да, но это и есть проблема: так не должно быть. Нет никаких предпосылок к тому, чтобы разработка Иллюстратора была десятилетней эпопеей на миллионы человеко-часов. Просто наши инструменты несовершенны: разработчики на C++ борются с проблемами, которые присущи не предметной области, а самому инструменту. Включая размер кода, который очень быстро сам по себе становится проблемой. Фокус не в том, где взять столько усилий, сколько вбухивает Адоби. Фокус в том, чтобы делать то же самое быстрее и проще. Этому не научишься, если постоянно доделывать один монолит, поэтому даже хорошо, что GTK не натягивается на HTML. Каждый следующий виток снимает еще одну головную боль, и постепенно, раз за разом, мы придем к нужному состоянию, когда студент сможет написать базовую версию Фотошопа за летние каникулы.