Пау-чок
В начале июня прошло международное соревнование программеров ICFP Contest 2011, в котором я пытался принять участие. Хочется поделиться впечатлениями =)
Не буду говорить о том, что такое ICFP Contest - об этом можно почитать, например, тут. Скажу только, что задания в нём обычно очень увлекательны и обставлены так, что их приятно и интересно выполнять =) Этот год не был исключением =)
Задание и всё остальноеЗадание
И вот, собственно, задание. Оно описывает правила игры Lambda: The Gathering (привет, MTG! =) ). Целью участников является написание программы, которая бы в эту игру играло... и выигрывало =) Выигрывало у других программ, написанных другими участниками.
Суть игры вот в чём. Есть два игрока. У каждого по 256 слотов, нумеруемых от 0 до 255. Слот имеет такие параметры как "жизни" и "значение". "Жизни" могут принимать целочисленное значение от -1 до 65535, "значением" может быть целое число от 0 до 65535 либо некая функция. Слот считается мёртвым, если его жизни равны 0 или -1. У каждого игрока есть неограниченное количество карт, описанных ниже.
Игроки по очереди играют свои карты. Причём каждый игрок может выбрать, сыграть слот на карту (т.е. применить функцию слота к катре) или сыграть карту на слот (т.е. применить функцию карты к значению слота). Что это значит станет более понятно ниже.
Карты
Задание (продолжение)
Итак... Игроки по очереди играют свои карты. Каждый игрок может выбрать, сыграть слот на карту или сыграть карту на слот. В результате получаем некототорую функцию. Если мы функцию не получаем (т.е. например, играем слот, значение которого равно "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). Если кому-то интересно, чтобы продолжение было опубликовано в этом сообществе - прошу оставить об этом коммент.
Не буду говорить о том, что такое ICFP Contest - об этом можно почитать, например, тут. Скажу только, что задания в нём обычно очень увлекательны и обставлены так, что их приятно и интересно выполнять =) Этот год не был исключением =)
Задание и всё остальноеЗадание
И вот, собственно, задание. Оно описывает правила игры Lambda: The Gathering (привет, MTG! =) ). Целью участников является написание программы, которая бы в эту игру играло... и выигрывало =) Выигрывало у других программ, написанных другими участниками.
Суть игры вот в чём. Есть два игрока. У каждого по 256 слотов, нумеруемых от 0 до 255. Слот имеет такие параметры как "жизни" и "значение". "Жизни" могут принимать целочисленное значение от -1 до 65535, "значением" может быть целое число от 0 до 65535 либо некая функция. Слот считается мёртвым, если его жизни равны 0 или -1. У каждого игрока есть неограниченное количество карт, описанных ниже.
Игроки по очереди играют свои карты. Причём каждый игрок может выбрать, сыграть слот на карту (т.е. применить функцию слота к катре) или сыграть карту на слот (т.е. применить функцию карты к значению слота). Что это значит станет более понятно ниже.
Карты
| 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 вообще не используется | < | /tr>
| 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). Если кому-то интересно, чтобы продолжение было опубликовано в этом сообществе - прошу оставить об этом коммент.
@темы: Computer Science, Точка зрения
-
-
02.10.2011 в 13:28