Мнения, высказанные здесь, отражают мои личные взгляды. И мнения и взгляды со временем могут меняться.
среда, 7 мая 2008 г.
Итоги турнира программ
Для меня же основной итог соревнования таков: мы можем справляться задачами такого уровня сложности.
понедельник, 28 апреля 2008 г.
Турнир программ
Сроки проведения турнира: начало: суббота, 26 апреля, в 10:20; окончание: четверг, 1 мая, в 14:00.
Поддерживаемые языки программирования:
- Java;
- Pascal;
- C++.
Правила игры SnakeCore
1. Общее описание игры
В SnakeCore игроку предстоит управлять кибернетической змеёй (будем условно называть её питоном). Под управлением игрока питон может ползать по плоскому игровому миру, собирать блоки (еду), атаковать чужаков и защищаться от чужих атак. Игроки ходят по очереди. Цель игры – набирать очки.Каждая игра ограничена определённым числом ходов. Побеждает тот, у кого в конце игры оказывается больше игровых очков, чем у соперников.
Питон состоит из головы и туловища. Голова является основным элементом питона, она управляет его движением. Туловище питона представляет собой цепочку из связанных блоков. Последний блок в туловище питона называется хвостом.Игра происходит на квадратом поле, разбитом на клетки. Клетки считаются соседними, если они имеют общее ребро. Таким образом, все клетки, за исключением тех, которые примыкают к границе поля, имеют четырёх соседей.
За один ход голова питона может переместиться лишь на одну из соседних клеток от её текущей позиции. Когда голова питона перемещается на пустую клетку, всё туловище перемещается вслед за головой так, что первый блок туловища оказывается там, где раньше была голова, второй блок туловища оказывается там, где раньше был первый, и т. д. Клетка, на которой раньше находился хвост, оказывается пустой.Все блоки на игровом поле делятся на связанные и независимые. Связанным называется блок, который входит в состав одного из питонов. Независимыми называются блоки, не входящие в состав ни одного из питонов.
Если голова питона перемещается на клетку, в которой находится независимый блок, этот блок становится частью туловища питона. Голова змеи при этом перемещается на выбранную клетку, новый блок становится в клетку, где раньше была голова, остальные блоки в туловище питона остаются на месте. Таким образом, собирая новые блоки, питон увеличивает свою длину.Перемещение питона на клетку в которой находится связанный блок считается атакой. Атаковать можно других питонов, либо себя самого. Если голова питона перемещается на клетку, в которой находится связанный блок, это приводит к разрыву цепочки блоков в этом месте. Блоки, которые принадлежали атакованному питону, но находились после места разрыва, становятся независимыми. Атаковавшему питону начисляется столько очков, какова длина откушенной им у соперника части; кроме того, он присоединяет блок на который проходила атака к своему туловищу.
Блоки на игровом поле бывают двух видов: обыкновенные и энергетические. Если в теле питона есть энергетически блок, питон может использовать его для активации режима защиты (энергетический блок при этом исчезнет). Полученная защита действует в точности 10 ходов (считая ход, использованный для включения защиты) и выключается перед тем, как питон делает свой 11 ход. Защита, полученная от нескольких энергетических блоков, суммируется: если питон последовательно использует два энергетических блока, то он получает 20 ходов защиты. Оставшиеся в конце игры ходы защиты в следующий тур не передаются.Голова и хвост питона в любой момент времени остаются неуязвимыми. Если питон не активировал защиту, то все остальные его блоки могут быть атакованы. Если защита активирована, тело питона становится недоступным для атак (даже для него самого).
Кроме перечисленных выше типов игровых объектов, есть ещё специальный тип объектов – реактор. Питон, который находится возле реактора, может "сбросить" блоки своего туловища в этот реактор. В случае, если игрок принимает решение "сбросить свой хвост", голова питона остаётся на месте, но его туловище исчезает. За доставку блоков в реактор игрок получает n(n + 1)/2 очков, где n — длина туловища питона в момент сдачи.Последним правилом в игре является "закон сохранения массы и энергии": количество блоков на игровом поле всегда остаётся постоянным. Если блок (обычный или энергетический) был доставлен в реактор, то он затем вновь появляется в случайном месте игрового поля. Если энергетический блок был использован для включения защиты, он также вновь появляется на поле.
2. Описание игрового поля
Как уже отмечалось, игра происходит на квадратом поле, разбитом на клетки. Для каждой из клеток верно одно из утверждений:- Клетка является пустой.
- В клетке находится препятствие (стена).
- В клетке находится реактор.
- В клетке находится простой блок.
- В клетке находится энергетический блок.
- В клетке находится голова питона (игрок).
Каждый ход игрок принимает решение о действиях подчинённого ему питона. Игрок может применить к питону одно из следующих действий:
- Переместить голову питона на одну из соседних клеток (выделяются следующие направления: вверх, влево, вниз, вправо).
- Пропустить ход.
- Активировать защиту (при этом питон теряет один энергетический блок).
Попытка переместить питона на клетку с реактором приводит к тому, что питон сбрасывает принадлежащие ему блоки в реактор (и игрок получает очки). Голова питона при этом остаётся в той же позиции.
Невозможно переместить питона на клетку, в которой находится препятствие (стена) или голова другого питона; кроме того, нельзя переместиться на клетку, в которой находится блок, защищённый каким-либо питоном (если блок является хвостом, или если у атакуемого питона включена защита). Отметим отдельно, что если попытаться напасть на собственный хвост, то хвост «убежит» прежде, чем его атакуют.
Кроме того, питон не может выйти за границы игрового поля.
3. Описание протокола взаимодействия с тестирующей системой
Участник турнира должен предоставить своё решение жюри в виде исходного текста программы, написанного на одном из языков программирования (официально поддерживаются языки Java, Pascal, C++). При компиляции решения жюри предполагает получить один .exe файл, если решение написано на языке C++ или Pascal; либо серию из .class файлов (класс и его вложенные классы), если решение написано на языке Java.
При тестировании решение участника запускается в виде отдельного процесса. Для взаимодействия тестирующей системы с программой-игроком используется стандартный механизм потоков ввода/вывода (тех самых, которые обычно связаны с клавиатурой и дисплеем). В начале каждой игры тестирующая система создаёт новый процесс, в котором запускает игрока; программа-игрок не должна завершать свою работу самостоятельно.
После старта, программа-игрок начинает получать через стандартный поток ввода запросы. Все запросы устроены одинаково: в первой строке запроса содержится идентификатор запроса: "getName" или "getAction" (без кавычек).
Запрос getName не содержит никаких дополнительных данных и состоит из единственной строки с идентификатором. Ответ на такой запрос должен состоять из строки, содержащей имя игрока. Имя игрока может содержать произвольные символы (с ascii кодами >= 0x20), длина имени не должна превышать 32 байта.
Запрос getAction несёт информацию об игровой локации. Вторая строка запроса содержит единственное положительное число n – размер игрового поля. В следующих n строках содержатся данные о клетках игрового поля: i-й знак j-й строки описывает клетку игрового поля с координатами (i - 1, j - 1). Начало координат в левом верхнем углу. Таблица соответствия:
- 'W' – препятствие (стена);
- 'R' – реактор;
- 'b' – обыкновенный блок;
- 'e' – энергетический блок;
- 'p' – голова питона (игрок);
- иначе – пустая клетка.
Далее идут k строк, описывающие питонов, k – количество игроков на локации. Первым описывается питон текущего игрока.
Строка описания питона представляет собой набор чисел, разделённых пробелами. Первое число в строке – оставшееся количество ходов в режиме защиты у данного питона (0, если питон не защищён); второе число l – длина питона. Питон всегда имеет положительную длину. Далее идут l пар – координаты: первая пара чисел описывает координаты головы, и (l - 1) пара описывают координаты блоков тела. Последняя пара описывает хвост. Все координаты лежат в [0, n - 1]x[0, n – 1].
В ответ на запрос getAction игрок должен вывести в отдельной строке символ, указывающий на тип действия:
- 'U' – переместиться вверх;
- 'L' – переместиться влево;
- 'D' – переместиться вниз;
- 'R' – переместиться вправо;
- 'N' – пропустить ход;
- 'A' – активировать защиту.
Если питон не в состоянии выполнить указание игрока, например, если игрок попытается переместить его на клетку, в которой находится препятствие, то питон пропустит ход. Напомним, если игрок попытается переместить питона на клетку реактора, это приведёт к тому, что питон сбросит в реактор принадлежащие ему блоки.
Для того, чтобы уменьшить техническую сложность соревнования, участникам предоставляется реализация класса AreaInfo на языках Pascal и C++. В этом классе имеется набор методов для работы с игровой локацией. Реализацию AreaInfo, а также некоторых других вспомогательных классов, участники могут найти в файлах Snake.pas и Snake.h для Pascal и C++ соответственно. Копировать код классов в своё решение не обязательно, эталонные файлы Snake.pas и Snake.h будут доступны при компиляции на стороне жюри. Эти файлы, а также оболочку для проведения и просмотра игр “Полигон” можно найти на официальном сайте турнира (см. комплект участника).
Для того, чтобы упростить разработку решений на языке Java, участникам также предоставляется некоторый набор готовых инструментов. Решение участника на этом языке должно представлять собой класс, являющийся потомком класса Jbot (см. комплект участника). Информация об игровой локации будет доступна через интерфейс AreaInfo аналогичный реализованному для Pascal и С++.
Гарантируется, что на протяжении игры:
- размер игровой локации не изменяется;
- количество игроков остаётся постоянным (если игрок дисквалифицирован – он просто не может двигаться);
- между двумя последовательными запросами getAction остальные игроки делают не более одного хода.
4. Ограничения на программу-игрока
В решении участника запрещено:
- выполнять внешние программы или создавать новые процессы;
- использовать сетевые средства;
- работать с файловой системой;
- работать с внешними устройствами (принтером, звуковой картой и т. д.);
- создавать или работать с любыми GUI-элементами (окнами, диалогами и т. д.);
- выполнять любые другие действия, которые могут нарушить работу программного обеспечения соревнования.
Кроме того, решение участника должно быть корректным. Это включает в себя следующее:
- программа не должна пытаться завершить свой процесс;
- время ответа на первый запрос (как правило, это getName) не должно превышать 15 секунд;
- время ответа на последующие запросы не должно превышать 1 секунду;
- суммарное время вычислений в течении одной игры не должно превышать 2 минуты;
- программа не должна нарушать протокола взаимодействия.
понедельник, 7 апреля 2008 г.
Турнир программ
Необходимые подзадачи:
- связаться с организаторами Дмм;
- разработать инструментарий для проведения турнира;
- создать страничку проекта.
Разработка инструментария включает:
- разработка полигона игры;
- разработка API для игроков-ботов;
- разработка примеров игроков-ботов.