問題の背景

Keep up your bright swords, for the dew will rust them. ——《オセロ》

オセロは自分がしてきたことを見つめ、心の中で後悔の念に駆られていた。彼は手に持っていた剣を置き、自身の人生の浮き沈みや情愛の波乱を振り返る。自身の嫉妬と疑心暗鬼が、最終的に自分が持っていたすべてを破壊してしまったのだ。

しかし、誰がそうではないと言えるだろうか？「塞翁が馬」という言葉があるように、福と禍は互いに転じ合う。現在の成功は過去の伏線の一つ一つによって築かれたものであり、それが未来のさらなる可能性につながることもある。人生はチェスのようなもので、白と黒が縦横に交錯する。かつて自分が打った駒が、行く手を阻む障害物になるかもしれない。Reversi（オセロとも呼ばれる）のように、白と黒の間で状況は絶えず変化し、真に先見の明を持ち、全体を統御できる者だけがその中で勝利を収めることができる。

問題文

Reversi（オセロとも呼ばれる）は $8\times 8$ の盤面で行われる。$(x,y)$ は第 $x$ 行第 $y$ 列（$0$ 始まり）を表す。初期状態では、盤面の中央に白と黒が交互に2つずつ配置されている。$(3,3)$ と $(4,4)$ が白、$(3,4)$ と $(4,3)$ が黒である。対局者は交互に石を打ち、黒が先手となる。新しく置いた石と盤面上の同色の石との間で、相手の石を挟んだ場合、挟まれたすべての石を裏返さなければならない。挟む方向は水平、垂直、または斜めである。挟む位置にはすべて相手の石が並んでいる必要があり、空きマスがあってはならない。また、この手で少なくとも1つ以上の石を裏返す必要があり、そうでない場合は不正な手となる。もしあるプレイヤーが打てる手が一つもない場合、そのプレイヤーのターンはスキップされる。一手で複数の方向に石を裏返すことができ、挟まれたすべての石は必ず裏返さなければならず、プレイヤーは特定の石を裏返さないという選択はできない。もし一方のプレイヤーが少なくとも一つ合法的な手を持っている場合、必ず石を打たなければならず、パスは認められない。対局は盤面が埋まるか、両者とも合法的な手が打てなくなるまで続き、最終的に石の数が多い方が勝利となる。

実装の詳細

メイン関数を実装する必要はなく、また実装すべきでもない。実装すべきは Play(Taskid,yourside) 関数のみである。ここで Taskid はサブタスク番号、yourside は自分の担当（yourside=0/1 はそれぞれ黒/白を表す）である。以下の2つの関数を呼び出してインタラクタとやり取りを行うことができる。

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 の終了後に必要な変数を初期化することに注意すること。スコアはこれら $10$ 局の対局のうち、敗北しなかった（勝利または引き分け）回数によって決定される。不正な操作を行った場合、その時点でスコアは $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> ReceiveMove();

プログラムをコンパイルする場合、本問題のディレクトリで以下を実行すること。

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

配布ファイルには grader.cpp、reversi.h、template-reversi.cpp、gamelauncher が含まれている。

gamelauncher は手元で遊べるゲームプログラムであり、ルールは本問題と同じである。ルールを把握するためにのみ使用し、このプログラムをベースにしてスコアを獲得しようとしないこと（例えば、このプログラムをインタラクタとして呼び出すなど）。プラットフォームの都合上、すべての環境でプログラムや UI が正しく動作することは保証しない。もしプログラムが実行できない場合は、以下のコマンドを実行してから再度試すこと。

chmod +x gamelauncher

評価方法

本問題には4つのサブタスクがあり、それぞれ難易度の異なるAIと対戦する。

AI（一）

このAIは、打てる場所がある場合、毎回ランダムに一つ選んで打つ。これがサブタスク1であり、10点分である。

AI（二）

このAIは、序盤はランダムに打ち、終盤はゲーム終了まで探索を行って最適な戦略を選択する。これがサブタスク2であり、20点分である。

AI（三）

このAIは、序盤は一手先までのすべての可能性を探索し、ある基準に従って手を選択する。終盤はAI（二）と同様である。これがサブタスク3であり、30点分である。

AI（四）

このAIは神の化身であり、天地開闢の時からここに存在している。人力によるものではなく、本問題の作者が諸君との対決のために招いたものである。これがサブタスク4であり、40点分である。

配布されたインタラクタはAI（一）を使用している。最終評価で使用されるインタラクタは配布されたものと実装が異なる可能性があるため、インタラクタの実装に依存するコードを書かないこと。評価時に使用されるインタラクタにはランダム性があるが、配布されたインタラクタの乱数シードは固定されている。より多くのランダムなデータでテストしたい場合は、インタラクタの seed 変数を変更することで実現できる。複数回提出することでスコアを向上させることができる。

AIとの対戦スコアは以下の表の通りである。