Контекст задачи

«Берегите свои светлые мечи, ибо роса заставит их заржаветь». — «Отелло»

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

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

Условие задачи

Реверси, также известная как Отелло, играется на доске $8\times 8$, где $(x,y)$ обозначает строку $x$ и столбец $y$ (индексация с $0$). Начальная позиция состоит из четырех фишек в центре: $(3,3)$ и $(4,4)$ — белые, $(3,4)$ и $(4,3)$ — черные. Игроки ходят по очереди, черные ходят первыми. При установке новой фишки все фишки противника, оказавшиеся зажатыми между новой фишкой и уже имеющимися на доске фишками того же цвета, переворачиваются. Зажатие может происходить по горизонтали, вертикали или диагонали. На линии зажатия должны находиться только фишки противника, без пустых клеток, и этот ход должен приводить к захвату хотя бы одной фишки, иначе он считается нелегальным. Если у игрока нет легальных ходов, его ход пропускается. Один ход может привести к перевороту фишек в нескольких направлениях; все зажатые фишки должны быть перевернуты, у игрока нет права выбора, какие фишки переворачивать. Если у игрока есть хотя бы один легальный ход, он обязан сделать его и не может пасовать. Игра продолжается до тех пор, пока доска не заполнится или пока оба игрока не лишатся возможности сделать ход. Побеждает тот, у кого на доске больше фишек.

Детали реализации

Вам не нужно (и не следует) реализовывать функцию main. Вам необходимо реализовать функцию Play(Taskid,yourside), где Taskid — номер подзадачи, а yourside — ваша сторона (yourside=0 для черных, yourside=1 для белых). Вы можете вызывать следующие две функции для взаимодействия с интерактором:

1. MakeMove(position): эту функцию нужно вызывать, когда наступает ваша очередь. Она указывает, что вы делаете ход в позицию position. Вы должны гарантировать, что $0\leq \texttt{position.first},\texttt{position.second}< 8$ и ход является легальным. Если у вас нет доступных ходов, вызовите MakeMove(make_pair(-1,-1)). Если игра уже завершена, вы не должны вызывать эту функцию. Функция не возвращает значения.
2. ReceiveMove(): эту функцию нужно вызывать в ход противника, чтобы получить его ход. Она возвращает переменную типа std::pair<int,int>, представляющую координаты хода противника. Если возвращается $(-1,-1)$, это означает, что противник не может сделать ход. Вы не должны вызывать эту функцию после завершения игры.

Если текущая партия завершена, вы должны вернуться из функции Play.

При тестировании интерактор вызовет Play ровно $10$ раз. В первых $5$ случаях вы играете за черных, в последних $5$ — за белых. Позаботьтесь об очистке необходимых переменных после каждого вызова Play. Ваш итоговый балл будет зависеть от количества партий, в которых вы не проиграли (победа или ничья). Обратите внимание: если вы совершите нелегальное действие, вы получите $0$ баллов.

Гарантируется, что интерактор использует менее $5\,\mathrm{s}$ времени и $10\,\mathrm{MB}$ памяти, что означает, что у вас есть как минимум $5\,\mathrm{s}$ времени и $502\,\mathrm{MB}$ памяти.

Как отлаживать программу

Данная задача поддерживает только C++.

Назовите вашу программу reversi.cpp.

Убедитесь, что в начале программы есть #include "reversi.h".

Интерфейс, который вы должны реализовать:

void Play(int Taskid,bool yourside);

Интерфейс, который вы можете вызывать:

void MakeMove(std::pair<int,int> position);

std::pair<int,int> Receive();

Для компиляции программы используйте команду:

g++ grader.cpp reversi.cpp -o reversi -O2 -lm

В предоставленных файлах содержатся grader.cpp, reversi.h, template-reversi.cpp и gamelauncher.

gamelauncher — это программа для игры на вашем компьютере с теми же правилами. Рекомендуется использовать её только для ознакомления с правилами. Не пытайтесь использовать её для получения баллов (например, вызывая её как часть интерактора). Из-за особенностей платформы не гарантируется корректная работа программы и UI на всех системах. Если программа не запускается, попробуйте выполнить:

chmod +x gamelauncher

Подзадачи

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

ИИ (1)

Этот ИИ каждый раз выбирает случайную доступную позицию для хода (если она есть). Это подзадача 1, стоимость $10$ баллов.

ИИ (2)

Этот ИИ делает случайные ходы в начале игры, а в конце использует поиск до завершения игры для выбора оптимальной стратегии. Это подзадача 2, стоимость $20$ баллов.

ИИ (3)

Этот ИИ в начале игры просматривает все возможные варианты на один ход вперед и выбирает ход по определенному критерию, а в конце игры ведет себя как ИИ (2). Это подзадача 3, стоимость $30$ баллов.

ИИ (4)

Этот ИИ — воплощение божества, существующее с начала времен. Это не человеческая разработка, автор задачи пригласил его для сражения с вами. Это подзадача 4, стоимость $40$ баллов.

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

Ваш балл в зависимости от количества проигранных партий против ИИ приведен в таблице: