Задача заочного тура

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

1. Правила игры

В игре принимают участие 2 игрока.

Игра ведется на прямоугольном поле, состоящем из клеток. Поле имеет размеры 17 (количество строк) на 26 (количество столбцов). Клетки делятся на 2 типа: проходимые и непроходимые (стенки). Каждая проходимая клетка принадлежит какому-либо игроку, и на ней находится гарнизон - армия, стоящая на этой клетке. Численность гарнизона выражается целым неотрицательным числом.

Игроки ходят поочередно, начиная с первого. Выигрывает игрок, захвативший всю проходимую территорию игрового поля.

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

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

Бой происходит следующим образом. Вначале в бой вступают гарнизон противника и наличная армия игрока.

Если гарнизон противника, умноженный на 3, больше наличной армии игрока, то в результате боя игрок теряет всю свою армию (она становится равной нулю), при этом гарнизон и наличная армия противника не изменяются.

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

В остальных случаях гарнизон уничтожается, а игрок теряет из своей армии ровно столько, какова была численность гарнизона.

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

Если после боя у игрока остается в наличии ненулевая армия, то игрок захватывает клетку противника, и она становится его клеткой. При этом на вновь захваченной клетке численность гарнизона становится равной нулю.

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

Каждые 25 ходов (то есть после каждого 25-го хода второго игрока) осуществляется прирост численности гарнизонов всех игроков на всех клетках. Гарнизон численностью

от 0 до 29 включительно увеличивается на единицу,

от 30 до 99 - на два,

от 100 до 299 - на три,

от 300 до 999 - на четыре,

от 1000 и выше - на пять.

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

позиция игрока (координаты на игровом поле);

наличная армия игрока;

территория игрока (общее количество клеток);

территория противника;

суммарная армия (наличная армия плюс гарнизоны на всех клетках) игрока;

суммарная армия противника.

2. Требования к решению

Жюри принимает решения на одном из трех языков: C++, Pascal, Java (jdk 1.3.1). Участникам, программирующим на C++ или Pascal можно использовать следующие среды программирования: Borland C++ 3.1, Visual C++ 6.0, Borland C++ Builder 5.0, Visual Age C++ 4.0, Borland Pascal 7.0, Borland Delphi 5.0. При отправке, решения выкладывать на FTP-сервер в папку, соответствующую среде разработки. Жюри рассмотрит предложения участников по расширению списка сред программирования.

Участники должны реализовать две процедуды: процедуру инициализации init и процедуру расчета хода игрока get_move.

Процедура init запускается перед началом игры. Процедура get_move запускается перед каждым ходом игрока.

Обращаем особое ВНИМАНИЕ на то, что требуется реализовать стратегию, играющую на поле как за первого игрока, так и за второго.

Участники могут использовать 32Mb оперативной памяти. Нельзя хранить информацию на жестком диске.

2.1 C++

Участники должны предоставить Жюри исходные тексты с игровой стратегией. Среди исходных текстов должен быть файл player.cpp с двумя функциями:

void init();
void get_move(int &new_ipos, int &new_jpos, long &collect_army);

Вся доступная игроку информация о текущем состоянии игры находится в следующих глобальных переменных:

int player - порядковый номер текущего игрока (0 или 1), при этом порядковый номер противника - (1-player).

int ipos, jpos - координаты игрока (номер строки и номер столбца, соответственно).
1 £ ipos £ 17, 1 £ jpos £ 26.

int field[19][28] - двумерный массив размером 19×28, содержащий информацию о проходимости клеток и принадлежности клеток игрокам. Если field[i][j] = 0, то клетка не проходима (является стенкой). Если field[i][j] = 1, то клетка проходима и принадлежит первому игроку. Если field[i][j] = 2, то клетка проходима и принадлежит второму игроку. Соответственно, если field[i][j] = (1+player), то клетка принадлежит текущему игроку, а если field[i][j] = (2-player), то клетка принадлежит противнику. Других значений field[i][j] принимать не может. Клетки поля имеют индексы i, j, где 1 £ i £ 17, 1 £ j £ 26. Остальные (граничные) элементы массива гарантированно равны 0. Другими словами, считается, что поле обнесено сплошной стеной.

long army[19][28] - двумерный массив размером 19×28, содержащий информацию о размерах гарнизонов в клетках поля, принадлежащих игроку. Если клетка не принадлежит игроку (принадлежит противнику или не проходима), то значение соответствующего элемента массива army равно 0.

