Турнир программ даёт Вам возможность посоревноваться в несколько иных навыках, нежели требуются для классических олимпиад по программированию. В этот раз вы побудете в роли стратега-завоевателя. А если быть более точным, то в роли создателя алгоритма работы стратега-завоевателя. В вашем распоряжении легионы войск и целый незавоёванный континент, ждущий ваших побед. Дерзайте!
С момента получения этого руководства для вас начинается этап обсуждения и планирования. Во время этого этапа вы можете подробнее ознакомиться с правилами игры, придумать алгоритм для Ваших легионов и спланировать этап кодирования.
Во время этого этапа вы можете обсуждать алгоритм, устройство Вашей программы и правила игры с кем угодно — со своей командой, со своими тренерами, с другими командами и другими тренерами и вообще со всеми, кто не будет этому сопротивляться. :-)
В конце этапа обсуждения и планирования вы будете допущены в компьютерные классы, в которых будет установлено необходимое программное обеспечение для создания Вашей программы-участника. Это и будет начало этапа кодирования.
Во время этого этапа запрещается разговаривать с кем-либо, кроме членов Вашей команды и людей из группы технической поддержки. Запрещается приносить и использовать любые ресурсы в электронном виде: тексты, программы, библиотеки и т.п.
Ваша задача — разработать, протестировать и отправить жюри вашу программу-участника.
Итак, Ваша команда должна будет отправить жюри готовую программу-участника. Если Ваша команда отправит её несколько раз, то в турнире будет участвовать последняя отправленная версия.
После окончания этапа кодирования, в указанное в расписании чемпионата время, будет проводиться собственно сам турнир программ. Все желающие смогут следить за ходом турнира, а участники — ещё и болеть за свои программы!
Игровой мир представляет собой квадратное поле n x n клеток-провинций. На поле есть две провинции-города (по одной на каждого игрока). В нашем турнире, это всегда будут провинции с координатами (0, 0) и (n-1, n-1)
Игроки ходят по очереди. В начале хода в городе игрока появляется 5 легионов.
Легион может пройти по захваченной дружественными легионами территории и попытаться захватить любую провинцию.
Легионеры не отступают и не бросают охраняемые земли, поэтому провинция остается во владении игрока, пока легион не будет разбит неприятелем. Но чтобы разбить окопавшийся легион, требуется уже не один, а два легиона. В результате сражения умирает оборонявшийся легион, и один из легионов нападавших. Выжившие получают бесценный опыт сражения и становятся ветеранами.
Легионы-ветераны, как и другие легионы, остаются в захваченной провинции, пока их не разгромит противник, но на разгром ветеранов требуется уже три простых легиона. В результате сражения умирает оборонявшийся легион ветеранов и два нападавших легиона. Выжившие также становятся ветеранами.
Размещать по два легиона в провинции нельзя — умрут с голода. Посылать атаковать соседние провинции больше легионов, чем нужно, тоже ни к чему, а если послать меньше, чем нужно, например два легиона против ветеранов, то атакующие бесславно погибнут, а защитники к следующему ходу залечат свои раны, восстановят прежние силы, да еще и станут ветеранами (если ими не были).
Если легион заставляют выполнить приказ, который он совершить не может (например, атаковать провинцию, к которой нельзя пройти по землям, уже принадлежащим игроку), то от позора командир кончает жизнь самоубийством, легион дезертирует и исчезает.
Провинцию-город охраняет один легион новичков. Как только одна из провинций-городов захвачена легионерами противника, игра заканчивается досрочно.
Один ход — это передвижение одним из игроков пяти своих вновь собранных легионов. Игра продолжается n x n ходов (или меньше, в случае досрочного окончания). В конце игры подсчитываются очки:
Ниже приведён пример игры на поле размером 7 клеток, начиная со второго хода. Крестиками и ноликами изображаются легионы-новички, а квадратами и кружками, соответственно, легионы-ветераны. Как видно, в примере после 13 хода побеждают крестики.
| ход 2, счёт 5: 5
|
ход 3, счёт 10: 4
|
ход 4, счёт 7: 8
|
| ход 5, счёт 12: 7
|
ход 6, счёт 10: 12
|
ход 7, счёт 14: 10
|
| ход 8, счёт 11: 14
|
ход 9, счёт 16: 12
|
ход 10, счёт 14: 17
|
| ход 11, счёт 18: 14
|
ход 12, счёт 15: 18
|
ход 13, счёт 98: 0
|
Турнир будет проводиться в два этапа.
На первом, отборочном этапе все игроки разделяются на 2k групп, и в каждой группе проводится турнир по схеме каждый с каждым. По результатам, в каждой группе определяется лидер, который проходит на второй этап. Определение лидера происходит по следующему алгоритму: У каждого игрока подсчитывается сумма очков, заработанных за все проведённые игры. Игрок, набравший сумму, большую, чем остальные считается лидером. Если есть несколько претендентов на лидерство с одинаковой суммой очков, то преимущество у того, чья программа раньше других была передана жюри.
Второй этап проводится по системе "игра до двух поражений" (double-elimination tournament также известный как "двойной нокаут"). В такой схеме каждый игрок имеет возможность проиграть одну игру (кроме финала), не потеряв шанса стать победителем. Но после того как игрок проиграет вторую игру, он покидает турнир.
Для создания программы-участника можно использовать любой доступный на основном соревновании язык программирования и любую доступную среду программирования:
Программа-игрок представляет собой исходный код программы, принимающей на вход текущее описание игрового поля, а на выход выдаёт описание очередного хода.
На сетевом диске X:\Legions\samples доступны примеры
программ-игроков, на всех доступных языках программирования с уже реализованными
подпрограммами ввода и вывода данных. Их можно (и нужно!) использовать в качестве
отправной точки при разработке собственного игрока.
Весь ввод-вывод осуществляется через консоль без использования дополнительных файлов. На вход программе-участику поступают следующие данные:
В первой строке — номер игрока, за которого играет программа (0 или 1). Во второй строке — число n — размер игрового мира (во время турнира n = 17). В третьей и четвёртой строках находятся под одной паре чисел, являющихся координатами городов нулевого и первого игроков, соответственно.
В следующих n строках находится описание карты — по одной строке на каждую строку карты. Каждая строка состоит из n описаний ячеек, разделённых знаком табуляции. Описание ячейки состоит либо из одного символа ".", если соответствующая клетка карты пуста, либо из двух символов c1 и c2, записанных подряд, если клетка занята легионерами. В последнем случае, c1 — может быть либо латинской буквой N (или n) в случае, если клетка занята новичками, либо латинской буквой V (или v), если клетка занята ветеранами. Верхний регистр означает, что клетка соединена дружескими провинциями с городом. Нижний регистр означает обратное. Символ c2 является цифрой, обозначающей номер игрока, чьи легионы занимают клетку.
Система координат задана следующим образом:
В случае если на вход не было подано никаких данных, программа должна вывести своё имя - одну строку, не более 16 символов длиной.
В противном случае, на выходе программа-участник должна выдать описание своего хода в нескольких строках.
Каждая строка представляет собой одну команду легионам и должна состоять из трёх чисел, разделённых пробелами: X, Y, C — координаты провинции и количество легионов, направленных в указанную провинцию. 0 ≤ X, Y ≤ n. Суммарное количество направленных куда-либо легионов не должно превосходить 5. Указанные программой команды будут выполняться последовательно.
Пример ввода:
1
7
0 0
6 6
N0 N0 . . . . .
. N0 . . . . .
. N0 . . . . .
. N0 N0 N0 v1 . .
. . N0 . v1 . .
. . N0 N0 V0 . .
. . . . N1 N1 N1Пример вывода:
3 6 1
3 5 2
2 5 2 В течение всего этапа кодирования у вас будет возможность протестировать и отладить
свою программу. На сетевом диске в директории X:\Legions\bin будет
находиться программа "Полигон", предназначенная для тестирования создаваемого
вами игрока. Полигон запускается файлом polygon.bat и
предоставляет простой и понятный интерфейс, для проведения игр между
программами игроками.
Внимание! Перед использованием необходимо скопировать всё содержимое
директории X:\Legions\bin на свой локальный диск.
В поддиректории X:\Legions\players находятся несколько простых
программ-игроков, при помощи которых вы можете тестировать вашу собственную
программу.
В процессе отладки своей программы вы можете воспользоваться отладочным выводом. Для этого в программе достаточно писать текст на стандартное устройство вывода ошибок (stderr в С++, ErrOutput в Delphi, System.Console.Error в C#). Весь текст, выведенный на это устройство, будет показан в Полигоне в специальном окне отладочного лога.
В конце этапа кодирования Вы должны будете отправить свою программу-игрока жюри. Для этого нужно использовать штатное программное обеспечение соревнования.
При написании программы-игрока запрещено: