среда, 22 июня 2011 г.

Lambda: the Gathering - поиграть штангой в карты

На прошедшем ICFPC авторы предложили мозговыносящую задачу, впрочем, как и в прошлые годы. Хотя, в этом году неплохое преимущество было у штангистов.

По формату этот ICFPC напоминал Google AI Challenge (вероятно, оттуда они и потырили часть идеи).

Описание задачи.

Предлагается написать бота, который будет сражаться с другими ботами турнирным методом. Боты играют попарно и ходят по-очереди. У каждого игрока имеется 256 слотов и фиксированный набор карт. Каждый слот имеет поле и очки жизней (хит-поинты). Поле слота может содержать либо целое число от 0 до 65535, либо функцию. Хит-поинты слота могут иметь значение от -1 до 65535. Слот считается живым, если его хит-поинты больше нуля. В начале матча каждый слот инициализируется тождественной функцией и 10 000 хит-поинтами.

На каждом ходу игрок может выполнить одно из двух действий: 'левое' либо 'правое'. Левое действие применяет заданную карту (функцию) к полю заданного слота. Правое применяет поле слота (содержащее функцию) к карте. Действие завершается ошибкой, если применяемая карта или поле не являются функцей, или заданный слот мертв.

Ход завершается, если происходит ошибка, если количество применений функций в результате левых или правых действий (включая их самих) превысит 1000 (фактически, это ограничение глубины стека виртуальной машины), или если применение завершается корректно без превышения этого лимита. В последнем случае полю слота присваивается полученное значение, а во всех других случаях оно перезаписывается в тождественную функцию. Все побочные эффекты, произведенные применениями функций, не откатываются, даже если применение завершилось аварийно.


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

Карты

Дан следующий набор карт.
  • Карта “I” - тождественная функция.
  • Карта “zero” - целое число 0 (не функция).
  • Карта “succ” - функция, принимающая аргумент n и возвращающая n+1, если n<65535 (или 65535, если n=65535). Возвращает ошибку, если n - не целое число.
  • Карта “dbl” - функция, принимающая аргумент n и возвращающая n*2, если n<32768 (или 65535, если n>=32768). Возвращает ошибку, если n - не целое число.
  • Карта “get” - функция, принимающая аргумент i и возвращающая значение поля i-го слота игрока-зашитника, если этот слот жив. Возвращает ошибку, если i - некорректный номер слота, или слот мертв.
  • Карта “put” - функция, принимающая (неиспользуемый) аргумент и возвращающая функцию #'identity.
  • Карта "S" - S-комбинатор λf.λg.λx.fx(gx).
  • Карта "K" - K-комбинатор λx.λy.x.
  • Карта "inc" - увеличивает на 1 хит-поинты слота защитника, если слот жив и количество хит-поинтов не привысит допустимого лимита.
  • Карта "dec" - увеличивает на 1 хит-поинты слота противника, если слот жив.
  • Карта "attack" - функция, принимеющая аргумент i и возвращающая другую функцию, которая (будучи применена) примет другой аргумент j и возвратит еще одну функцию, которая (будучи применена) примет аргумент n и уменьшит на n*9/10 хитпоинты (255-i)-го слота противника, при этом уменьшит также и хитпоинты атакующего j-го слота на n, после чего возвратит тождественную функцию.
  •  Карта "help" - действует похожим образом, но, вместо уменьшения жизней слота противника на n*9/10, увеличивает количество жизней слота защитника на n*11/10.
  • Карта "copy" - функция от i, которая возвращает функцию от j, которая копирует содержимое (255-i)-го слота притивника в поле j-го слота защитника.
  • Карта "revive" - функция, которая оживляет слот зашитника, давая ему 1 хит-поинт.
  • Карта "zombie" - функция от i, которая возвращает функцию от x, которая запишет x в (255-i)-й слот противника, если этот слот мертв, устанавливает его хит-поинты в -1 и возвращает тождественную функцию.
Непосредственно перед началом каждого хода игрока функция в поле каждого слота с хит-поинтами -1 автоматически применяется к тождественной функции начиная с первого мертвого слота до конца по возрастающей. При каждом из таких автоматических применений происходит ошибка. если поле содержит не функцию, или количество применений функции привысило 1000. Если возникает ошибка, то слот перезаписывается тождественной функцией, а хитпоинты слота устанавливаются в 0.

Кроме того, во время такого автоматического применения эффекты четырех карт изменяются:
  • Эффекты карт “inc” и "dec" меняются между собой.
  • Третья функция в карте “attack” увеличивает, а не уменьшает хит-поинты атакуемого слота.
  • Третья функция в карте “help” уменьшает, а не уменьшает хит-поинты подлечиваемого слота.
Такое автоматическое применение позволяет делать нетривиальные вещи с помощью зомбей.

Виртуальная машина

Первое, что необходимо было сделать - написать виртуальную машину, которая симулировала бы состояние обоих игроков. Матчи велись отдельной спарринг-программой, которая принимала от ботов через stdin три значения. Так, "1 dbl 10" соответствует левому применению карты dbl к десятому слоту, а "2 zero 0" - правому применению слота 0 к карте zero. Это означает, что простейший бот мог просто посылать одну и ту же команду на каждом ходу, но для сколько-ниудь осмысленных действий необходимо было знать текущее состояние слотов.

