Background

Keep up your bright swords, for the dew will rust them. —— Othello

Othello looks back on everything he has done, filled with remorse. He lays down his sword and reflects on the ups and downs of his life, the turbulence of his emotions. His own jealousy and suspicion ultimately destroyed everything he possessed.

And who is not the same? As the saying goes, "The old man lost his horse, but who knows if it is a blessing or a curse?" Fortune and misfortune transform into one another. Current success is built upon the foreshadowing of the past, which in turn creates more possibilities for the future. Life is like a game of chess, a complex interplay of black and white—the pieces you once placed may become stumbling blocks on your path. Just like Reversi (also known as Othello), the transformation between black and white is fickle; only those with true foresight and a grasp of the overall situation can emerge victorious.

Problem Statement

Reversi, also known as Othello, is played on an $8\times 8$ board, where $(x,y)$ denotes the $x$-th row and $y$-th column (0-indexed). The initial board consists of four pieces alternating in the center: $(3,3)$ and $(4,4)$ are white, while $(3,4)$ and $(4,3)$ are black. Players take turns placing pieces, with black moving first. When a new piece is placed, all of the opponent's pieces that are trapped between the new piece and an existing piece of the same color on the board must be flipped. This can occur horizontally, vertically, or diagonally. The trapped line must consist entirely of the opponent's pieces with no empty spaces, and the move must trap at least one piece to be legal. If a player has no legal moves, their turn is skipped. A single move can flip pieces in multiple directions; all trapped pieces must be flipped, and the player has no choice in which pieces to flip. If a player has at least one legal move, they must make a move and cannot pass. The game continues until the board is full or neither player has any legal moves. The player with more pieces on the board wins.

Implementation Details

You do not need to, and should not, implement the main function. You only need to implement the function Play(Taskid,yourside), where Taskid and yourside represent the subtask ID and your side (yourside=0 for black, yourside=1 for white), respectively. You can call the following two functions to interact with the grader.

1. MakeMove(position): This function must be called when it is your turn to move, indicating that you are placing a piece at position. You must ensure $0\leq \texttt{position.first},\texttt{position.second}< 8$ and that the move is legal. If you have no valid moves, you must call MakeMove(make_pair(-1,-1)). You should not call this function if the game has already ended. This function has no return value.
2. ReceiveMove(): This function must be called during the opponent's turn to receive the position of their move. It returns a std::pair<int,int> representing the opponent's coordinates. If it returns $(-1,-1)$, it means the opponent cannot make a move. You should not call this function after the game has ended.

If the current game has ended, you should return from the Play function.

During evaluation, the grader will call Play exactly $10$ times. You will play as black for the first $5$ games and as white for the last $5$ games. Therefore, ensure you clear any necessary variables after each Play call. Your score will be determined by the number of non-loss (win or draw) games out of these $10$ matches. Note that if you perform an illegal operation, you will receive $0$ points.

The grader is guaranteed to use less than $5\,\mathrm{s}$ of time and $10\,\mathrm{MB}$ of memory, meaning you have at least $5\,\mathrm{s}$ of time and $502\,\mathrm{MB}$ of memory available.

How to Debug Your Program

This problem only supports C++.

Name your program reversi.cpp.

Ensure your program includes #include "reversi.h".

The interface you need to implement is:

void Play(int Taskid,bool yourside);

The interfaces you can call are:

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

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

To compile your program, run the following in the problem directory:

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

The provided files include grader.cpp, reversi.h, template-reversi.cpp, and gamelauncher.

gamelauncher is a game for players to use on their own computers. The rules are the same as in this problem. It is recommended that players use it only to familiarize themselves with the rules and for fun; do not attempt to use this program as a basis for gaining points in this problem (e.g., by calling it as an interaction program). Due to platform issues, it is not guaranteed that the program and UI will work correctly on all platforms. Additionally, if you cannot run this program, try running the following command before attempting to run it again:

chmod +x gamelauncher

Subtasks

There are four subtasks, each involving an AI of a different difficulty level.

AI (1)

This AI will randomly select a valid position to place a piece (if any) each turn. This is subtask 1, worth $10$ points.

AI (2)

This AI will make random moves in the early game and search until the end of the game in the late game to choose the optimal strategy. This is subtask 2, worth $20$ points.

AI (3)

This AI will search all possible outcomes for one move in the early game and choose a move based on a specific method; the late game is the same as AI (2). This is subtask 3, worth $30$ points.

AI (4)

This AI is the embodiment of God, appearing here since the dawn of time. It is not of human creation; the author of this problem invited it to compete with you. This is subtask 4, worth $40$ points.

The provided grader uses AI (1). The grader used for final evaluation differs from the provided one; please do not write code that depends on the specific implementation of the grader. Note that the grader used during evaluation is randomized, whereas the provided grader uses a fixed random seed. If you wish to test with more random data, you can modify the seed variable in the grader. You can improve your score through multiple submissions.

Your score against the AI is shown in the table below: