Программирование змеи

Игра представляет собой пошаговое сражение от двух до четырех роботов-змей на клеточном поле. Для победы змеи должны атаковать противников, откусывая им хвосты, и, по возможности, избегать ответных атак. Бой заканчивается, если осталась только одна змея, съевшая всех соперников, если ни одна змея не может сделать ход или если истек лимит ходов, отпущенных на бой.

Змеи состоят из двух или более сегментов трех типов: голова, тело (ноль, один или несколько сегментов) и хвост. Каждый сегмент занимает одну клетку поля. На каждом шаге все змеи поочередно (в случайном порядке) передвигаются на одну клетку, если эта клетка свободна или в ней находится чей-нибудь хвост (исключение: змея не может ходить в клетку, занятую своим хвостом, если она состоит только из головы и хвоста, т. е. она не может развернуться на месте). Если змея передвигается на клетку, занятую хвостом противника, она откусывает этот хвост. В результате длина атакованной змеи уменьшается на одну клетку, а длина атакующей, соответственно, увеличивается. Если от атакованной змеи остается только голова, эта голова превращается в хвост, и змея считается съеденной. Если рядом с головой змеи нет ни свободных клеток, ни хвостов, то змея пропускает свой ход (это единственная ситуация, допускающая пропуск хода). Перед началом боя все змеи имеют одинаковую длину. По окончании боя каждой участнице начисляются очки в зависимости от ее итоговой длины. Разумеется, чем больше очков — тем лучше.

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

  • пустая клетка;
  • граница поля (клетка, лежащая за пределами поля);
  • тело своей змеи;
  • хвост своей змеи;
  • голова противника (любого);
  • тело противника (любого);
  • хвост противника (любого).

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

Шаблон может иметь модификатор НЕ, инвертирующий набор элементов — например, набор «голова, тело или хвост противника» с этим модификатором означает «все, кроме головы, тела или хвоста противника» (т. е. пустая клетка, граница, свое тело или свой хвост). Каждый шаблон входит в одну из нескольких И-групп либо ИЛИ-групп. И-группа требует, чтобы все шаблоны, входящие в нее, совпали с элементами на игровом поле. ИЛИ-группа требует совпадения хотя бы одного шаблона. Помимо указанных шаблонов карта обязательно требует наличие специального шаблона «голова своей змеи» в любой клетке. Он указывает положение головы змеи на поле, а направление взгляда головы указывает, в каком направлении должна двигаться змея в данной ситуации. Каждая карта может содержать текстовое описание ситуации. Программа так же может содержать описание.

При анализе карты генерируются восемь вариантов, представляющих 4 поворота × 2 отражения исходной карты. Все карты пронумерованы, номер задает порядок проверки карт. При анализе ситуации происходит следующее:

  1. Определяются возможные направления движения. Если возможных ходов нет или есть только один ход, то дальнейший анализ не производится.
  2. Выбирается первая карта в программе, генерируются ее варианты, соответствующие возможным направлениям движения (по два варианта на направление). Каждый вариант карты сверяется с игровым полем. Вариант считается корректным, если с элементами на поле совпали все шаблоны хотя бы одной И-группы и хотя бы по одному шаблону из каждой ИЛИ-группы. Если не нашлось ни одного корректного варианта, то анализируется следующая карта программы. Если ни для одной карты не нашлось корректных вариантов, то выбирается случайным образом один из допустимых ходов.
  3. Ход считается корректным, если для него есть хотя бы один корректный вариант. Если корректный ход только один, то змея делает этот ход, анализ на этом заканчивается. Если корректных ходов больше одного, то каждый из них оценивается по количеству и «качеству» совпавших шаблонов, выбирается ход, получивший максимальную оценку. Если максимальную оценку получили два или три хода, то ход выбирается из победителей случайным образом. Оценка хода равна сумме оценок соответствующих вариантов. Некорректный вариант имеет оценку 0 баллов. Оценка корректного варианта равна сумме оценок совпавших шаблонов. Оценка шаблона — семь баллов минус количество элементов, которым может соответствовать шаблон. Примеры:
    • шаблон «хвост противника» — 1 возможный элемент, 6 баллов;
    • шаблон «не хвост противника» — 6 элементов, 1 балл;
    • шаблон «голова, тело или хвост противника» — 3 элемента, 4 балла.

Ограничения (обсуждаемо):

  • количество карт в программе: от 1 до 9;
  • размер карты: 7×7 клеток;
  • количество И-групп: 4;
  • количество ИЛИ-групп: 4;
  • количество пользовательских наборов элементов на программу: 4.
 
projects/snakes/prog.txt · Последние изменения: 2012/11/21 23:09 От AVA12
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki