オセロ 豆知識

オセロの手順は何通りあるか

オセロの初手は4通りありますが、どこに打っても同じ形なので、初手を「1通り」と考えた場合、2手目は3通りあります。3手目は・・・合計14通り。そのようにして、n手目までの手順が何通りあるかを数えたら、何通りあるでしょうか。

人が数えるのは無理な数になってしまうので、コンピュータを使ってちょっと数えてみました。

1手目を4箇所のうちの1つに固定した場合
2手目まで:3通り
3手目まで:14通り
4手目まで:61通り
5手目まで:349通り
6手目まで:2,050通り
7手目まで:13,773通り
8手目まで:97,554通り
9手目まで:751,330通り
10手目まで:6,142,855通り
11手目まで:53,065,220通り
12手目まで:484,974,801通り

これは「手順の数」であって、途中で同じ形、鏡にうつしたような形になることもあるので、「局面の種類の数」はもっと少ないです。

1手進むごとに手順が何倍になるかを計算してみると、

1→2:3倍
2→3:4.67倍
3→4:4.36倍
4→5:5.72倍
5→6:5.87倍
6→7:6.72倍
7→8:7.08倍
8→9:7.70倍
9→10:8.18倍
10→11:8.64倍
11→12:9.13倍

この辺から、そろそろ私が作ったプログラム(スクリプト)では数えるのに時間がかかりすぎるようになってきました。13手目以降もしばらくは倍率は増えて行くと思います。

45手目くらいまで、控えめに考えて大体10倍で増えて行くとすると、12手目までの手順の数(484974801通り)のさらに10の33乗倍ということで、10の41乗の桁は超えるでしょう。

終盤は、打てる場所の数が減って行くので倍率も減ると思いますが、46~50手目を7倍、51手目から55手目を5倍、56・57手目を3倍、58手目を2倍、59手目を1.5倍・・・と私の大体の感覚ですが、それであと9桁くらい増えるとして、少なくとも10の50乗通りは行くでしょう。

中盤の変化の数をかなり控えめに見積もったと思うので、どこかで見た10の60乗説を否定するものではありません。中盤をランダムで作りまくって倍率の平均(打てる場所の数の平均)を求めて計算したら、大体分かると思います。

戻る