Ры (pbl) wrote,
Ры
pbl

ICFPC 2011

ICFPC 2011,
или (dbl (succ (dbl (succ zero)))) колесо

(succ zero)

Прямо с ночи Влад, Микал и cail начали понемногу обсуждать все это безобразие. Всплыла, разумеется, Unlambda. Некоторые идеи протухли впоследствии совершенно незаслуженно (copy), некоторые, in hindsight, кажутся довольно смешными:
Поскольку игра детерминированная и с полной информацией, будет куча людей, которые напишут поиск по древу.
Я так понимаю, в действительности почти никто этим не занимался.

К тому моменту как я проснулся, Влад уже вовсю писал функции карт и базовый движок. Я сначала засел читать задание (тут очень кстати у меня глухо уронился мобильный интернет - помашем теле2 лапкой), и первое, что мне пришло в голову - то, что у меня есть вполне работающий abstraction_elimination.js

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

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

B- и C-комбинаторы я выкинул за неимением, прикрутил токенизатор и научил парсер читать лямбда-выражения вида (λx y. ...)

Параллельно всему этому в скайпе шла оживленная дискуссия о создании "несучковатых" (гг, "ветвистых" было бы уместнее) термов, а равно о прочих королях и капустах. Несучковатая генерация вращалась в основном вокруг (x y) (z t) и (get i) (get j). К сожалению, никто из нас не владел комбинаторной логикой в такой степени, чтобы сесть и нарисовать трансформацию сходу (да и не сходу - тоже).

Из капусты обсуждались в основном вопросы глобальной стратегии (комба vs. контроль), зомбаки, GIL (в формулировке "БЛЯ ТОЛЬКО БЕЗ ТРЕДОВ!!!"), B-комбинатор ("но у нас же его нет!" - "есть.") и оценка намерений противника. Ко всему этому току постепенно присоединились cail, fj и earthdok.

Хотя эмулятор был еще не готов, Влад начал писать болванки ботов.

Очень скоро Влад сел и внезапно сделал охуенную вещь - несмотря на ее видимую челябинскость. А именно, поиск нужных нам термов брутфорсом. И запустил.

Я тем временем отполз от кода, поскольку не очень было понятно, что еще отдельное я мог сделать; да и работы накопилось - в частности, пришел еще один юный чукча на интервью (кстати, берем!!! хотя задачки мои он отрешал отнюдь не блестяще).

cail написал драфт интерфейса бота-стратега и генератор нужного числа в нужном слоте на его основе (но после этого надолго пропал), а брутфорсалка продолжала люто брутфорсить.

В два часа по Риге она нашла нам (get 1) (get 0).

ЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫ!

Это был пипец какой прорыв, но я до этого сразу не допер, - и никто не допер, мне показалось.

Впрочем, скоро бульдозер Влада докопался до (get 2) (get 0) и (get 3) (get 0). Что невооруженным взглядом генерализовывалось на (get n) (get 0). Вот тут стало ясно, что это круто. Мы еще не могли получить произвольный терм, но мы уже знали, как это сделать.

Попутно нашлись и несколько других термов типа (get 2) (get 2), что впоследствии сыграло довольно важную роль.

earthdok написал базовый run, а я начал гонять StrategyBotа и делать AppNTo0Strategy.

Пипл начал обсуждать риплей и визуализацию, от которых я в неприличном смятении отрекся, а cail прорезался на минуту и резонно спросил, мол, пацаны, а вам не кажется, что надо бы работающую эмуляцию?

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

earthdok начал методично доделывать эмулятор, fj ломал что-то в той же эпсилон-окрестности, а я отпал до половины девятого по транспортным причинам.

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

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

Около половины одинадцатого fj сказал, что нашел генерализованный (get i) (get j), отчего я возликовал, но потом сказал, что пока оно глючит. Впрочем, через несколько минут он пушнул. Я увлеченно разламывал ботов, ио и гейм, поэтому смотреть туда все-таки не стал, ибо убоялся.

Ближе к полуночи появился Микал, и разговор зашел о стратегии, а потом как-то резко перескочил на "неспортивненько". Тут всплыла какая-то легендарная, но темная история с адептом, отчего многих коллег одолела ржака :-) Вообще меня очень радовало, что никто из команды (насколько я знаю) не шарился по межкомандным жаббер-конфам и т. д. Я не думаю, что это совсем уж анафема, но правда ж неспортивненько.

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

Я все продолжал пилить ввод-вывод и арену. Получалось тяжеловесно, да и подумать стоило покрепче, поскольку я больше механически выламывал весь ио, чем размышлял о том, кому и в каком виде он вообще нужен. Меня интересовало другое: я вообще довольно часто, выдумав объект типа T, начинаю думать о том, а нельзя ли сделать такой смищной тип, который из двух T будет делать опять же T (and I blame Haskell for that, too). Примерно такую развесистую клюкву я и написал, с ужасно комбинируемым вводом-выводом для риплеев, разных форматов аутпута и компетишна.

Скоро у меня образовался кособокий треугольник арена-гейм-бот с болтающимся сбоку ио, но работало это все весьма убедительно.

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

В тот момент я даже представить не мог, что готовит для меня день второй.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 10 comments