edaxが使っている枝刈り手法を説明します。 stability cutoff: オセロの終盤では「今後絶対にひっくり返らない石」が生じます。これをstable discと呼びます。四隅が最も有名ですが、それ以外にも例えば上下左右斜めの8方向に空白が一切存在しない石は自明に…

edaxというオセロソフトのソースコードをガチャガチャいじって遊んでいたのですが、いろいろわかって満足したので忘れる前に書いておきます。 探索アルゴリズムの基本的な説明 最初なので基本的というか、将棋ソフトとかと共通していてedaxでも使われている…

前回から引き続き、「オセロの初期局面から合法的に到達可能で、かつ合法手の数が34通りあるような局面は存在するのか？」を調べました。前回の最後に言及したように、flip関数をz3で書き下すことで、主問題そのものをソルバーに投げられるようにしました。…

前回の記事では合法手の数が34通りあるようなオセロの局面を生成しましたが、あれは初期局面から到達可能かどうかを考慮していませんでした。初期局面から到達可能で、かつ合法手の数が34通りあるような局面は存在するのでしょうか？ いっぱい存在すると期待…

将棋の最大分岐数（すべての局面における合法手の数の最大値）は593であることが証明されています。http://www.nara-wu.ac.jp/math/personal/shinoda/bunki.htmlこの証明は実際の局面を構成してはいませんが、簡単に構成可能でして、やっている人がいます。l…

edaxというオセロソフトがあるのですが、そこでは『1を左シフトする操作』が表引きで実装されています。マクロがbit.hで宣言されていて、表の実体はbit.cにあります。https://github.com/abulmo/edax-reversi/blob/master/src/bit.h extern const unsigned l…

2進数(binary number)は0と1だけからなりますが、3進数(ternary number)は0と1と2からなります。2進40桁以下の符号なし整数を受け取って、それを『偶然0と1だけでかけるような3進数だった』と解釈して、その値を2進数にして返す関数は以下のように書けます。…