Ры (pbl) wrote,
Ры
pbl

ICFPC 2011

ICFPC (succ (dbl (succ (dbl (dbl (succ (dbl (succ (dbl (dbl (succ (dbl (succ (dbl (succ (dbl (succ (dbl (succ zero))))))))))))))))))),
или (((((S ((S (K S)) ((S (K K)) ((S (K S)) K)))) ((S ((S (K S)) ((S (K K)) ((S (K S)) K)))) (K ((S ((S (K S)) K)) I)))) succ) dbl) (succ zero)) колесо

(((((S (K (S ((S (K S)) K)))) ((S (K S)) K)) dbl) succ) zero)

Tempers are running high aboard USS Enterprise.

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

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

Я полез смотреть simple_bot'а, чтобы переписать на него убивалку слотов. Довольно скоро slot_killer был готов. Делал он все то же самое - качал слот-батарейку, и стрелял лазором - но на новом, прости господи, фреймворке. Я его благословил и залил на дуэльник, где он начал грубо мочковать всяких тестовых ботов. Это был первый наш рабочий бот, который убивал быстрее, чем за 100,000 ходов. По ходу, какую-то ступень на пути к совершенству мы пропустили, потому что был широкий класс ботов, успевавших убить примерно 80 наших слотов к моменту отправки обратно к создателям.

Вскоре Убийца Слотов наткнулся на бота, вынесшего его за 1680 ходов. Это было грустно, но отнюдь не удивительно - и так было ясно, что надо делать что-то хитрое с комбинаторами.

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

((λc f x. (λi. (λg. i c f x) (i f x))) (λc f x. (λi. (λg. i c f x) (i f x))) (dec) (zero))

Тут я немножко погикал, заорал, что это МЕГА-ТЕРМ ПОБЕДЫ!!1 но совершенно напрасно. Так как при попытке запустить этот ад бот зависал наглухо.

Я обратился за консультацией к Владу и fj, которые к тому моменту тоже уже появились в онлайне, и тут мне объяснили, что...

pbl@vu:~/Sandbox/python/icfpc2011-tbd/ltg$ time python src/play.py --replay ../replays/slot_killer.rpl 'test_combo_bot()' 'test_idiot_bot()'
4058976


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

Момент с пространственной сложностью результата уже всплывал в чате, но я его тогда пропустил мимо своих ослиных ушей.

Я немного пал духом, но тут, слава богу, все-таки сообразил за насчет гетов. И сел писать бота, которого самонадеянно назвал kick_ass. Это был все тот же Убийца Слонтов, но обремененный ячейками наведения, и с интегрированной лечебно-боевой частью, активирующейся простым I.

(Начиная с названия kick_ass меня почему-то повело вразнос, и из меня хлынули дебильные идентификаторы, лазоры и коммит мессиджи из старварсов и терминатора: сам кикэсс пошел в репу под бессмертным - Do not try. Do, or do not.)

Жоподер уделывал Убийцу легко, но вот на дуэльнике проявил себя очень паршиво. Он долго раскчивался, во-первых. А во-вторых, мне показалось, что там элементарно пошла волна все более и более сильных сабмишнов.

Впрочем, я загикал вдвое яростнее, и стал выдумывать как бы Улучшить Результат.

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

Идиот.

Я уже тоже мог бы усвоить, что твики - не путь к победе на ICFPC.

Все это привело к двум новым вариациям: kick_ass_2, который слишком умничал, долго-долго строил очень уж толстую боевую часть, зато потом - в теории - мочил несколько яростнее, чем предыдущие боты; и the_battery, у которого боевая часть была крайне простой и не боевой - она просто обеспечивала очень быстрые хилы на батарейку. The Battery атаковал, собирая термы по старинке. Естественно, эта идея была абсолютно нелепой, потому что хорошо откормленный комбинаторный бот может снести любой слот одной атакой, не давая ему шанса отъесться.

Короче, в самом затвиченном варианте все это безобразие могло вынести бота-идиота за ~25,000 ходов. Это явно не котировалось.

Скоро моя дятлопись вышла на atomic do $ save Madoka. И они нас, разумеется, вынесли за 186 ходов. Вот тут я реально выпал в осадок и задумался о смене парадигмы.

