勝敗の判定方法

ゲームの各時点における盤面は，各要素が \(\{\) 白，赤，青 \(\}\) のいずれかの値を取るような \(3 \times 3\) の2次元配列 \(C\) で表すことができます．すなわち， \(C_{i,j}\) はマス \((i,j)\) の色に対応します．盤面の色が \(C\) である状態からゲームを続けたとき，最終的に勝つプレイヤーを \(f(C)\) とします．

\(I\) を，すべての要素が白である \(3 \times 3\) の2次元配列とします（初期状態に対応）．求める答えは \(f(I)\) ですから，任意に与えられた \(C\) に対して \(f(C)\) を高速に求めることができれば，問題を解くことができます．

\(f(C)\) の計算方法を考えましょう．以下，現在の手番のプレイヤーを \(x\)，もう一方のプレイヤーを \(y\) とします．

もし， \(C\) がすでに終了状態（赤または青の同じ色で塗られたマスが \(3\) マス連続するか，白のマスが存在しない）であれば，勝敗は容易に判定できます．

\(C\) が終了状態でない場合， \(x\) が白で塗られたマスを一つ選んで自分の色で塗ることにより，別の盤面に遷移します．このとき，次が成り立ちます．

• \(C\) から \(1\) 回の操作で遷移できる盤面 \(C'\) のうち， \(f(C')=x\) となるようなものがあれば， \(C\) から \(C'\) に遷移することで \(x\) が勝つことができる
• 逆に，\(C\) から \(1\) 回の操作で遷移できるすべての盤面 \(C'\) について， \(f(C')=y\) ならば，\(x\) はどのように操作しても勝つことができない

この性質より， \(C\) から遷移できるすべての盤面 \(C'\) について \(f(C')\) が求まっていれば，それらの値から \(f(C)\) を求めることができます．このような処理は，再帰関数による実装が簡便です．

再帰関数による実装

再帰関数による実装では，盤面 \(C\) に対して関数 \(f\) が呼び出されたときに，次のような処理を行います．

1. \(C\) が終了状態ならば，勝敗を判定して答えを返す
2. \(C\) が終了状態でなければ， \(C\) から \(1\) 回の操作で遷移できる盤面 \(C'\) をすべて列挙する
3. 各 \(C'\) について \(f(C')\) を計算する
4. 計算した \(f(C')\) の結果から，前節の議論に基づいて \(f(C)\) の値を定める

関数 \(f\) の処理の中で関数 \(f\) 自身を呼び出している（ステップ 3）ので，このような処理は再帰と呼ばれます．ここで， \(f(C)\) から呼び出される \(f(C')\) の \(C'\) は \(C\) よりも終了状態に近づいているので，このような再帰的な呼び出しが無限に続くことはありません（形式的には，盤面の遷移関係からなるグラフは 有向非巡回グラフ (DAG) になっています）．

\(f\) が呼び出される回数を大雑把に見積もってみましょう．1回目の手番で可能な操作は \(9\) 通り，2回目の手番で可能な操作は \(8\) 通り，…となるので，初期状態から終了状態へ到達するまでの操作の組み合わせは \(9! \approx 3.6 \times 10^5\) 通り程度であり，十分高速です（実際には，同じ色で塗られたマスが \(3\) つ連続した時点でゲームが終了し，再帰的呼び出しがそこで打ち切られるため，より少ない呼び出し回数になります）．

実装例 (Python)

発展：メモ化再帰による実装

本問題ではナイーブな再帰関数でも十分高速に動作しますが，メモ化と呼ばれる工夫をすることで，再帰的呼び出しの回数を減らすことができます．

再帰関数による実装では，初期状態 \(I\) から盤面 \(C\) に到達するまでの操作の組み合わせが複数個ある場合，その回数だけ \(f(C)\) が呼び出されます．しかし，同じ \(C\) に対しては \(f(C)\) は常に同じ値を返すため，毎回再帰的呼び出しにより \(f(C)\) を計算するのは無駄です．そこで， \(f(C)\) を最初に計算したときの結果を覚えておいて，2回目以降に \(f(C)\) が呼び出されたときにはその覚えておいた値を返すようにします．

メモ化を行ったときの \(f(C)\) の呼び出し回数を見積もりましょう． \(C\) としてありえるものは大雑把に見積もっても \(3^{3 \times 3} = 19683\) 程度であり，各盤面から遷移できる盤面はたかだか \(9\) 通りですので， \(f\) の呼び出し回数はたかだか \(19683 \times 9 \approx 1.7 \times 10^5\) 回です．メモ化を行わないときの見積もり \(3.6 \times 10^5\) に比べて小さくなっていることがわかります．

本問題ではメモ化は要求されていませんが，より盤面の数や可能な遷移の数が多いような問題では，メモ化を行うことで計算量が大幅に改善されることがあります．

実装例 (Python)