○×ゲームの計算解析

○×ゲームは何通り?数値解析編

このページは基本的に
How many Tic-Tac-Toe (noughts and crosses) games are possible?>http://www.btinternet.com/~se16/hgb/tictactoe.htm?
の翻訳±αです。日本語にすると変な部分や無意味な部分は剥ぎ取って、解説っぽいものが必要そうなら入れました。


問題設定

3x3のマスに○と×を交互に置いていく。その際、縦・横・斜めのいずれか1列に同じ記号が3つ並んだら終了。または9マス全てが埋まったら終了。この時、終了するまでにマスを埋める順番は何通りあり得るか。
(訳注:原文では○が後手、×が先手となっているが、日本人の一般的感覚だと逆なので日本人側に合わせる。)

上界

上界は考えるまでもなく、1手目が9通り、2手目が8通り、3手目が7通り…9手目が1通りなので
9*8*7*6*5*4*3*2*1=9!=362880通り
実際には、途中で終わるものも続きを数えていたりするため、本当の答えはもっと小さいと思われる。

ゲームが終わるには全マスが埋まるか1列揃うかしなければならないため、最低でも5手かかる。つまり5手~9手のそれぞれで終わるゲーム数を数えればよい。9手で終わるゲームには勝ち負けが決まるものとどの列も揃わずに引き分けになるものとがあることに注意しなければならない。

5手目で終了する場合(1440通り)

3つが並ぶ列は8通り(縦が3列、横3列、斜め2列)ありえ、その列に○がどの順番に置かれても関係なく、×はその列以外の6マスならどこに、どの順に置いても構わない。したがって計算結果は
8*3!*6*5=1440通り
8:○が並ぶ列の数
3!:↑で○を置く順番
6*5:×を置く数

6手目で終了する場合(5328通り)

先程と同様に×が並ぶ列は8列あり、その中ではどの順に置かれても問題ない。そして○は残り6マスに(列が揃わないように)置いていれば順序は関係ない。まず括弧にくくった部分を無視して、
8*3!*6*5*4=5760通り
8:×が並ぶ列の数
3!:↑で×を置く順番
6*5*4:○を置く数

そしてこの中から本来含めてはならない、○も並んでいる場合を数える。この時、○も×も斜めにはなりえず、一方の列がどこになるかを決めれば、もう一方は2列分しか可能性がなくなる。(○が縦に並んでいれば×も縦に並ばざるをえない)このことから、
6*3!*2*3!=432通り。
6:×が並ぶ列の数
3!:↑で×を置く順番
2:○が並ぶ列の数
3!:↑で○を置く順番

したがって、両者の差をとって
5760-432=5328通り

7手目で終了する場合(47952通り)

○が並ぶ列は同様に8列あり、7手目に置く○はその列になければならない。3つの×は残り5マスに(列が揃わないように)置けば順番は関係ない。同様にまずは括弧の部分を無視して
8*3*6*3!*5*4*3=51840通り
8:○が並ぶ列の数
3:7手目の○を置く場所
6:列に入らない○をどこに置くか
3!:1,3,5手目の○を置く順番
5*4*3:×を置く順番

次にありえない場合を除く。前と同様に、
6*3*6*3!*3!=3888通り
6:○が並ぶ列の数
3:7手目の○を置く場所
6:列に入らない○をどこに置くか
3!:1,3,5手目の○を置く順番
3!:×を置く順番

差し引いて
51840-3888=47952通り

8手目で終了する場合(72576通り)

×が並ぶ列は同様に8列あり、8手目に置く×はその列になければならない。4つの○は残り5マスに(列が揃わないように)置けば順番は関係ない。同様にまずは括弧の部分を無視して
8*3*6*3!*5*4*3*2=103680通り
8:×が並ぶ列の数
3:8手目の×を置く場所
6:列に入らない×をどこに置くか
3!:2,4,6手目の×を置く順番
5*4*3*2:×を置く順番

