ミニマックスで三目並べ

問題

ミニマックスは、ゲームを指すプログラムが手を選ぶ方法です。両者が完璧に指すと仮定し、終局したすべての対局に点数を付けて、その点数をゲーム木の上へ伝えます。手番のプレイヤーは自分にとって最も点数の高い子を選びます。

盤面は行ごとに読む 9 文字の文字列 (インデックス 0-8) で、"X"、"O"、または空きマスを表す "." からなります。X が常に先手なので、両者の印の数が同じなら X の手番、そうでなければ O の手番です。

終局の点数は手番のプレイヤーから見て、勝ちなら +1、引き分けなら 0、負けなら -1 とします。ミニマックスの点数が最も高い空きマスを返し、同点が複数あれば最も小さいインデックスを返します。

best_move(board) を実装してください。

board: まだ誰も勝っておらず、空きマスが 1 つ以上ある正しい局面。

最善手のインデックス (0-8) を返します。

board はちょうど 9 文字で、各文字は X、O、. のいずれか

実際の対局で現れうる局面で、誰も勝っておらず、空きマスが 1 つ以上ある

例 1

入力：
board = "XX.OO...."

期待される出力：
expected = 2

入力：
std::string board = "XX.OO....";

期待される出力：
long long expected = 2;

入力：
string board = "XX.OO....";

期待される出力：
long expected = 2;

X と O は 2 つずつなので X の手番です。2 に置くと上の行がそろい、即座に勝ちます (+1)。

例 2

入力：
board = "X..OO...X"

期待される出力：
expected = 5

入力：
std::string board = "X..OO...X";

期待される出力：
long long expected = 5;

入力：
string board = "X..OO...X";

期待される出力：
long expected = 5;

X の手番です。O は 5 で中段をそろえようとしています。ほかの手ではすべて O が勝ち (-1)、5 でふさぐと引き分け (0) になるので、答えは 5 です。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

X と O の個数から手番を判定し、合法手をすべて再帰的に評価します。

ヒント 2

終端局面は現在のプレイヤー視点でスコア化し、その値を最大にする手を選びます。

ヒント 3

複数の手が同点なら、最初の空きセル index を優先し、さらに先の手を見る前に勝ちを判定します。

目安の計算量

時間 O(9!)、追加メモリ O(9)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。