最短手数の詰みを見つける話 - ひよこ将棋、はじめました。

ひよこカルロ将棋v0.18が落ちる原因がわかりました。この原因を説明するのは非常に難しく、たぶん他の将棋ソフトはうまくやっているのだと思いますが、ひよこはうまく出来ていなかったということで、ざっと理由だけ開発者向けに書いておきます。

まず、現局面が1手詰めであるとき、このときの評価値をscore_mate1plyという定数で表現してあるものとします。Bonanzaとかそうなっていますね。

現局面が3手詰めである場合、score_mate1ply-2と表現します。3手詰めのほうが1手で詰めるよりは評価が低いわけですね。こうすることで普通にαβ探索をすれば手数の短いほうの詰みを発見できるようになります。

この詰みの値を置換表に書きこむときには注意しなくてはなりません。それは、例えば探索深さ5(探索開始局面から4手進めた局面)において、3手詰めがあることを置換表によって見つけたとします。そのときの評価値とは、4+3 = 7手詰めです。すなわち、score_mate1ply-6です。このように置換表から詰みの値を取り出すときには現在の探索深さを考慮しながら復号化しなければなりません。

いま、search関数(αβ探索を行なう関数)で、呼び出された時点でalpha = score1ply-2 (3手詰め)であったとします。ところがこのときの探索深さが5であれば、何か1手でも合法手があるのであれば、最悪でもscore1ply - 4(5手詰め)であることは確定します。このように、最短手数での詰みを探そうと思うと探索深さに応じて、alphaの値を補整していかなければなりません。Bonanzaでもやっています。search.cでalpha_oldという変数にalphaを代入した直後です。

この処理が結構やっかいというか、気持ち悪いというか、速度的に無駄というか、そういう風に思えるので、私はあまりやりたくはないのですが、しかし3手で詰む将棋を15手ぐらいかけて詰ませると「コンピューターって馬鹿なのね」とか言われても悔しいので、この部分をきちんと処理することを考えます。

Bonanzaでは、alpha_oldをalphaに代入したあとに、このalpha値の補整をして、そのあと探索します。合法な指し手が1手でもあるなら、first_move_expandedが非0になり、その場合、alpha値の補整によってalpha値が変更されているのでこのときのbestmoveを置換表に書いておきます。

私のプログラムでは、指し手を1手ずつ試すループにてalpha値が更新されるごとにbestmoveとしてそのときの指し手を代入するように書いていたのですが、このループでalpha値が更新されない場合がありました。このとき、alpha_old≠alphaなのに、bestmoveが不在ということになります。

なぜこのループにてalpha値が更新されなかったかというと、それは次の指し手によって、劣等局面(盤面の駒の状態が同じで手駒だけが減っている局面)に到達するからで、この場合、-score_inferiorという特殊な定数が返ります。(ちなみにBonanzaもそうなっています)

Bonanzaの場合、このときpv_closeでPV(最前応手列)を更新していて、alpha_old≠alphaのときに置換表に書きこむ値は、ここから取得しています。

  hash_store( ptree, ply, depth, turn, value_exact, alpha,
     ptree-&gt;pv[ply].a[ply], state_node );

しかし、私はPV用の配列を持ちたくなかったのでPVは必要なときに置換表からかき集めてきています。(Stockfishとかponanzaとかもそうなっているそうです。)

PV用の配列を持っていない場合、どうなるのかというのがややこしいです。そもそも、score_inferiorは、反則手並の扱いをしていて(そんな手を自分は死んでも指さないという意味で)、score_mate_1plyより大きな値をつけてあります。

ということは、-score_inferior(自分による即詰みがある局面で、自分の無駄な駒捨てに対して相手が同玉と応じたことにより自分の劣等局面に突入した)では上位ノードのalphaの値(-score_mate_1ply+X)を更新しません。

しかし合法な指し手には変わりないので、hash_storeを呼び出すときにbestmoveにこのときに指し手が代入されていないと、上記のhash_storeでbestmoveを設定しないまま呼び出すことになり、この部分で初期化されていないbestmoveの値を書き込んでしまい、今度その値を取り出したときに非合法手であって、その非合法手で局面を進めてしまい、落ちるというのがひよこカルロ将棋v0.18が落ちていた原因です。

このへん非常にややこしくて、私はどうするのがベストなのかよくわかりません。

search関数でalpha_oldにalphaを代入するタイミングをalpha値の補整をした直後に変更することで一応上の問題は回避できるのですが、しかしそうすると、合法手が一つでもあればそれを置換表に書き出すという動作にはならなくなってしまいます。とは言え、その動作が本当に適切なのか私にはよくわかりません。

あと、劣等局面に突入して、詰むことは実戦の将棋ではよくあることで、間違えて歩打ってしまって、そのあとその歩を成り捨てて同玉以下詰むことだってあるわけです。ゆえに探索ルート以前の局面に対する劣等局面だからと言って、そこが詰まないという保証はないわけです。

また、あと4手でどう応じても詰むという状況であるなら、劣等局面へ入ってでも、手数を伸ばすということは出来ます。「劣等局面に入る手を死んでも指さない」という処理が本当に正しいのかどうかはよくわからない意味があります。

それはつまり、「あと5手でどう応じても詰むというとき、劣等局面に入る手も考慮した上でなければならない」と思うのです。「この手は劣等局面に突入するから相手は指してこないだろう」というのはおかしいわけです。

そういうことを考えだすとこれは大変難しい問題に属することがわかります。