int territory - количество клеток, принадлежащих игроку.

int opponent_territory - количество клеток, принадлежащих противнику.

long hand_army - количество наличной армии.

long total_army - суммарная армия игрока (наличная армия плюс гарнизоны на всех клетках).

long opponent_total_army - суммарная армия противника (наличная армия плюс гарнизоны на всех клетках).

Функции get_move передаются ссылки на три переменные, в которые она должна записать информацию о ходе, а именно:

new_ipos, new_jpos - новые координаты игрока. Если ход на новую клетку не допустим, то игрок остается в той же клетке.

collect_army - сколько армии игрок намерен забрать с новой клетки и присоединить к наличной армии. Если при этом значение collect_army отрицательно, то -collect_army - количество наличной армии, которое игрок намерен добавить к гарнизону новой клетки.
Если collect_army > army[new_ipos][new_jpos], то перед совершением хода collect_army присваивается значение army[new_ipos][new_jpos]. Если collect_army < -hand_army, то перед совершением хода collect_army присваивается значение -hand_army. При этом, если ход на новую клетку не допустим, то перераспределение армии не совершается.

Участник может хранить свои данные в виде глобальных переменных.

2.2 Pascal

Участники должны предоставить Жюри исходные тексты с игровой стратегией. Среди исходных текстов должен быть модуль player.pas с двумя процедурами:

procedure init;
procedure get_move(var new_ipos, new_jpos : integer; var collect_army : longint);

Вся доступная игроку информация о текущем состоянии игры находится в следующих глобальных переменных:

player_num : integer - порядковый номер текущего игрока (0 или 1), при этом порядковый номер противника - 1-player.

ipos, jpos : integer - координаты игрока (номер строки и номер столбца соответственно).
1 £ ipos £ 17, 1 £ jpos £ 26.

field : array [0..18,0..27] of integer - двумерный массив размером 19×28, содержащий информацию о проходимости клеток и принадлежности клеток игрокам. Если field[i,j] = 0, то клетка не проходима (является стенкой). Если field[i,j] = 1, то клетка проходима и принадлежит первому игроку. Если field[i,j] = 2, то клетка проходима и принадлежит второму игроку. Соответственно, если field[i,j] = (1+player), то клетка принадлежит текущему игроку, а если field[i,j] = (2-player), то клетка принадлежит противнику. Других значений field[i,j] принимать не может. Клетки поля имеют индексы i, j, где 1 £ i £ 17, 1 £ j £ 26. Остальные (граничные) элементы массива гарантированно равны 0. Другими словами считается, что поле обнесено сплошной стеной.

army : array [0..18,0..27] of longint - двумерный массив размером 19×28, содержащий информацию о размерах гарнизонов в клетках поля, принадлежащих игроку. Если клетка не принадлежит игроку (принадлежит противнику или не проходима), то значение соответствующего элемента массива army равно 0.

territory : integer - количество клеток, принадлежащих игроку.

opponent_territory : integer - количество клеток, принадлежащих противнику.

hand_army : longint - количество наличной армии.

total_army : longint - суммарная армия игрока (наличная армия плюс гарнизоны на всех клетках).

opponent_total_army : longint - суммарная армия противника (наличная армия плюс гарнизоны на всех клетках).

Функции get_move передаются ссылки на три переменные, в которые она должна записать информацию о ходе, а именно:

new_ipos, new_jpos - новые координаты игрока. Если ход на новую клетку не допустим, то игрок остается в той же клетке.

collect_army - сколько армии игрок намерен забрать с новой клетки и присоединить к наличной армии. Если при этом значение collect_army отрицательно, то -collect_army - количество наличной армии, которое игрок намерен добавить к гарнизону новой клетки.
Если collect_army > army[new_ipos][new_jpos], то перед совершением хода collect_army присваивается значение army[new_ipos][new_jpos]. Если collect_army < -hand_army, то перед совершением хода collect_army присваивается значение -hand_army. При этом, если ход на новую клетку не допустим, то перераспределение армии не совершается.

Участник может хранить свои данные в виде глобальных переменных.

2.3 Java

Участники должны предоставить исходные тексты класса
ru.nsu.olympic.strategy.player.Player,
реализующий интерфейс ru.nsu.olympic.strategy.Player. Далее все упоминаемые классы и интерфейсы находятся в пакете ru.nsu.olympic.strategy.

Интерфейс Player определяет две функции:

public void init(GameInfo gameinfo);
public MoveInfo get_move(GameInfo gameInfo);