Все это время fj интенсивно ковырял гаечным ключом в энджине и утилитах для конвиньенса, а Влад порождал network.

Когда об этом самом нетворке зашла речь в первый раз, я, под влиянием Греки Беспалова, не удержался и желчно пробубнил что-то о "сунул гоал эрроу в нетворк". In case you haven't realized that I'm quite a jerk yet, now would be just the time to figure that one out.

В общем пилка и стружка продолжались еще некоторое время. Я все-таки ДОДУМАЛСО разбираться с рекурсивными комбинаторами, а Влад все строил своего живуче-адаптивного некроманта.

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

А у меня был какой-то примерно такой комбинатор:

(λicomb. (K (icomb get (succ (succ zero)))) ((icomb get zero) (icomb get (succ zero))))

Заниматься нетворками-фреймворками я отказался наотрез. Не знаю, какую роль в этом сыграла история с энтерпрайзом - я порядочный мудак, так что какую-то наверняка сыграла. Но мне действительно казалось неразумным заниматься какой-то новой заумной шнягой, когда у меня тут АБСОЛЮТНАЯ ВЛАСТЬ вот почти уже (о чем я орал непрерывно).

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

Я же сначала влил оппу три десятка деков для проверки концепции. Потом сделал мегахелс на том же комбинаторе. А потом породил и комбинатор со счетчиком:

(λzeroarg icomb. ((icomb get) (succ (succ zero)) (succ zeroarg)) ((icomb get) zero zeroarg))

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

В общем, эта штуковина в чем-то была крутой. Она раскачивалась аж пятьсот ходов, зато потом начинала вливать дикий дамаг пополам с селф-хилом каждые несколько ходов. Только цели давай. Тем не менее, тупой ея твикинг был ошибкой. Да, максимально затвиченная она может снести идиота за ~2,500 ходов (один более другой твик был гораздо медленнее в целом, но зато давал 80к дамага за атаку, гггг):

(0, r'(\icomb. icomb get 0 (icomb get 1 (icomb)))'),
(4, r'(voltage)'),
(5, r'(otake)'),
(1, r'(\icomb. (attack 0 (icomb get 2) (get 5)) (icomb help 0 0 (get 4)))'),
(2, r'(tgt)'),
(3, r'(get zero I)'),


Но при этом долго раскачивается, и вообще не держит удар.

Очень быстро мы выяснили, что бот Влада убивает ее элементарно. Нулевой же слот нейтрализуется одним из первых. А он критичен.

Мы с fj немного брэйнстормнули, и он подал идею использовать "ненужные" слоты как красные бутылочки для критичных. Я был в восторге и не сомневался, что это путь к победе.

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

В конце концов в финал пошла зомби-катапульта Влада и это, наверно, правильно. У нее есть как минимум один печальный эксплойт (не учитывая крутых комбинаторщиков классом выше) - она перебирает слоты по порядку, и не реагирует на конструкции противника. Если кто-нибудь уползет в середину и отстроит лазор там... Мегашайсверферу это не помогло бы - у него слишком неэффективные термы для лазора, он собирался бы в недрах еще дольше, и стрелял бы куда медленнее, но вообще такая дырка есть. Несмотря на это, у МШВ дырка куда толще - ему надо, чтобы его слоты долго-долго не трогали. Тогда он раскачается и убьет. Нашел дураков...

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

На этом все и закончилось.

* * *

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

По большому счету, все компоненты у нас были. Не хватило времени и фокуса, чтобы свести все воедино.

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

Написал я около двух тыщ импакта за три дня (это, по-видимому, мой стандартный результат на задачах icfpc'шного класса), но, как я уже упоминал, все это не прикотиилос.

Задачка понравилась даже не очень, а очень-очень: и, кста, мне как раз по душе, что она дает нездоровое преимущество функциональщикам. ICFPC все-таки.

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

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

А всем не пробовавшим желаю попробовать. Соло или в команде, на сишечке или на няшном хаскеле, в жопе турнирной таблицы или на первом месте - все равно оно того стоит. (dbl (dbl (succ (dbl (dbl (dbl (succ (dbl (succ zero)))))))))-пудово.
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments