ICFP Contest 2011

[programming]

В начале июня прошло международное соревнование программеров ICFP Contest 2011, в котором я пытался принять участие. Хочется поделиться впечатлениями =)

Не буду говорить о том, что такое ICFP Contest - об этом можно почитать, например, тут. Скажу только, что задания в нём обычно очень увлекательны и обставлены так, что их приятно и интересно выполнять =) Этот год не был исключением =)

Задание и всё остальное

Задание
И вот, собственно, задание. Оно описывает правила игры Lambda: The Gathering (привет, MTG! =) ). Целью участников является написание программы, которая бы в эту игру играло... и выигрывало =) Выигрывало у других программ, написанных другими участниками.

Суть игры вот в чём. Есть два игрока. У каждого по 256 слотов, нумеруемых от 0 до 255. Слот имеет такие параметры как "жизни" и "значение". "Жизни" могут принимать целочисленное значение от -1 до 65535, "значением" может быть целое число от 0 до 65535 либо некая функция. Слот считается мёртвым, если его жизни равны 0 или -1. У каждого игрока есть неограниченное количество карт, описанных ниже.

Игроки по очереди играют свои карты. Причём каждый игрок может выбрать, сыграть слот на карту (т.е. применить функцию слота к катре) или сыграть карту на слот (т.е. применить функцию карты к значению слота). Что это значит станет более понятно ниже.

Карты
</tr>

1)Карта I
Карта I представляет собой тождественное отображение (identity function). Т.е. если она применяется к чему-либо, она возвращает то, к чему применяется. Короче, I(x)=x.
2)Карта zero
Карта zero представляет собой константу 0.
3)Карта succ
Карта succ принимает один целочисленный параметр n и возвращает n+1. Если полученное значение больше 65535, оно становится 65535. Если n - не число, возникает ошибка.
4)Карта dbl
Карта dbl принимает один целочисленный параметр n и возвращает n*2. Если полученное значение больше 65535, оно становится 65535. Если n - не число, возникает ошибка.
5)Карта get
Карта get принимает один целочисленный параметр i и возвращает значение i'го слота текущего игрока. Если этот слот мёртв или слота i вообще не существует (т.е. i>255 или i<0), возникает ошибка.
6)Карта put
Карта put принимает параметр x и возвращает функцию тождественного отображения I. Т.е. x вообще не используется
7)Карта S
Карта S принимает параметр f и возвращает функцию, которая принимает параметр g и возвращает функцию, которая принимает параметр x и... И тогда вот эта самая последняя функция делает вот что: 1. Если f - функция, то h=f(x), иначе возникает ошибка. 2. Если g - функция, то y=g(x), иначе - ошибка. 3. Если h - функция, то z=h(y), иначе - ошибка. 4. Возвращаем z в качестве результата. Казалось бы, ненужное пьяное шаманство. Однако же, это одна из самых полезных карт =) Вместе со следующей:
8)Карта K
Карта K принимает параметр x и возвращает функцию, которая принимает параметр y и возвращает значение x. Т.е. параметр y вообще не используется.
9)Карта inc
Карта inc принимает параметр i и если i'й слот текущего игрока жив, и у него жизни не на максимуме (65535), то увеличивает их на 1. Возвращает функцию I. Если i не число, либо i'го слота не существует - возникает ошибка.
10)Карта dec
Карта dec принимает параметр i и если (255-i)'й слот противника жив, то уменьшает его жизни на 1. Возвращает функцию I. Если i не число, либо i'го слота не существует - возникает ошибка.
11)Карта attack
Карта attack принимает параметр i и возвращает функцию, которая принимает параметр j и возвращает функцию, которая принимает параметр n и... 1. Если i - не число, если i'го слота не существует, если n - не число, или если у i'го слота жизней меньше, чем n, то возникает ошибка. 2. Иначе - значение жизней i'го слота текущего игрока уменьшается на n. 3. Если j - не число или (255-j)'го слота не существует, возникает ошибка. 4. Иначе, если (255-j)'й слот противника жив, то значение его жизней уменьшается на n*9/10, округлённое в меньшую сторону (если после этого значение жизней слота становится меньше 0, то оно устанавливается в 0). Если же слот мёртв, то ничего не делается. 5. В качестве результата возвращается I.
12)Карта help
Карта help, аналогично катре attack, принимает параметр i и возвращает функцию, которая принимает параметр j и возвращает функцию, которая принимает параметр n и... 1. Если i - не число, если i'го слота не существует, если n - не число, или если у i'го слота жизней меньше, чем n, то возникает ошибка. 2. Иначе - значение жизней i'го слота текущего игрока уменьшается на n. 3. Если j - не число или j'го слота не существует, возникает ошибка. 4. Иначе, если j'й слот текущего игрока жив, то значение его жизней увеличивается на n*11/10, округлённое в меньшую сторону (если после этого значение жизней слота становится больше 65535, то оно устанавливается в 65535). Если же слот мёртв, то ничего не делается. 5. В качестве результата возвращается I.
13)Карта copy
Карта copy принимает параметр i и возвращает значение i'го слота противника. Либо, если i не число или i'го слота не существует, возникает ошибка.
14)Карта revive
Карта revive принимает параметр i и если i'й слот текущего игрока мёртв, устанавливает его жизни в 1. Если он жив - не делает ничего. Но в любом случае катра возвращает функцию I. Либо, если i не число или i'го слота не существует, возникает ошибка.
15)Карта zombie
Карта zombie принимает параметр i и возвращает функцию, которая принимает параметр x и: 1. Если i не число или i'го слота не существует или у противника i'й слот жив - возникает ошибка. 2. Иначе значение i'го слота противника устанавливается в x, а его жизни устанавливаются в -1. 3. Возвращается функция I.

