ICFPC'11: миниотчет
Jun. 22nd, 2011 02:47 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonВ минувшие выходные прошло ежегодное 72-часовое соревнование ICFP Contest. В этом году его организовывали японцы (судя по выложенному ими бинарнику, пишущие на окамле). На мой взгляд, задание получилось очень хорошим, лучше нескольких предыдущих (2008-2010). Условие повторять не буду, его можно прочитать в оригинале на английском c красивыми картинками или в подробном пересказе по-русски.
К огранизации японцы тоже подошли грамотнее предшественников: чтобы обезопасить себя от падений официального сервера, задействовали гугловские сервисы - blogger для вывешивания условия и spreadsheets для приема ссылок на решения. Сами решения скачивались уже после контеста и теперь неспеша будут запускаться и сражаться.
1. Как это было.
Первую часть времени я эффективно прокрастинировал, а вторую успешно тупил. Несмотря на это удалось сделать и отправить бота, который побеждает случайных оппонентов немного чаще, чем проигрывает (95 побед из 156 дуэлей на тестовом сервере со зрелыми ботами).
2. Как работает мой бот.
Во дни сомнений, во дни тягостных раздумий о судьбах моей... в общем, в те редкие моменты, когда нет готовой микропрограммы (последовательности команд) для исполнения, и нужно думать, бот оценивает обстановку и выбирает один из режимов работы. Режимов четыре: Grow, Fire, Protect и Defend.
Если живых слотов у нас осталось меньше 50, значит нас сильно бьют, и хватит уже изображать из себя героя, надо спасаться - это режим Defend. В этом режиме он занимается только тем, что оживляет погибшие слоты в порядке возрастания стоимости действия (числа ходов).
В самом начале размышлений над стратегией я нарисовал такую картинку:
Это количество ходов, необходимых для построения числа от 0 до 255 - номера слота. Другим цветом - оно же для (255-j), т.е. стоимость набора номера этого слота для врага, т.к. ему нужно набирать 255-j чтобы попасть в мой слот j. При старте бот вычисляет такую табличку и сортирует ее, получая номера слотов в порядке увеличения сложности их набора. Эту последовательность он потом везде активно использует.
Если живых слотов не меньше 50, то бот накапливает энергию, после чего либо атакует врага, либо наращивает защиту своих активных слотов. Выбирается живой слот g с минимальной ценой набора (если все живы, это слот 0). Если в нем энергии меньше 50000, то бот переходит в режим Grow - выращивания. В этом режиме он собирает в отдельном слоте цикл с командой help g g n, где g - номер слота, в котором растим энергию, а n - аккуратно выбранное количество энергии (меньше v[g] и кратное 512 обычно). Но цикл этот не достраивается до конца - последняя команда не вводится. В результате получается заготовка, которую можно применять несколько раз подряд, а не строить каждый раз заново. Когда такая заготовка готова, в слоте g делается ее копия (через get i) и вводится последняя команда, запускающая цикл на исполнение. Цикл за один ход увеличивает энергию слота в два с лишним раза. Повторный его запуск, благодаря сохраненной заготовке, делается очень быстро. Это позволяет наращивать энергию довольно хорошими темпами. Еще момент: в команде help g g n значение n меняется чаще, поэтому когда стоимость построения help g g больше, чем у get i (где i - номер слота с еще одной заготовкой), то help g g тоже строится в отдельном слоте, а потом просто оттуда копируется при построении цикла. Это позволяет ускорить построение заготовки цикла, когда g > 0.
Когда энергии в слоте g не меньше 50000, бот либо атакует врага (Fire), либо защищает используемые слоты (Protect). Выбор между атакой и защитой делается псевдослучайно с вероятностью перехода к защите 1/4.
В режиме атаки из живых слотов врага, которых можно убить с имеющейся энергией в g, выбирается слот с наименьшей энергией, а если таких несколько, то из них с наиболее простым номером (255-j). Сила атаки (третий параметр в attack i j n) выбирается такой, чтобы слот врага убился, наш остался жив, а значение n было наиболее дешевым в наборе с учетом заданных ограничений. Это позволяет сэкономить несколько ходов.
В режиме защиты (Protect) из используемых (под заготовки) слотов выбирается слот с наименьшей энергией и, если в нем энергии меньше 59000 (количество, позволяющее выдержать атаку максимальной силы), ему передается около половины энергии из слота g. Если защищать некого (все уже защищены), то бот переходит в режим атаки.
3. О реализации.
C января месяца ничего не писал на окамле, и тут остро почувствовал, какое же это удовольствие! При реализации модели игры - интерпретатора комбинаторного исчисления, где помимо обычный S,K и I есть еще кучка с побочными эффектами - очень пригодился паттерн-матчинг:
А для организации общего процесса, где ходы по очереди делают игроки, каждый из которых может быть человеком (ввод с stdin в ответ на осмысленный prompt), врагом (ввод с stdin, но без prompt'a) или ботом с состоянием, оказались очень кстати окамловские объекты.
4. Сабмит.
Рождение бота проходило медленно и со скрипом, описанный выше был готов где-то часов за 7 до конца контеста. Были еще мысли по улучшению, но локальное тестирование показало, что в нем баг - цикл работал только в нулевом слоте. Часов за 5 до конца я кажется даже понял, почему это так. Долго пытался придумать замену, но придумывались лишь такие конструкции, которые я не умел строить в одном слоте, а строить подвыражения в другом слоте и копировать в основной мне почему-то не нравилась идея. В итоге за полтора часа до конца было решено просто добавить проверку "если не в нулевом слоте, то не использовать цикл". После этого лишь я стал готовить программу к запуску с сервером организаторов, тут к счастью проблем не возникло. За час до конца контеста я запустил виртуалку с линуксом (до этого все делалось в в винде) и стал собирать решение там. Окамл там уже был установлен, со сборкой проблем не возникло. За 15 минут до конца засабмитил информацию о решении на страничке организаторов, причем ссылку дал еще несуществующую: консольный ftp отправлять файл на мой сервер отказывался, а замену ему я быстро найти не смог. Потом кое-как отправил себе архив с решением и выложил таки у себя за пару минут до конца контеста. Успел. Команда Dee_Mon в списке скачанных японцами решений присутствует.
5. Бонус.
А ведь птицы на карточках были неспроста - введите в гугле "combinator birds" и узрите.
К огранизации японцы тоже подошли грамотнее предшественников: чтобы обезопасить себя от падений официального сервера, задействовали гугловские сервисы - blogger для вывешивания условия и spreadsheets для приема ссылок на решения. Сами решения скачивались уже после контеста и теперь неспеша будут запускаться и сражаться.
1. Как это было.
Первую часть времени я эффективно прокрастинировал, а вторую успешно тупил. Несмотря на это удалось сделать и отправить бота, который побеждает случайных оппонентов немного чаще, чем проигрывает (95 побед из 156 дуэлей на тестовом сервере со зрелыми ботами).
2. Как работает мой бот.
Во дни сомнений, во дни тягостных раздумий о судьбах моей... в общем, в те редкие моменты, когда нет готовой микропрограммы (последовательности команд) для исполнения, и нужно думать, бот оценивает обстановку и выбирает один из режимов работы. Режимов четыре: Grow, Fire, Protect и Defend.
Если живых слотов у нас осталось меньше 50, значит нас сильно бьют, и хватит уже изображать из себя героя, надо спасаться - это режим Defend. В этом режиме он занимается только тем, что оживляет погибшие слоты в порядке возрастания стоимости действия (числа ходов).
В самом начале размышлений над стратегией я нарисовал такую картинку:
Это количество ходов, необходимых для построения числа от 0 до 255 - номера слота. Другим цветом - оно же для (255-j), т.е. стоимость набора номера этого слота для врага, т.к. ему нужно набирать 255-j чтобы попасть в мой слот j. При старте бот вычисляет такую табличку и сортирует ее, получая номера слотов в порядке увеличения сложности их набора. Эту последовательность он потом везде активно использует.
Если живых слотов не меньше 50, то бот накапливает энергию, после чего либо атакует врага, либо наращивает защиту своих активных слотов. Выбирается живой слот g с минимальной ценой набора (если все живы, это слот 0). Если в нем энергии меньше 50000, то бот переходит в режим Grow - выращивания. В этом режиме он собирает в отдельном слоте цикл с командой help g g n, где g - номер слота, в котором растим энергию, а n - аккуратно выбранное количество энергии (меньше v[g] и кратное 512 обычно). Но цикл этот не достраивается до конца - последняя команда не вводится. В результате получается заготовка, которую можно применять несколько раз подряд, а не строить каждый раз заново. Когда такая заготовка готова, в слоте g делается ее копия (через get i) и вводится последняя команда, запускающая цикл на исполнение. Цикл за один ход увеличивает энергию слота в два с лишним раза. Повторный его запуск, благодаря сохраненной заготовке, делается очень быстро. Это позволяет наращивать энергию довольно хорошими темпами. Еще момент: в команде help g g n значение n меняется чаще, поэтому когда стоимость построения help g g больше, чем у get i (где i - номер слота с еще одной заготовкой), то help g g тоже строится в отдельном слоте, а потом просто оттуда копируется при построении цикла. Это позволяет ускорить построение заготовки цикла, когда g > 0.
Когда энергии в слоте g не меньше 50000, бот либо атакует врага (Fire), либо защищает используемые слоты (Protect). Выбор между атакой и защитой делается псевдослучайно с вероятностью перехода к защите 1/4.
В режиме атаки из живых слотов врага, которых можно убить с имеющейся энергией в g, выбирается слот с наименьшей энергией, а если таких несколько, то из них с наиболее простым номером (255-j). Сила атаки (третий параметр в attack i j n) выбирается такой, чтобы слот врага убился, наш остался жив, а значение n было наиболее дешевым в наборе с учетом заданных ограничений. Это позволяет сэкономить несколько ходов.
В режиме защиты (Protect) из используемых (под заготовки) слотов выбирается слот с наименьшей энергией и, если в нем энергии меньше 59000 (количество, позволяющее выдержать атаку максимальной силы), ему передается около половины энергии из слота g. Если защищать некого (все уже защищены), то бот переходит в режим атаки.
3. О реализации.
C января месяца ничего не писал на окамле, и тут остро почувствовал, какое же это удовольствие! При реализации модели игры - интерпретатора комбинаторного исчисления, где помимо обычный S,K и I есть еще кучка с побочными эффектами - очень пригодился паттерн-матчинг:
let rec apply a b = incr ac; if !ac > 1000 then failwith "too many applications" else match a,b with | I, x -> x | Get, N i -> chk_index i "get i"; f.(i) | Put, _ -> I | S0, x -> S1 x | S1 x, y -> S2(x, y) | S2(f, g), x -> let h = apply f x in let y = apply g x in apply h y | K0, x -> K1 x | K1 x, y -> x ...
А для организации общего процесса, где ходы по очереди делают игроки, каждый из которых может быть человеком (ввод с stdin в ответ на осмысленный prompt), врагом (ввод с stdin, но без prompt'a) или ботом с состоянием, оказались очень кстати окамловские объекты.
4. Сабмит.
Рождение бота проходило медленно и со скрипом, описанный выше был готов где-то часов за 7 до конца контеста. Были еще мысли по улучшению, но локальное тестирование показало, что в нем баг - цикл работал только в нулевом слоте. Часов за 5 до конца я кажется даже понял, почему это так. Долго пытался придумать замену, но придумывались лишь такие конструкции, которые я не умел строить в одном слоте, а строить подвыражения в другом слоте и копировать в основной мне почему-то не нравилась идея. В итоге за полтора часа до конца было решено просто добавить проверку "если не в нулевом слоте, то не использовать цикл". После этого лишь я стал готовить программу к запуску с сервером организаторов, тут к счастью проблем не возникло. За час до конца контеста я запустил виртуалку с линуксом (до этого все делалось в в винде) и стал собирать решение там. Окамл там уже был установлен, со сборкой проблем не возникло. За 15 минут до конца засабмитил информацию о решении на страничке организаторов, причем ссылку дал еще несуществующую: консольный ftp отправлять файл на мой сервер отказывался, а замену ему я быстро найти не смог. Потом кое-как отправил себе архив с решением и выложил таки у себя за пару минут до конца контеста. Успел. Команда Dee_Mon в списке скачанных японцами решений присутствует.
5. Бонус.
А ведь птицы на карточках были неспроста - введите в гугле "combinator birds" и узрите.