Каждой из них передается объект класса GameInfo. Он содержит всю доступную игроку информацию о текущем состоянии игры, а именно:

player - порядковый номер текущего игрока (0, или 1), при этом порядковый номер противника - 1-player.

ipos, jpos - координаты игрока (номер строки и номер столбца соответственно).
1 £ ipos £ 17, 1 £ jpos £ 26.

field[][] - двумерный массив размером 19×28, содержащий информацию о проходимости клеток и принадлежности клеток игрокам. Если field[i][j] = 0, то клетка не проходима (является стенкой). Если field[i][j] = 1, то клетка проходима и принадлежит первому игроку. Если field[i][j] = 2, то клетка проходима и принадлежит второму игроку. Соответственно, если field[i][j] = (1+player), то клетка принадлежит текущему игроку, а если field[i][j] = (2-player), то клетка принадлежит противнику. Других значений field[i][j] принимать не может. Клетки поля имеют индексы i, j, где 1 £ i £ 17, 1 £ j £ 26. Остальные (граничные) элементы массива гарантированно равны 0. Другими словами считается, что поле обнесено сплошной стеной.

army[][] - двумерный массив размером 19×28, содержащий информацию о размерах гарнизонов в клетках поля, принадлежащих игроку. Если клетка не принадлежит игроку (принадлежит противнику или не проходима), то значение соответствующего элемента массива army равно 0.

territory - количество клеток, принадлежащих игроку.

opponent_territory - количество клеток, принадлежащих противнику.

hand_army - количество наличной армии.

total_army - суммарная армия игрока (наличная армия плюс гарнизоны на всех клетках).

opponent_total_army - суммарная армия противника (наличная армия плюс гарнизоны на всех клетках).

Функция get_move должна возвратить информацию об очередном ходе игрока. Функция возвращает объект класса Moveinfo. Он содержит следующие переменные

new_ipos, new_jpos - новые координаты игрока. Если ход на новую клетку не допустим, то игрок остается в той же клетке.

collect_army - сколько армии игрок намерен забрать с новой клетки и присоединить к наличной армии. Если при этом значение collect_army отрицательно, то -collect_army - количество наличной армии, которое игрок намерен добавить к гарнизону новой клетки.
Если collect_army > army[new_ipos][new_jpos], то перед совершением хода collect_army присваивается значение army[new_ipos][new_jpos]. Если collect_army < -hand_army, то перед совершением хода collect_army присваивается значение -hand_army. При этом, если ход на новую клетку не допустим, то перераспределение армии не совершается.

Участник может хранить свои данные в виде переменных класса
ru.nsu.olympic.strategy.player.Player.

3. Судейство и ограничения, налагаемые на стратегию

Для определения победителя и призовых мест будет проведен турнир между стратегиями команд и/или решением Жюри, состоящий из серии матчей между стратегиями. Матч будет состоять из нескольких игр между одними и теми же стратегиями на разных картах. Жюри предоставляет участникам некоторые из этих карт; их вы можете найти ЗДЕСЬ. Победитель в матче определяется количеством побед в играх. При равных количествах побед победитель определяется по количеству ходов, затраченных на победы. Преимущество будет отдаваться стратегиям, выигрывающим за меньшее число ходов. Каждая игра заканчивается победой одного из игроков или ничьей. Игрок побеждает, если в ходе игры он не нарушил ограничений, налагаемых на стратегию, и сумел захватить всю территорию противника за количество ходов, не превосходящее ограничение на количество ходов. Игрок также побеждает, если его противник нарушил ограничения, налагаемые на стратегию. Если игроки не нарушили ограничений, налагаемых на стратегию, и не сумели захватить территорию противника за количество ходов, меньшее, чем ограничение на количество ходов, то игра заканчивается вничью.

На стратегию налагаются следующие ограничения.

Максимальное время работы процедуры init: 30 секунд.

Максимальное время работы процедуры get_move: 0.3 секунды.

Максимальное количество ходов - 6000.

Тестирование будет проходить на машинах не хуже Celeron 433.

4. Средства, предоставляемые Жюри

Жюри предоставляет участникам исходные тексты своих программ для отладки решений участников на трех языках: для Borland C++ 3.1, Borland Pascal 7.0, и Java. Исходные тексты содержат процедуры обработки ходов, простейшие средства визуализации и примеры реализации двух стратегий. Описание вышеуказанных средств находится в общем пакете и доступно ЗДЕСЬ.