HOME > natural science Laboratory > コンピュータ・シミュレーション講座 > 機械学習

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

文責:遠藤 理平 (2018年9月 5日) カテゴリ:TIPS 集(107)機械学習(18)

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

準備:対称性の確認

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

元の並び

回転 → 反転

反転 → 回転

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

点対称反転

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


全譜面の列挙(対称性を考慮)

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

0手目:1パターン


1手目:3パターン


2手目:12パターン


3手目:38パターン


4手目:108パターン


5手目:174パターン


6手目:228パターン


7手目:174パターン


8手目:89パターン


9手目:23パターン



合計:850パターン

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



▲このページのトップNPO法人 natural science トップ

関連記事

TIPS 集

機械学習







▲このページのトップNPO法人 natural science トップ




Warning: mysqli_connect(): (28000/1045): Access denied for user 'xsvx1015071_ri'@'sv102.xserver.jp' (using password: YES) in /home/xsvx1015071/include/natural-science/include_counter-d.php on line 8
MySQL DBとの接続に失敗しました