オセロは思ったより小さい

今週のゼミで、教授から「オセロのゲーム木の大きさをまず測ってみてはどうか」と言われた。
「ゲーム木の大きさ」って何か。最初の石の配置から、プレイヤーがどの選択肢を選ぶかによってゲームはどんどん枝分かれしていくでしょう。「枝分かれしていく」ってのがまさに木の形、中学の数学なんかで樹形図ってやったでしょう、あれになるから枝分かれの様子を「木」と呼ぶんです。その大きさと言ったら、枝分かれと末端をあわせた数のこと。さてどのくらいあるのか。
これまで、概算で10⁵⁸個だと言われてきました。10⁵⁶程度だという意見もあります。
http://dais.main.jp/reversi/solve-reversi.html
でもその概算はかなりいい加減で、「1手につきだいたい選択肢が10通りくらいあって、ゲームは平均58手くらいで終わるから」という理由。おいおい、それを言ったら最初の手は4通り、2手目は3通りしかないし、最後の手も普通1通りしかないぞ！？　（しかも、その計算では末端の数が10⁵⁸個あると言うことになるので、木の大きさを求めたことになっていない)
そこで、計算してみることにしたわけです。すべての手を網羅するのはもちろん無理だから、ランダムに打つだけのコンピュータ同士に5万回対戦させて、何手目では選択肢が何通りあったのか、それを報告させて平均をとる。
こうして各手目ごとの平均分岐数が求まったらそれを掛け合わせれば末端の数、掛け合わせながら足していけばゲーム木の大きさが求まるという寸法です。
まず大事なのは、平均の取り方。平均にも算術平均、相乗平均、調和平均などなどありますね。（中央値なんてのもあったなそういえば）
そこで予備実験。4×4オセロの木の大きさは191401だとすでに求まっているから、算術・相乗・調和のどれで計算したものが一番近い値を出してくれるか、勝負です。
結果:算術=203262.3 相乗=112714.3 調和=56126.4
もっともまともな結果を返してくれるのは算術平均だと判明。（相乗平均が一番まともなんじゃないかと予想していた。はずれ。）
さて、算術平均を使うことに決定してオセロのゲーム木サイズを推測させると・・・
8×8オセロ・・・4×10⁵³
6×6オセロ・・・3×10²²
と出ました。10⁵⁸に比べたら5桁も少なくなってる。2万分の1くらい。ま、天文学的数字なことに変わりはないけどね。
こういう、乱数を使って何かを予測したり近似値を求めたりする手法をモンテカルロ法と呼びます。モンテカルロと言えばカジノ。サイコロ任せの手法ってことですね。