解法

GeneralReversiによってボードサイズが小さいリバーシ／オセロを解くことができます。
解いた結果は以下のようになりました。

  BoardSize2 BoardSize3 BoardSize4 BoardSize5 BoardSize6
Cross 2-2 L M 0-9 L M 3-11 L M 19-6 L M 16-20 L M
Parallel 2-2 L M 9-0 L M 6-9 L M 20-5 L M 17-19 L M

表の見方は、横軸がボードサイズで縦軸が初期配置です。
そして、各マスの中には「黒-白」のスコアと、ログ（L）と棋譜（M）のデータへのリンクがあります。

まず、ボードサイズ2についてです。
これは開始局面が終了局面となるのでプレイヤーによる着手は一度もありません。
「これがゲームと呼べるのか」という声が聞こえてきそうですが、
ゲームとして定義できないわけではないので、一般化のために記載しました。
結果は当然のことながら、交差型・平行型ともに引き分けです。

次に、ボードサイズ3についてです。
全9マスのうち初期配置4マスなので、空きマスは5マスになります。
結果は交差型では白必勝、平行型では黒必勝となりました。

次に、ボードサイズ4についてです。
全16マスのうち初期配置4マスなので、空きマスは12マスになります。
結果は交差型・平行型ともに白必勝となりました。
また、交差型・平行型ともに空きマスを残しての終局となっています。

次に、ボードサイズ5についてです。
全25マスのうち初期配置4マスなので、空きマスは21マスになります。
今までのボードサイズでは順序閾値や置換閾値はどのような値であっても一瞬で解くことができますが、
ボードサイズ5に関しては、深さ21の探索を行うことになるので、一瞬で解くことはできません。
と言っても数秒から数十秒なのですが、リンクにあるログは最速設定によるもので、
交差型で3秒、平行型で1秒かかりました。
最速設定は以下の通りです。
●深さ　　：21
●順序閾値：6
●置換閾値：10
スコアは交差型・平行型ともに黒必勝となりました。

最後に、ボードサイズ6についてです。
全36マスのうち初期配置4マスなので、空きマスは32マスになります。
深さ32の探索は相当な計算コストがかかり、順序閾値と置換閾値の設定が非常に重要です。
作者がとったアプローチは、ボードサイズ5の深さ21の最速設定が21-6-10で、
ボードサイズ8の深さ20の最速設定（FFO#40）が20-6-9であったことから、
最初にトライした設定は32-6-10でした。
しかし、この設定ではパソコンのメモリを使い切ってしまうことがわかりました。
そこで順序閾値は固定した状態で置換閾値を変化させ、
タスクマネージャーのメモリ上昇速度をチェックしながら、
最終的に32-6-13の設定で交差型・平行型ともに解くことができました。
解法にかかった時間とメモリ使用量は以下の通りです。
●交差型：22時間・10GB
●平行型：40時間・17GB
人類で最初にボードサイズ6を解いた人は交差型に2週間、平行型に5週間かかっており[4]、
平行型が交差型に対して2倍程度の時間がかかるという点で、
リーズナブルな結果が得られたと思います。
詳細についてはログをご参照ください。
スコアは交差型・平行型ともに白必勝となりました。

【考察】
  • 同じスコアになる棋譜は複数存在します。
    なので、今回の実験では完全棋譜の中の一つを示したに過ぎません。
    他の完全棋譜を得たければソルバーのランダム性をオンにすればよいですが、
    網羅的に得たいとなると専用の機能を追加しなければなりません。
  • 交差型に関して言えば、初期配置の対称性を考えると、
    深さを1減らすことができます。
    つまり、先手である黒が着手可能位置の4つのマスからどれを選ぼうが、
    ボードを回転させたり、ひっくり返したりすることによって、同一視することができます。
    なので最初の黒の着手は4つのマスから適当に選んで、
    白の手番の状態から探索すれば十分です。
    これによって例えばボードサイズ6であれば22時間かかっていたものが、
    5時間になります。
    今回の実験ではわかりやすくするため平行型と同じ設定で行いました。
  • 表の傾向を読みとると、ボードサイズ4、5、6に関して、交差型・平行型ともに、
    白必勝、黒必勝、白必勝、となっています。
    この傾向が続くとすれば、ボードサイズ7は黒必勝、
    そして、ボードサイズ8は白必勝ということになりますが…。
  • ボードサイズ7についてですが、
    全49マスのうち初期配置4マスなので、空きマスは45マスになります。
    ボードサイズ6の空きマス32との差は13マスで、
    ボードサイズ6とボードサイズ5の空きマスの差は32-21=11になります。
    今、この空きマスの差13と11が近いと見なし、
    ボードサイズ5からボードサイズ6になったときのかかった時間の比率107が、
    ボードサイズ6からボードサイズ7になったときのかかった時間の比率に等しいと仮定すると、
    ボードサイズ7の解法にかかる時間は107日、一万年のオーダーになります。
    生きているうちに解法するのは難しそうなので、
    ボードサイズ7の解法にトライするのはやめておきます＾＾；
inserted by FC2 system