オセロAIのオタクをしています。にゃにゃんです。
実は私はオセロAI制作をきっかけに人力でもオセロを楽しんでいます。ですので、オセロAI歴が1年8ヶ月ほど、そして人力オセロ歴が8ヶ月ほどです。人力でオセロをやると、オセロの戦術について色々と学ぶことになり、これもまた、面白いものです。
オセロAI制作についてはこちらに詳しく書きました。
さて、オセロには「ストナー」という名前のついた(中盤に頻出の)戦術があります。このストナーという罠にかかってしまうと、受ける側はかなりの大打撃を被るという危険な進行です。今回は、対局開始から最短何手でストナーが起こりうるのかを調べてみた話です(誰得)。
ストナー自体がかなり難しい戦術なのですが、この記事はなるべく多くのプログラマーに読めるよう、オセロ初心者にもわかりやすく、まずストナーの解説から書きました。と、その前に、とりあえずこの遊びのきっかけをご説明しましょう。
きっかけ
私は筑波大学でオセロサークルMiN2に入っております。2022年も暮れの12月29日、サークルメンバーからいきなりこんなLINEが飛んできました。
なんと、対局開始から14手でストナーが成立すると言うのです。ちなみに並べてみると、確かにストナーに見えます。
実は厳密にはこれは回避可能なストナーなのですが、とにかく、短い手数でストナーが成立するかもしれないという事実に惹きつけられました。そして、プログラマーなら当然(？)、対局開始から最短でストナーに到達する手筋を列挙したくなります。
ということで、飲酒しながら3時間くらいで雑にコードを書いたら多分まともに動いたので、そのコードを貼ります。
とりあえず結論を知りたい人向け
最短ストナーは開始局面から13手のようです。その一つがこちらです。
e6d6c6d7c8b6c7f7f6e8f8g8b7
並べてみると、以下のようになります。
ストナーとは？
この章はオセロの戦術に関する基礎知識の説明です。ストナーという手筋を軽く解説します。すでにストナーを知っている方は読み飛ばして構いません。
隅を取ると有利？
オセロでは隅を取ると有利に立てると言いますが、それはある程度正しいものの、ある程度は間違いです。一つの例(ストナーではありません)を出して検証してみましょう。例えば、下図の場合はどうでしょうか？画像は黒番(次に着手するのは黒)で、黒がこれから攻められてしまう局面です。なお、この記事に出てくる盤面画像では、着手できるところが青い小丸で、直前に相手が置いた手が赤丸で表示されています。
白が直前に置いた手はg7です。白がこの手を置いてしまうと、黒は右下の隅であるh8にたやすく着手できます。では、着手してみましょう。
さて、白番です。黒にh8の隅を渡してしまいましたが、実は白には良い手があります。それは、g8です。白がg8に打てば、黒がどうあがいても、確実に白は下辺(a8からg8まで)を手に入れられます。下図は左から白g8、黒h7、白a8と進んだ様子です。
こうすれば白が下辺を確保できます。下辺を確保してしまえば、白の下辺は確定石(絶対にひっくり返されない石)です。
このような進行をオセロでは「ウィング攻め」と言います。オセロにおいて隅が強いと言われるのは、隅から辺に自分の確定石を増やしやすいからです。ですから、今回の例のように、自分が隅を確保しても相手に潜られて一辺を確保されるような場面では、隅は強くありません。
ストナーの原理
さて、前置きはこの程度に、一気にストナーの話をしてしまいましょう。
上で解説したウィング攻めは、実は「黒に対する強制力」がありません。黒が隅(h8)に着手しない限りは、当然白は下辺を確保できません。黒には隅に着手するか別のところに打つかという選択肢があります。しかし、ストナーはその余裕すらありません。気づいたときにはもう遅い。眼の前の罠に引っかかるしかない。これがストナーの怖いところです。
では、ストナーの形をお見せしましょう。黒番で、黒がこれからストナーの罠に引っかかってしまいます。
なんだかすごいことになっています。ひときわ目を引くのは、白の石がg7にあることでしょう。しかし、先程のウィング攻めとは違い、黒はすぐに隅(h8)へは着手できません。これは、d4からg7までの斜めのラインが全て白石だからです。オセロのルールでは自分の石で相手の石を挟まないといけないので、この場合には黒が隅に着手することはできません。
ということで、ここから黒が想定する流れは以下です。
- まず、黒の着手でd4、e5、f6のどれかの石を黒石にする
- 白がどこかに着手する
- 黒が隅(h8)に着手する
では実際にやってみましょう。例として、黒がg3に着手したとします。これによってe5の石が黒になります。次は白番です。
さて、白はこのまま黒に隅を与えるだけでしょうか？もちろん「ストナー」という大層な名前のついた戦術ですから、そんなわけがありません。ここで、白はf8に着手します。次は黒番です。
黒番は、これで困ってしまいます。
h8という隅に着手することはできます。しかし、f8に白石があるせいで、隅に着手したとは言え白に下辺(a8からf8)を確保されるのは確実です。この様子が下図です。黒h8、白a8と進んでいます。
だからと言って、これをf8の白石を返してこの状況を回避すべく、黒がg8に着手したらどうでしょうか？f8の白石をなくせるものの、なんとg7の白石まで返してしまいます。これでは、白にh8の隅を与えてしまい、さらにはその後白a8と打たれたら、白に下辺(a8からh8)を完全に確保されてしまいます。実際に黒g8、白h8、黒h7、白a8と打った様子が以下です。これはもう、黒は絶望的に辛いです。
このように、ストナーにかかってしまうと、受ける側(今回は黒)がどうあがいたとしても、必ず白に一辺を確保されてしまうのです。
しかも、さらに辛いことには、ウィング攻めと違ってストナーは無視できないのです。ストナーの局面から黒がどんな手を打とうと、結局白がf8に打ちさえすればストナーが爆発してしまいます。例として先程とは違って黒b3(この手では黒がh8の隅に打てるようにはならない)、白f8と進んだ局面が以下です。結局、これでもストナーは成功します。
まとめると、ストナーというものは、
- 攻めた方が確実に一辺を確保できる
- 受けた方は何をしてもそれを止めることができないし、無視しても一辺を確保されてしまう
というものです。
ストナーの形
ここまではストナーの原理を説明しました。ここでは実践的に、どのような形がストナーとなるかを列挙します。
黒4形
まずは上でも紹介した形です。
この形を、勝手に黒4形と名付けました。
黒3白1形
そして、実は以下のような形でもストナーが成立します。
下辺の形が少し違いますが、同じような流れでストナーが爆発します。
この場合は、例えば下図のように、黒f3(黒がh8に置く準備)、白e8(ストナー発動)で黒が困ってしまいます。
この形を、勝手に黒3白1形と名付けました。
黒3形
さらに、この形もストナーです。
この形でも、例えば黒f3(黒がh8に置く準備)、白e8(ストナー発動)で黒は困ります。
これでもし黒がf8に置いてしまうと、やはり下図のようにg7の白石が返ってしまいます。
そして当然ながら、黒がh8の隅に置いたところで、白が下辺(a8からe8)を確保します。
この形を、勝手に黒3形と名付けました。
ストナーも失敗することがある
ストナーは、実は失敗する可能性を秘めていることがあります。例えば以下の盤面では、黒4形ストナーに見えますが、実は受け手である黒には妙手があります。
ここで、黒がもしf3と打つとどうでしょうか？
なんと、白はf8に打てなくなってしまいます。つまり、ストナーが発動しません。さらに悪いことには、黒f3によってf6が黒石になるため、黒はh8に打ててしまうのです。そしてこれを白は防げません。これは、ストナー失敗です。
ここでは話の本筋から離れてしまうので、確実にストナーが成功するために満たすべき条件などは触れませんが、ストナーのような形になったとしても、それが確実に成功するかはまた別問題であることを念頭に置いてください。
最短ストナーを探す
やっとここからプログラミングにまつわる話です。
人力で最短ストナーを見つけるのは骨が折れるので、計算機にやってもらいたいですね。ということで、最短ストナーを見つけるプログラムを書くために、まずはざっくりと道筋を立てましょう。結論を言えば、私は以下の手順を考えました。
- $d$を0で初期化する
- 開始局面から$d$手進めた局面を全列挙する
- 列挙した局面の中から、ストナーになりそうな形(上で紹介した3種類)を満たすものを全て見つける
- ストナーになりそうな形1つ1つについて、受け側がストナー発動を回避できるかを確認する
- 対局開始から$d$手でストナーが見つからなければ、$d$を1つ増やしてもう一度実行する
この2と3を「列挙」、4を「詰み探索」と言うことにして、それぞれ解説します。
なお、プログラム自体はC++で書いて、オセロのルールの実装は自分で以前実装した簡易的なオセロAI"Nats"のものを使いまわしました。Natsは以下で公開しています。
ストナーになりそうな形を列挙する
これについては、本当にただ全列挙すれば良いだけです。黒が打つ手全部に対して、白が打つ手を全部試して、さらにそれに対して黒の手を全部試して…と深さ優先探索を再帰関数で書きました。
ストナーになりそうな形の判定部分のアルゴリズムの解説と、探索の省略ができる部分の解説をします。
ストナーになりそうな形の判定アルゴリズム
これについては、上で解説した3種類のストナー形を軽く実装しました。具体的には石の配置について以下の条件を見ました。例えば黒4形では以下です。
- 青: 辺の形がストナーになりそうか(上で紹介した3種類のいずれかを満たすか)
- 赤: 斜めの部分が全て攻める側の石か
ここで注意すべきは、別にこの時点ではストナーが成功するかどうかなど気にしていないところです。
例えば黒の着手の後に白がf8に置けるかどうかなど、とりあえず気にしません。
ストナーが成功するかどうかは「詰み探索」の部分できちんと確認するので、ここではストナーの最低条件を満たしていればOKということにしました。
省略1 対称形の排除
オセロでは、盤面を回転させたり反転させたりすることで、対称性を考えれば同じ盤面がいくつか出てきます。例えば、以下の4つは向きが違うだけなので同一として扱えます。
さて、上の例はまさにストナー形ですが、ストナーを探す場合に対称性を考慮して変化するのは「どの辺でストナーとなっているか」だと考えられます。
ですから、対称的な局面を同一に扱うためには、単にストナーになりそうな形の判定を1つの辺だけで行えば良いだけです。今回は、下辺でのストナーのみを考慮することにしました。
さらに言えば、下辺でのストナーも2種類あります。「左向きのストナー」か、「右向きのストナー」かです。実はオセロの初期局面は左右対称ではないので、これは対称形とは言えません。しかし、似たような話なのでここで扱います。
左右の問題については、そもそも開始局面自体を左右反転させることで対応しました。
左が通常のオセロの初期配置です。左の局面からの手筋を探した後に、左右反転させた右の局面からも同じように手筋を探索します。こうすることで、右向きか左向きか、どちらか一方のストナー判定だけを書けば済みます。最後、手筋を出力するときに手筋自体を左右反転させればOKというわけです。
省略2 下辺の隅にどちらかが着手できる状態になってしまう場合を省く
ストナーになりそうな形が完成する前の段階でどちらかのプレイヤが下辺の隅のどちらかに着手できるのであれば、探索を省くことにしました。これは、ストナーになる前に隅に着手できたのにそれを逃してストナーをする/ストナーにはまるというのは、さすがにオセロというゲームにおいて気持ちが悪いからです。
省略3 自らストナーにはまりに行く手は排除
$d$手目は必ず攻める側が打つという条件を加えました。これは、もし$d$手目を受ける側が打つとすると、それは自らストナーにはまりに行くことを意味するからです。
最短ストナー自体が、白黒双方が協力してストナー形を実現するという側面を持ちますが、とは言え、自らあからさまなストナーに突っ込むというのは、これもオセロというゲームにおいて気持ち悪く感じたからです。
省略4 残り手数で確実にストナー(になりそうな)形にならない場合を省く
ストナーになりそうな形を判定するには、石の配置を見ることにしました。上と同じ図を再度掲載します。
例えば、この黒4形のストナーを満たすためには、まず黒(受け側)が辺にb8からe8まで4つの石を連続で置かなくてはいけません。さらに、白(攻める側)はg7に石がなければいけません。これを満たす見込みがないとわかった場合には、その時点で探索を打ち切ります。
この見込みについて詳しく解説します。初期盤面から$d$手のストナーを探していて、すでに初期盤面から$l$手打っているとします。そして、例えば黒4形について調べる場合であればb8からe8までの4つ、およびg7の合計5つの場所が空きマスである個数を調べ、この調べるべき空きマスのうち$e$個の場所が空きだったとします。このとき、以下を満たす場合にはそもそもストナー形には絶対になりません。
$$d-l<e$$
右辺は深さ$d$までに打てる残りの手数、$e$はストナーになりそうな形までに確実に着手しなくてはならない場所の数です。
ストナーの詰み探索
さて、ストナーになっていそうな手筋を列挙したら、次はそれぞれが「きちんと成功する」ストナーかを見てみなければいけません。
ストナーの解説において、ストナーが失敗する場面を一つ例示しましたが、現実的に、ストナーが成功するかどうかをルールベースで書くことはまず不可能です。これは、ストナー回避が必ずしも上で示したように1手で終わるとは限らないことと、回避できる可能性のある手筋があまりにもたくさん考えられるからです。
例えば一番最初にサークルメンバーが見つけたストナー(になりそうで実はならないもの)ですが、これは黒からe3g3c5c3h2と進めることでストナー自体は失敗します(黒はストナー回避のためにあまりにも無理しているのでストナーにはまる以上に大損なのですが…)。
これを見ると、黒はd4からf6までのどこかに黒石を乗せつつe列を全部黒にしてしまうことに注力し、白は逆にd4からf6までを全部白にしつつe列に白石を乗せることに注力しています。
上の例では白黒共に注力すべきことが明確でしたので、まだルールベースでも何とか書けそうですが、実はこれはまだ簡単な例で、「攻める側が今すぐストナーを発動させたら(受け側の辺のすぐ隣に着手したら)ストナーが失敗するが、一旦別のところに打ってから発動してみると実は成功する」という場合も考えられます。これがまた厄介なのです。
将棋の詰み探索をヒントに
さて、私はオセロAIを嗜むので、その派生として将棋AIの技術についても少し知っています。将棋は終局間近には詰将棋という状態になるようですが、将棋AIでこのときに使う特殊な探索が詰み探索です。これが何なのかを軽く解説しましょう。ただ、私自身は将棋AIの制作経験がないため、ここでの情報は不確かな可能性が大いにあります。
将棋の詰み探索では、攻める側は王手のみを、そして受け側は王手になった状態を解除する手のみを選んで探索します。さらに、攻める側は詰ませる手(さらに言えば最短で詰みに辿りつける手)を1つ見つけたいのに対し、受け側は不詰みであれば不詰みに導く手を、詰みだとしても最大限粘れる手を選ぶようです。
将棋の詰みについて特殊なことは、手数の長短を一旦考慮しないことにすれば、攻める側は詰む手を1つ以上見つければ良くて、逆に受ける側は詰まない手を1つ以上見つければ良いということです。
ちなみにこういった探索をAND/OR木探索と言うようです。この探索は言い換えると、攻める側の手番では詰む手を1つ見つけ、受ける側の手番では全ての手が詰むことを確認します。前者がOR演算、後者がAND演算の考え方ですので、このような名前だそうです。
将棋からオセロへ
オセロのストナーにおいても、将棋の詰み探索と似たような考えが適用できます。攻める側はストナーが成功する手を1つ以上見つけて、受ける側はストナーを失敗させる手を1つ以上見つければ良いです。ちなみに、今回はストナーのみについて考えるので、攻める側はストナーを成功させるためなら、受ける側はストナーを失敗させるためなら、いかなる大損をも許すことにします。
将棋の詰み探索には効果的なアルゴリズムがいくつか考案されているそうですが、さすがに年末のお遊びでそこまでしっかりと勉強してコードを書く気にはならなかったので、この要件を満たす全探索コードを雑に書きました。実装は深さ優先探索を再帰関数で書きました。
訪問ノード数を減らす工夫
一つの局面から複数の合法手が存在するとき、実は「良さそうな手」から探索すると良いことが知られています(ただ、これはオセロAIに限った私の知る範囲の話ですので、将棋の詰み探索については存じ上げません)。
ということで、攻める側の「良さそうな手」と、受ける側の「良さそうな手」をそれぞれルールベースで考えてみました。
攻める側の「良さそうな手」
- もし下辺の隅のどちらかに置く手があるならば
- 下辺を獲得できるのでストナー成功と見なす
- もしストナーを発動できる(受ける側の辺のすぐ隣に着手できる)ならば
- ストナーを発動してみて、そのストナーが次の一手(黒4形および黒3白1形ならばg8、黒3形ならばf8)で失敗するかどうかを見る
- もし受ける側が隅に置ける状態であるならば
- 受ける側が隅に置けない状態にできる手のみを打つ
- もし受ける側が隅に置けない状態であれば
- 攻める側がストナーを発動できる状態になる手を打つ
- それ以外の手を打つ
受ける側の「良さそうな手」
- もしストナーが発動していない状態で下辺の隅のどちらかに着手できるならば
- ストナー発動前に受ける側が下辺を確保できるのでストナー失敗と見なす
- もし攻める側がストナーを発動できる状態ならば
- 攻める側のストナー発動を阻害しつつ、受ける側が隅(h8)に置けるようになる手を打つ
- それ以外で攻める側のストナー発動を阻害する手を打つ
- それ以外の手を打つ
- もし攻める側がストナーを発動できない状態ならば
- 受ける側が隅(h8)に置けるようになる手を打つ
- それ以外の手を打つ
これによって、それなりに高速になりました。
だが、まだちょっと遅かった…
実は、実装開始当初はストナーの詰み探索など簡単だろうと思っていたのですが、やってみると思ったよりも難しいことに気づきました。想像よりも訪問ノード数が多かったのです。
オセロのルールの実装には私が本気で作っているオセロAI"Egaroucid"のものではなくて、簡易版のものを使いました。しかも、さすがにお酒の入った状態でしたので並列化を実装する気にはなりませんでした。ですので、そもそも定数倍がかなり遅いです。
ということで、ほとんどの場合は許容できる時間でストナーの成功可否がわかるのですが、一部の場合では処理時間があまりにも長くなってしまいました。深夜2時の私はここで諦めて、14手までで詰みが見つからなければ不詰み、つまりストナー失敗として扱うことにしてしまいました。良くないですね…
実行結果(完全版)
ということで、成功するストナーは対局開始13手で初めて現れるようです。その個数は今回41個でしたが、詰み探索の実装をサボっているのでもしかしたらもう少し多いかもしれませんね…
0 stoner-like solutions found but no successful stoner path found at depth 0 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 1 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 2 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 3 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 4 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 5 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 6 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 7 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 8 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 9 in 0 ms
0 stoner-like solutions found but no successful stoner path found at depth 10 in 1 ms
0 stoner-like solutions found but no successful stoner path found at depth 11 in 3 ms
6 stoner-like solutions found but no successful stoner path found at depth 12 in 28 ms
301 stoner-like solutions found and 41 successful stoners found at depth 13 in 4111 ms
d3c5d6e7b6d2c6a6d7e8f8g8b7 longest way to escape: 0 moves
e6d6c5b6c6e7c7d8f8f6e8g8b7 longest way to escape: 0 moves
e6d6c5b6c7e7c6d8f8f6e8g8b7 longest way to escape: 0 moves
e6d6c6f6c4e7e8b6c7d8f8g8b7 longest way to escape: 0 moves
e6d6c6d7c8b6c5e8e7f7f8g8b7 longest way to escape: 0 moves
e6d6c6d7c8b6c7f7f6e8f8g8b7 longest way to escape: 0 moves
e6d6c7f6c6e7e8d8f8b6c4g8b7 longest way to escape: 0 moves
e6d6c7f6c6e7e8d8f8b6b7g8c4 longest way to escape: 0 moves
e6d6c7f6c6e7e8d8f8g8c4b6b7 longest way to escape: 0 moves
e6d6c7f6c6e7f8b6b7d8e8g8c4 longest way to escape: 0 moves
e6d6c7f6c6e7f8d8c4b6e8g8b7 longest way to escape: 0 moves
e6d6c7f6c6e7f8d8e8b6c4g8b7 longest way to escape: 0 moves
e6d6c7f6c6e7f8d8e8b6b7g8c4 longest way to escape: 0 moves
e6d6c7f6c6e7f8d8e8g8c4b6b7 longest way to escape: 0 moves
e6d6c7f6c6e7f8b6c4d8e8g8b7 longest way to escape: 0 moves
c4c5d6e7b6d3c6a6d7e8f8g8b7 longest way to escape: 0 moves
c4c5d6e7b5d3c6a6d7e8f8g8b7 longest way to escape: 0 moves
f5f6e6d6e7d8c6b6d7e8f8g8b7 longest way to escape: 2 moves
f5f6e6d6c6b6e7d8d7e8f8g8b7 longest way to escape: 2 moves
f5d6c6f6e6d7c8b6f7g8f8e8b7 longest way to escape: 2 moves
f5d6c6f6e6d7f7g8c8b6f8e8b7 longest way to escape: 2 moves
e6f6f5d6f7g8c6d7c8b6f8e8b7 longest way to escape: 2 moves
f5d6c6f6e6d7f7b6c8g8f8e8b7 longest way to escape: 2 moves
f5d6c6f6e6b6e7d8d7e8f8g8b7 longest way to escape: 2 moves
c4c5d6e7c6b6d7e8f8g8b7c7c8 longest way to escape: 2 moves
c4c5d6e7c6b6d7e8b7c7f8g8c8 longest way to escape: 2 moves
c4c5d6e7c6b4b6a6d7e8f8g8b7 longest way to escape: 2 moves
c4c5d6e7b6b4c6a6d7e8f8g8b7 longest way to escape: 2 moves
f5f6e6d6f7g8c6d7c8b6f8e8b7 longest way to escape: 2 moves
f5f6f7d6e6g8c6d7c8b6f8e8b7 longest way to escape: 2 moves
e6d6c6f6f5b6e7d8d7e8f8g8b7 longest way to escape: 2 moves
e6d6c6f6f5d7f7b6c8g8f8e8b7 longest way to escape: 2 moves
e6d6c6f6f5d7f7g8c8b6f8e8b7 longest way to escape: 2 moves
e6d6c6f6f5d7c8b6f7g8f8e8b7 longest way to escape: 2 moves
e6f6f5d6c6b6e7d8d7e8f8g8b7 longest way to escape: 2 moves
e6f6f5d6e7d8c6b6d7e8f8g8b7 longest way to escape: 2 moves
f5f6e6d6f7g8c6d7e8b6f8d8b7 longest way to escape: 6 moves
f5f6f7d6e6g8c6d7e8b6f8d8b7 longest way to escape: 6 moves
e6d6c6f6d3b6d7e8e7d8f8g8b7 longest way to escape: 6 moves
e6d6c6f6d3b6e7d8d7e8f8g8b7 longest way to escape: 6 moves
e6f6f5d6f7g8c6d7e8b6f8d8b7 longest way to escape: 6 moves
なお、成功するかどうかはともかく、ストナーの形状を満たす局面は12手で初めて現れるようです。これらの局面はサボっていない詰み探索でも不詰みとなったので、最短ストナーが13手であろうことはバグがなければ確実です。
余談: 最短ストナーのdはいくつから始めれば良いか？
今回、面倒だったので最短ストナーは0手から順番に探索を始めました。しかし、よく考えれば、0手とか1手とかでストナーができるわけがありません。別に短い手数でのストナー探索はすぐに終わるので、考慮する必要がないのですが、興味として考えてみました。
ストナーになりそうな形を列挙するところで、残り手数による枝刈りを行いました。これを拡張すると、最短ストナーが確実に存在しない手数を証明できます。
3種類の各ストナーについて、まず絶対に石がなくてはいけないところに石を置きます。そして、オセロのルールの特徴として、オセロの全ての石は必ず8近傍で連結し、かつ必ず1つ以上の方向で3つ以上石が連続している必要があります。この条件を満たすように最短経路で(人力で)これらの石を連結させます。人力ですので、もしかしたらミスがあるかもしれません(プログラムを書いて確認するほどの気力はありませんでした)。
下図は左から黒4形、黒3白1形、黒3形のそれぞれで実際に連結してみた様子です。
オセロにおいては4+手数(初期局面で4枚置かれているので4つずれる)がそのまま盤面の石数になるため、これらの盤面の石数を数えれば、最短ストナーが確実に存在しない手数がわかります。
上図の石数を数えてみると、左から14、15、15であるため、それぞれに至る最小手数は必ず10、11、11手以上です。
つまり、今回のプログラムでは$d$の初期値を10に設定して探索しても良かったということになります。
もちろん、上に載せたプログラムの実行結果を見れば、これらの例示した盤面は実際には初期局面から到達できないもののようです。初期局面からの厳密な到達可能性は、結構面倒な問題です。
最後に
ところで、こんな記事誰が読むのでしょうか………というか、ここまで読んでくださった方はいらっしゃるのでしょうか……
でも、私が楽しく遊べたので満足です。
所詮3時間実装なのでミスがあったら教えてください。
良いお年を！！！