次にありえない場合を除く。前と同様に、
6*3*6*3!*2*4!=31104通り
6:×が並ぶ列の数
3:8手目の×を置く場所
6:列に入らない×をどこに置くか
3!:2,4,6手目の×を置く順番
2:列に入らない○をどこに置くか
4!:○を置く順番

差し引いて
103680-31104=72576通り

9手目で勝ち負けが決まる場合(81792通り)

この場合は勝ちパターンが簡単ではないので、さらに場合分けをする。結果だけ先に書いておくと
12672+27648+41472=81792通り

2列が一度にできる場合

列の組み合わせは
縦と横の組み合わせ…3*3=9通り
(縦または横)と斜めの組み合わせ…6*2=12通り
斜めと斜めの組み合わせ…1通り
9+12+1=22通り

最後の○は2列の交差する場所に置かなければならないため、1箇所に限定されるから
22*1*4!*4!=12672通り
22:上に挙げた組み合わせの数
1:最後の○を置く場所
4!:1,3,5,7手目の○を置く順番
4!:×を置く順番

斜めに列ができる場合

列としては2通りあり、最後の○はその斜めの列に置かなければならない。並ぶ列と最後に置く○の場所が決まっている場合、列に並ばない○を置くパターンは15通りありえるが、2列が一度にできる場合や既に1列できている場合を除くので8通りしか数えない。
15と8という数の具体的なを挙げておく。
例えば、最後に右上に置いて、/方向に列を完成させることを考えるとき
・数える8通り
○×☆ ○×☆ ×○☆ ×○☆ ×○☆ ××☆ ××☆ ××☆
×○○ ×○× ○○× ×○○ ×○× ○○× ○○× ×○○
○×× ○○× ○×× ○×× ○×○ ○○× ○×○ ○○×
・数えない7通り
○○☆ ○×☆ ○×☆ ×○☆ ××☆ ××☆ ××☆
×○× ○○× ×○× ×○× ○○○ ×○○ ×○×
○×× ○×× ○×○ ○○× ○×× ○×○ ○○○
したがって
2*3*8*4!*4!=27648通り
2:○が並ぶ列の数
3:最後の○を置く場所
8:列に並ばない2個の○を置くパターン
4!:1,3,5,7手目の○を置く順番
4!:×を置く順番

縦または横に列ができる場合

列としては6通りあり、あとは斜めに列ができる場合と同様に考えると、ありえないパターン(2列同時に完成、既に○が列を作っている、既に×が列を作っている)を除くと4通りしか組み合わせがないので
6*3*4*4!*4!=41472通り
6:○が並ぶ列の数
3:最後の○を置く場所
4:列に並ばない2個の○を置くパターン
4!:1,3,5,7手目の○を置く順番
4!:×を置く順番

9手目が終わって引き分けに終わる場合(46080通り)

○も×も列を作らないパターンは16通り(下記に示す基本3パターンと、その対称形)なので
16*5!*4!=46080通り
16:パターン数
5!:○を置く順番
4!:×を置く順番
8通り  4通り  4通り ←対称形の数
×○×  ○×○  ○×○  8通り…元のまま、上下反転、左右反転、右90度回転、左90度回転
×○○  ○×○  ××○      180度回転、上下反転+右90度回転、上下反転+左90度回転
○×○  ×○×  ○○×  4通り…↑のうち、形が重複しない4つ

まとめ

5手目で決着 1440
6手目で決着 5328
7手目で決着 47952
8手目で決着 72576
9手目で決着 81792
引き分け 46080
合計 255168

おまけ

添付の ox.c>http://www9.atwiki.jp/othello/?cmd=upload&act=open&pageid=42&file=ox.c? に探索するプログラムを置いておきました。結果は上記の計算結果と一致しています。
プログラムを簡単にする都合上、引き分けを10手目で終了と同様に扱わせてもらってます。@wikiへ

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2007年12月09日 22:43
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。
添付ファイル