オセロ必勝法
6×6のオセロがコンピュータで完全読み切りをした結果、後手必勝だということが判明した。1993年の出来事である。イギリスの研究者Joel Feinstein(ファインシュタイン)が発表している。
http://www.maths.nott.ac.uk/personal/jff/othello/6x6sol.html
SGIのマシンを2週間ぶっ続けで走らせたらしい。
1993年のコンピュータというと、まあ、いまのコンピュータの1/50程度の速度だと思う。だもんで、いまやれば、8時間ぐらいで結果が出そうだ。
せっかくだから7×7のオセロはどうなのかコンピュータで完全読み切りを行なうことを考えてみる。オセロはそれぞれの局面で有力な候補手は2,3手ぐらいだと思う。(それ以外はすぐにダメになってしまう変化だと思う)
氏の論文によれば、おおよそ100,000,000,000 positionsを調べたとあるから、オセロは最初から4つ石があるので6*6-4=32箇所、どの局面でも候補手の数kは一定だと仮定すると、k^32=100000000000だからk ≒ 2.2067。やはり候補手は2,3手というのは間違いなさそうだ。
ならば、7×7の盤面では、k^(7*7-4)=2942727176209282だ。これは、100000000000の29427倍だ。たいしたことないな。つまり、いまどきのコンピュータなら8時間の29427倍。ほんの9809日。たかが27年弱だ。つまりは、パソコン27台用意すれば1年で終わるわけだ。
ついでに、8×8の盤面では、k^(8*8-4)なので、↑のおよそ14万倍だ。つまり、パソコン27台あれば14万年で済むわけだ。*1
まあ、しかし、14万年は現実的ではないけども、1億人の参加するP2Pネットワークとかで分散コンピューティングできれば、1ヶ月もかからず計算完了である。そう考えると、P2Pネットワークを利用した分散コンピューティングはなかなか魅力的ではある。
1億人というのは非現実的な数字かというと、そうでもないと思う。マイクロソフトがWindowsにそういう仕組みを導入してくれて、1ヶ月に1回、その月に走らせるプログラムを公募して、採択されたものをみんなでスクリーンセーバー起動時に実行するとか、そんなのでも構わない。分散コンピューティングを用いなければ解決できないような問題には、タンパク質の解析(白血病の原因の特定)のような、医学的な価値があるものもあるわけだし、こういうの、導入考えてくれないかなぁ..(´Д`)>マイクロソフト