swizard (swizard) wrote,
swizard
swizard

По следам последнего ICFPC


Зачитал тут пачку отчетов с ICFPC, проглядел исходники: крайне любопытно, надо отметить :) Ощущения двоякие: с одной стороны почувствовал себя невероятно тупым, с другой -- крайне коварным и стратегичным. Все-таки, подобные конкурсы хорошо выявляют сильные и слабые стороны участников.

Сначала о фейлах. Какие-то были эпическими, какие-то так, по-мелочи.

Во-первых, я так не нашел применения картам I и zombie :) Ну, тоесть, меня не покидало ощущение, что в конкурсе победят те, кто научится грамотно гонять зомбей, но сам что-то полезное с ним я придумать не смог. Что касается identity, то для моих целей он мне тупо не пригодился.

Стыдно признаться, но еще я ниасилил сконструировать натуральное число из константы "0" и функций succ и dbl :) Ну, тоесть, разумеется осилил, но у меня это оказался тупо брутфорс =) Честно говоря, я написал его минут за десять и мне даже в голову не пришло, что можно сделать как-то по-человечески. Вот так это выглядело у меня: здесь eval-binary берет число i и, рассматривая его как битовую маску, выполняет succ для битов "1" и dbl для битов "0". Получившееся число сравнивает с требуемым, и если они не равны, то берет следующий i :)

(defun make-number-chain (number)
  (iter (for i from (ash 1 (- (+ (integer-length number)
                                 (count-ones number))
                              2)))
        (when (= (eval-binary i) number)
          (return-from make-number-chain (chainify i)))))

LTG> (make-number-script 5)
((R SUCC) (L K) (L S) (R DBL) (L K) (L S) (R DBL) (L K) (L S) (R SUCC) (R ZERO))


А вот так это должно выглядеть (© Futamura Rejection):

-- | Builds a list of moves for constructing a number, assuming that the slot contains I
buildNumberMoves :: Slot -> Int -> [Move]
buildNumberMoves slot n = SlotToCard slot Zero : reverse (unfoldr numberBuilder n)
  where
    numberBuilder :: Int -> Maybe (Move, Int)
    numberBuilder 0 = Nothing
    numberBuilder n | odd n     = Just (CardToSlot slot Succ, n-1)
                    | otherwise = Just (CardToSlot slot Dbl, n`div`2)


И дело тут даже не в недостатке времени, я более чем уверен, что участвуй я в конкурсе все положеные мне 72 часа, мой брутфорс совершенно спокойно бы уехал в финальный сабмишн.

Далее, я вообще не пытался разобраться с комбинаторами. Ну, тоесть, даже какую-либо теорию читать не стал. Какие уж там циклы и рекурсии, я просто путем экспериментов в slime REPL подобрал последовательность комбинаторов, которые позволяли мне конструировать числа, применять их к картам типа help и attack и пользоваться кэшами через get и copy в каких-то вспомогательных слотах. Надо сказать, что из-за того, что я запутался в правых и левых аппликациях. у меня даже не вышло кэшировать произвольные цепочки действий из скриптов, только целиком числа и целиком функции.

Ну это ладно. Возможно, если бы у меня было больше времени, я бы разобрался. А может и нет :)

Теперь о том, что у меня получилось круто!

Во-первых, в отличие от большинства участников, которые поначалу делали слепых ботов, я сразу же сделал мониторинг игровой ситуации на поле, потому что моя стратегия изначально предполагала слежение за действиями противника. Сама стратегия была простая: help+attack: Подлечить слотом A слот B так, чтобы следующим ходом слот B смог грохнуть слот C противника. Но я сразу же заложил пару нюансов, которые, как выяснилось после чтения отчетов, попали точно в цель:

  1. Я предположил, что народ, в своей основной массе, ломанется мочить либо прицельно мой нулевой слот, либо слоты, начиная с 255 и ниже. Собственно, понятно почему. Так и вышло :) А мой бот все свои гадости строит в рандомных слотах с индексами между 32 и 192 (ну или в других, если там никого живого).
  2. Опять же, фишка с рандомизацией слотов для строительства должна была спасти меня от слепых ботов. Так оно и получилось.
  3. Каждое использование врагом своего слота инкрементировало у меня соответствующий счетчик, и, когда у меня было все готово для убийства, я целился в самый активный слот супостата. Как выяснилось из отчетов, это был тоже удачный ход :) Разумеется, против мудрых врагов, которые рекурсивно отлечивали слоты до 65535 или успевали меня убить еще до моих активных действий все это не помогало, но, в целом, я угадал.

Далее, я сразу правильно придумал, как организовать AI. У меня, в отличие от многих, это были не просто скрипты, а сопрограммы в CPS. Грубо говоря, вызов функции ai мне возвращал очередной ход из текущего активного скрипта и продолжение, которое я должен буду позвать на следующиий ход. Это позволило мне убить сразу нескольких зайцев:
  • Языком скриптов стал полноценный лисп (host CL), а не DSL на типах или еще какой (у команты THIRTEEN это была вообще пачка текстовых файлов с внешним интерпретатором).
  • В скриптах стало возможно "заглядывать в реальный мир". Тоесть, не просто:
    ОТЛЕЧИТЬ СЛОТОМ 0 СЛОТ 1 НА 2000;
    АТАКОВАТЬ СЛОТОМ 1 ВРАЖЕСКИЙ СЛОТ 255 НА 12000;
    а
    ОТЛЕЧИТЬ СЛОТОМ 0 СЛОТ 1 НА [сколько там не хватает чтоб убить 10k hp врагу];
    АТАКОВАТЬ СЛОТОМ 1 ВРАЖЕСКИЙ СЛОТ [какой там у него на данный момент самый борзый] НА [сколько там у него сейчас жизней];
  • Стало возможным временно приостанавливать один скрипт, чтобы выполнить другой (например, когда нужно срочно воскресить свой слот, или добить "единичку" у врага, или еще что-то). Соответственно, после к приостановленному скрипту можно спокойно возвращаться.
  • Сами скрипты при этом получили возможность мониторить свои слоты и слоты врага, прикидывая, не получится ли утащить частично готовое число через get или copy, чтобы не строить его самому.


В целом же, я своим выступлением доволен. Лисп показал себя в данной задаче, с одной стороны, просто потрясающе (REPL, символы, почти 1:1 маппинг предметной области напрямую в язык), с другой -- в режиме острой нехватки времени код у меня вышел крайне кривой и вообще write-only. Ну это и черт бы с ним, благо я участвовал соло без команды.

Так что вот. На следующий год попробую поиграть в команде, чтобы за счет мозгов напарников можно было компенсировать свой тупизм :)
Tags: common lisp, contest, icfp, icfpc, lisp, ltg, report
Subscribe
  • Post a new comment

    Error

    default userpic

    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.
  • 5 comments