На написание первого приближения виртуальной машины у нас ушел весь первый день. К сожалению, мы долго тупили, проникаясь укуренностью остальной части задачи. Целый день на симулятор - это оказалось слишком много.

Собственно, штанга

В середине первого дня в команду пришел еще один участник, который что-то соображал в комбинаторной логике. И это было очень здорово, потому как, чтобы натравить одного зомби, пришлось бы строить такую функцию: S(K(S(K(zombie(zero)(1)))(get)))(succ)(zero), а это уже целое заклинание некромантии.

К концу второго дня стало ясно в общих чертах, как нужно сочетать карты с помощью SKI-комбинаторов, чтобы получать тот или иной эффект. К восьми часам утра я таки запостил на тестовый сервер примитивного бота, который атаковал всех по-очереди, пока не заканчивались хит-поинты, после чего я пошел спать.

Как ни странно, даже такой тупой бот выиграл бот 16 из 23 матчей, но еще в трех матчах он нарушил спецификацию и был дисквалифицирован. Это означало, что где-то в симуляторе были ошибки. Перспектива шерстить весь код на наличие несоответствий была безрадостной, но куда деваться.


Третий день стало понятно, что хорошие места в турнирной таблице нам не светят, потому как в конфе icfpc@cjr пробегали понты типа "я размочил все слоты за 500 ходов", а мы тогда знали, как убить все слоты за отведенные 100 000 ходов. К концу соревнования довольно результативно полистали код симулятора на предмет ошибок и оформили минимально вменяемую стратегию бота, после чего засабмитили на официальный и тестовый серверы и пошли спать. Всех ошибок в симуляторе мы обнаружить не смогли, но до дисквалификации на тестовом сервере он смог выиграть 12 из 42 матчей (к тому времени соперники стали умнее).


Итоговый бот


Виртуальная машина интерпретировала операции в последовательности инструкций, которые одна за другой передавались спарринг-программе. Одна операция могла преобразовываться в много или очень много инструкций. Серьезную проблему представляло получение больших чисел, т.к. для этой цели были доступны только карты zero, succ и dbl. Так, для записи числа 8 в слот 3 генерировалась следующая очередь:

1  put  3    ;; #'identity
2  0    zero ;; 0
1  succ 3    ;; 1
1  dbl  3    ;; 2
1  dbl  3    ;; 4
1  dbl  3    ;; 8


Доступ к слотам противника осуществлялся в обратном порядке, и, чтобы атаковать его нулевой слот, нужно было хранить в одном из слотов число 255. Первые слоты самые ценные, но и убить их наиболее трудно, потому что номер слота приходится "набирать" последовательным применением succ и dbl в определенном порядке, а это лишние ходы. Поэтому было выделено слотов-хранилищ, которые были своего рода кешем, позволяющим использовать имеющиеся числа повторно. Три слота-хранилища были расположены вначале, т.к. к ним наиболее быстрый доступ, а противнику их сложнее всего убить. Тем не менее, в начале каждого хода проверялось, живы ли эти слоты, и если они какой-либо из них был мертв, текущая очередь команд прерывалась, создавалась новая очередь, применяющся карту revive, а по ее завершению начиналось оживление нового слота, либо возвращалась прерванная очередь. За одну нашу атаку бот снимал с противника 3686 хит-поинтов, но при этом сам терял 4096 хит-поинтов. Если слот противника умирал, то значение слота-хранилица увеличивалось на 1, и атаковался следующий слот. Когда наши хит-поинты подходили к концу, генерировалась очередь, за один ход многократно применяющая карту inc. Полноценную рекурсию сделать не получилось, но многократное удвоенное действие позволило за один ход наращивать 1000 хит-поинтов (больше нельзя, но это тоже неплохо). Когда силы бота восстанавливались, то он снова переходил к атаке.


Вообще говоря, суть конкурса ICFPC в том, что авторы в игровой форме ставят сложные задачи так, чтобы знание предметной области было не обязательным (хотя и желательным). Короче говоря, мы слили, хотя и не так позорно, как в прошлом году. Не помог нам даже великий и славный common lisp (хотя и очень облегчил задачу, потому как жаберы и сиплюсплюсники страшно матерились, и это понятно). В целом, очень интересная задача, заставляет шевелить даже затекшие мозги. Код финального сабмишна, если вдруг кому интересно, лежит по адресу http://lisper.ru/files/icfpc/skobochka.tar.gz


Спасибо всем участникам (turtle, gltronred, laser123, dmitry_vk).


ЗЫ. По завершении конкурса авторы написали, что картинки (на сайте кроме карт были еще две картинки) не так просты, как кажется. Первую картинку можно полуить из второй, а вторую из первой:

java -jar new_books.png > lambda.png
java -jar lambda.png > new_books.png

Вот уж действительно боевые человекоподобные японцы :)

Перевод книги ANSI Common Lisp, #2

К сожалению, выпуск перевода затягивается издательством на неопределенный срок из-за серьезных финансовых проблем. Короче говоря, они на грани банкротства.

Если их трудности утрясутся, то ожидать выпуска книги можно в середине осени. Если им таки настанет крышка, то доработаем и издадим сами, вопрос с правообладанием как-нибудь разрешим.