Задание (продолжение)
Итак... Игроки по очереди играют свои карты. Каждый игрок может выбрать, сыграть слот на карту или сыграть карту на слот. В результате получаем некототорую функцию. Если мы функцию не получаем (т.е. например, играем слот, значение которого равно "15" на какую-либо карту или играем карту "zero" к чему-либо), возникает ошибка.
Полученные в результате хода функции тут же вычисляются. Если в результате вычислений возникает ошибка или количество выполненных функций превышает 1000, в слот который игрался к карте или на котороый игралась карта, записывается I. Если же функция возвращает значение, то в слот записывается именно оно.
И ход переходит к другому игроку.

В начале хода игрока значение каждого его слота, чьи жизни равны -1, автоматически применяется к функции тождественного отображения I начиная с 0'го слота - и заканчивая 255'м. Если в результате применения возникает ошибка, осуществляется переход к следующему слоту. По окончании каждого применения в значение слота записывается I, а его жизни устанавливаются в 0.
В этой фазе хода эффект некоторых карт изменяется:
1. Карта inc уменьшает жизни i'го слота текущего игрока на 1 (если слот жив).
2. Карта dec увеличивает жизни i'го слота противника на 1 (если слот жив и жизни у него не на максимуме).
3. Третья функция карты attack увеличивает жизни j'го слота противника на 9/10*n если слот жив. Если жизни после этого превышают 65535, они устанавливаются в 65535.
4. Третья функция карты help уменьшает жизни j'го слота текущего игрока на 11/10*n если слот жив. Если жизни после этого становятся меньше 0, они устанавливаются в 0.

Игра заканчивается, когда у одного из игроков все слоты убиты, либо когда каждым игроком сыграно 100000 ходов. В любом случае, выигрывает тот, у кого выжило больше слотов. Если количество выживших слотов одинаково, то объявляется ничья.

Отличия от предыдущих соревнований
В этом году соревнование устраивалось университетом Тохоку (Япония). И японцы были в своём репертуаре =) В том смысле, что стереотип об их инопланетном разуме вполне подтвердился - просто прочитайте задание =)
Неприятным сюрпризом было то, что в этом году судьи в качестве результата принимали исключительно исполняемые программы. И выкладывать их надо было на сторонний сервер, откуда бы эти программы скачивались =\ Т.е. адекватно проверить свою прогу в боевых условиях возможности практически не было. "Практически" - потому, что был открыт тестовый сайт, куда можно было залить своё "творчество" - и через некоторое время узнать, что программа падает по неизвестной причине =(
Но, за неимением лучшего... Японцы и так на фоне Фукусимы и предшествующих событий сумели не зафейлть сам факт проведения контеста. Уже за это всё (и моё в том числе) нытьё по поводу "аааа, раньше было лучше!" просьба воспринимать исключительно как субъективный трындёж =)

Выполнение
И вот случилось! 17 июня, три ночи по Москве! Ура! Началось!
продолжение следует... Надеюсь, у меня руки дойдут до этого =) Я и так пост начал писать ещё в июне =)


Кросс-пост из моего дайрика ( O). Если кому-то интересно, чтобы продолжение было опубликовано в этом сообществе - прошу оставить об этом коммент.