アルゴリズム
三目並べの譜面全パターン分析

３×３のマス目に○（先手）と×（後手）のマークを交互に埋めていき、縦・横・斜めのいずれかで同じマークが３つ並ぶと勝ちという２人対決ゲームがあります。３×３＝９つのマス目に「○」「×」「未配置」の３つのどれかが入ると考えると、位置まで区別すると全部で$3^9=19683$パターンの状態が存在しますが、対称性を考慮すると自明ではありません。対称性まで考慮してそもそも何パターンの状態が存在するのかを調べました。
※ソースコードはこちら（HTMLファイル）

準備：対称性の確認

３×３のマス目は正方形なので、４回（９０°回転）の回転対称性と４本の軸対称性（横軸、縦軸、右上斜軸、右下斜軸）があります。 三目並べの場合、譜面を回転・反転しても本質的には同じとなるため、同一の譜面とみなします。さらに、回転した後に反転した譜面も同様に同一の譜面とみなせます。 次の結果は３×３のマス目に左上から順番に１から９の数字を記入した譜面を、「回転→反転」、「反転→回転」させた際の全譜面です。

元の並び

回転 → 反転

反転 → 回転

「回転 → 反転」のどれかと必ず一致するため考慮する必要はありません。

点対称反転

正方形には点対称も存在しますが、２次元の場合は１８０°回転と同じとなるため、考慮する必要はありません。

全譜面の列挙（対称性を考慮）

「○」→「×」→「○」→「×」→「○」→「×」→「○」→「×」→「○」 と順番に埋めていった場合の、０手目から９手目までの全パターンを列挙します。 なお、途中で勝敗が決定した場合も９手目まですべて埋めるとします。

０手目：1パターン

１手目：3パターン

２手目：12パターン

３手目：38パターン

４手目：108パターン

５手目：174パターン

６手目：228パターン

７手目：174パターン

８手目：89パターン

９手目：23パターン

合計：850パターン

思ったよりも多いですね。次回は勝敗が決した時点で終了する場合の全譜面を調べます。
※ソースコードはこちら（HTMLファイル）