アルゴリズム
三目並べの譜面全パターン分析
3×3のマス目に○(先手)と×(後手)のマークを交互に埋めていき、縦・横・斜めのいずれかで同じマークが3つ並ぶと勝ちという2人対決ゲームがあります。3×3=9つのマス目に「○」「×」「未配置」の3つのどれかが入ると考えると、位置まで区別すると全部で$3^9=19683$パターンの状態が存在しますが、対称性を考慮すると自明ではありません。対称性まで考慮してそもそも何パターンの状態が存在するのかを調べました。
※ソースコードはこちら(HTMLファイル)
準備:対称性の確認
3×3のマス目は正方形なので、4回(90°回転)の回転対称性と4本の軸対称性(横軸、縦軸、右上斜軸、右下斜軸)があります。 三目並べの場合、譜面を回転・反転しても本質的には同じとなるため、同一の譜面とみなします。さらに、回転した後に反転した譜面も同様に同一の譜面とみなせます。 次の結果は3×3のマス目に左上から順番に1から9の数字を記入した譜面を、「回転→反転」、「反転→回転」させた際の全譜面です。
元の並び
![](http://www.natural-science.or.jp/img/20180905-1.png)
回転 → 反転
![](http://www.natural-science.or.jp/img/20180905-2.png)
反転 → 回転
「回転 → 反転」のどれかと必ず一致するため考慮する必要はありません。
![](http://www.natural-science.or.jp/img/20180905-3.png)
点対称反転
正方形には点対称も存在しますが、2次元の場合は180°回転と同じとなるため、考慮する必要はありません。
![](http://www.natural-science.or.jp/img/20180905-4.png)
全譜面の列挙(対称性を考慮)
「○」→「×」→「○」→「×」→「○」→「×」→「○」→「×」→「○」 と順番に埋めていった場合の、0手目から9手目までの全パターンを列挙します。 なお、途中で勝敗が決定した場合も9手目まですべて埋めるとします。
0手目:1パターン
![](http://www.natural-science.or.jp/img/20180905-5.png)
1手目:3パターン
![](http://www.natural-science.or.jp/img/20180905-6.png)
2手目:12パターン
![](http://www.natural-science.or.jp/img/20180905-7.png)
3手目:38パターン
![](http://www.natural-science.or.jp/img/20180905-8.png)
4手目:108パターン
![](http://www.natural-science.or.jp/img/20180905-9.png)
![](http://www.natural-science.or.jp/img/20180905-10.png)
5手目:174パターン
![](http://www.natural-science.or.jp/img/20180905-11.png)
![](http://www.natural-science.or.jp/img/20180905-12.png)
6手目:228パターン
![](http://www.natural-science.or.jp/img/20180905-13.png)
![](http://www.natural-science.or.jp/img/20180905-14.png)
![](http://www.natural-science.or.jp/img/20180905-15.png)
7手目:174パターン
![](http://www.natural-science.or.jp/img/20180905-16.png)
![](http://www.natural-science.or.jp/img/20180905-17.png)
8手目:89パターン
![](http://www.natural-science.or.jp/img/20180905-18.png)
9手目:23パターン
![](http://www.natural-science.or.jp/img/20180905-19.png)
合計:850パターン
思ったよりも多いですね。次回は勝敗が決した時点で終了する場合の全譜面を調べます。
※ソースコードはこちら(HTMLファイル)