ICFPC 2011
Японская трава такая трава.
В этом году ежегодный контест в рамках конференции функциональных языков хостил университет Тохоку. Заданием было написать AI для игры - гибрида MtG и подвида лямбда-исчисления. Хорошее описание тут (может ещё будет их отчёт...).
Началось всё в ночь с четверга на пятницу (у нас было 4 утра). Один из товарищей по команде довольно точно предсказал что будет. долго боялись что не будет скореборда, но его сделали (и назвали неофициальным 8-) ).
Наша команда - BearsAteOurBrains. в следующем году если успею - возьму такое же название 8-)
пятница.
До восьми утра мы расклассифицировали карты, немного посмотрели как оно всё работает (никто ж раньше с SKI записью не работал...). в 9 утра я закоммитил идею использования зомби, которой в конце и воспользовался (я по логам svn проверил 8-) ), и пошел спать.
к моменту когда я проснулся, один товарищ уже полдня писал свой эмулятор, а второй - систему запуска скриптов на демомашине оргов. по результатам некоторых изысканий эмулятор был заброшен, а я стал писать свой (кстати, доотладил я его только после контеста 8-\ ). ближе к ночи собственно эмуль я закончил, и начали думать, что туда запихивать.
суббота.
параллельно отладке моего эмуля и написанию очень тупой стратегии шли разговоры за то, что и как надо делать. мой эмуль упорно отказывался запускаться под запускатором скриптов. товарищи сказали что пофиксят - и исчезли навсегда. я потихоньку ловил багов, думал за зомбей и за циклы. этой ночью перед сном я как раз придумал обе наработки вошедшие в финальный сценарий - улучшенный цикл на dec (S(dec)(S((get)(I)))) и как убить [255] слот за 30 тактов. были ещё идеи как кильнуть [0] за 43 такта и [255] за 56 подняв здоровье до неба - но от них пришлось отказаться.
воскресенье.
первую половину дня я тупил. 8-\
Я всё ещё надеялся, что товарищи вернутся и чем-нибудь помогут - и думал как ещё можно нагадить врагу.
когда я понял, что ждать без шансов - стал писать чуть более умную стратегию. Очень хотелось отвлечься и ещё немного попридумывать реализуемых гадостей - типа ядро зомби активирующее копи - но уже не было времени...
В результате получилось 3 блока и доп.условие: 1) 30 тактов на убить ячейку [255], 2) 25+<создание адреса(<15т))>+<создание размера(<15т если не использовался хил)> атака на произвольный слот через зомби (или, если там (1) - 1+<создание адреса> через dec) 3) если 255 слот оживили - убить через dec (2 такта) или "цикл+dec" (18 тактов) 4) доп. условием была жизнь слотов 0-2, т.е. если вдруг обнаруживалось что они мертвы, то алг пытался их поднять.
последний коммит пришелся на "за час до конца".
я уже знал, что в топ я никак не попадаю: моя стратегия убивала "не сопротивляющегося игрока" за ~22 тыс. тактов, в то время как уже в пятницу убивали всё за 1900, финальный вариант человека не использовавшего зомби (только циклы) - 700, а финальный вариант программы одного из топа - вообще за 190 тактов (использовалась идея совмещения цикла и зомби: зомби засылал цикл из heal(i++)(i++)(8К), и килял ~60 ячеек за запуск.)
Ошибка, кстати, была совершенно дурацкая: я не предполагал, что имеет смысл куда-то копировать оператор K без параметров - а вот выходит, имело смысл.
лучший результат официально сабмиченной версии: из 14 пусков 3 моих облома (дисквалификация), 9 побед, 2 поражения
текущий вариант версии без бага - 14 пусков, 10 побед, 1 ничья, 3 поражения.
Программящий народ, давайте уже в следующем году участвовать! Это напряжно и мозгосъедательно, но весело и туча адреналина, особенно когда понимаешь, насколько другие круче тебя. 8-)
В этом году ежегодный контест в рамках конференции функциональных языков хостил университет Тохоку. Заданием было написать AI для игры - гибрида MtG и подвида лямбда-исчисления. Хорошее описание тут (может ещё будет их отчёт...).
Началось всё в ночь с четверга на пятницу (у нас было 4 утра). Один из товарищей по команде довольно точно предсказал что будет. долго боялись что не будет скореборда, но его сделали (и назвали неофициальным 8-) ).
Наша команда - BearsAteOurBrains. в следующем году если успею - возьму такое же название 8-)
пятница.
До восьми утра мы расклассифицировали карты, немного посмотрели как оно всё работает (никто ж раньше с SKI записью не работал...). в 9 утра я закоммитил идею использования зомби, которой в конце и воспользовался (я по логам svn проверил 8-) ), и пошел спать.
к моменту когда я проснулся, один товарищ уже полдня писал свой эмулятор, а второй - систему запуска скриптов на демомашине оргов. по результатам некоторых изысканий эмулятор был заброшен, а я стал писать свой (кстати, доотладил я его только после контеста 8-\ ). ближе к ночи собственно эмуль я закончил, и начали думать, что туда запихивать.
суббота.
параллельно отладке моего эмуля и написанию очень тупой стратегии шли разговоры за то, что и как надо делать. мой эмуль упорно отказывался запускаться под запускатором скриптов. товарищи сказали что пофиксят - и исчезли навсегда. я потихоньку ловил багов, думал за зомбей и за циклы. этой ночью перед сном я как раз придумал обе наработки вошедшие в финальный сценарий - улучшенный цикл на dec (S(dec)(S((get)(I)))) и как убить [255] слот за 30 тактов. были ещё идеи как кильнуть [0] за 43 такта и [255] за 56 подняв здоровье до неба - но от них пришлось отказаться.
воскресенье.
первую половину дня я тупил. 8-\
Я всё ещё надеялся, что товарищи вернутся и чем-нибудь помогут - и думал как ещё можно нагадить врагу.
когда я понял, что ждать без шансов - стал писать чуть более умную стратегию. Очень хотелось отвлечься и ещё немного попридумывать реализуемых гадостей - типа ядро зомби активирующее копи - но уже не было времени...
В результате получилось 3 блока и доп.условие: 1) 30 тактов на убить ячейку [255], 2) 25+<создание адреса(<15т))>+<создание размера(<15т если не использовался хил)> атака на произвольный слот через зомби (или, если там (1) - 1+<создание адреса> через dec) 3) если 255 слот оживили - убить через dec (2 такта) или "цикл+dec" (18 тактов) 4) доп. условием была жизнь слотов 0-2, т.е. если вдруг обнаруживалось что они мертвы, то алг пытался их поднять.
последний коммит пришелся на "за час до конца".
я уже знал, что в топ я никак не попадаю: моя стратегия убивала "не сопротивляющегося игрока" за ~22 тыс. тактов, в то время как уже в пятницу убивали всё за 1900, финальный вариант человека не использовавшего зомби (только циклы) - 700, а финальный вариант программы одного из топа - вообще за 190 тактов (использовалась идея совмещения цикла и зомби: зомби засылал цикл из heal(i++)(i++)(8К), и килял ~60 ячеек за запуск.)
Ошибка, кстати, была совершенно дурацкая: я не предполагал, что имеет смысл куда-то копировать оператор K без параметров - а вот выходит, имело смысл.
лучший результат официально сабмиченной версии: из 14 пусков 3 моих облома (дисквалификация), 9 побед, 2 поражения
текущий вариант версии без бага - 14 пусков, 10 побед, 1 ничья, 3 поражения.
Программящий народ, давайте уже в следующем году участвовать! Это напряжно и мозгосъедательно, но весело и туча адреналина, особенно когда понимаешь, насколько другие круче тебя. 8-)