fail-softにするべきたった一つの理由

その昔、one reply(王手されて同玉の1手しかないような場合)でその1手を指すのに長考しているコンピューター将棋ソフトがよくありました。

毎回決まった深さまでiterationをするプログラムですとそういうこともあります。

そこで、one replyのときは即座に指すというヒューリスティック(?)が導入されました。たぶんいまやどのソフトにも搭載されているのかも知れません。

しかし、1手以外はすべて詰むような場合にその必然の1手をなかなか指さないコンピューター将棋ソフトはいまでもときどき見かけます。これは明らかに思考時間の無駄です。

alpha-beta探索は、子ノードのなかで評価値の一番大きなものを探すのですが、評価値が2番目に大きなものは探せません。search関数からalpha以下の値が返ってきた場合、その値については全く保証がありません。こういう状態をfail-lowと言います。

ところが、alpha-beta探索でalphaを更新しなかったときにalphaを返すのではなく、そのときの子ノードの最大の値を返すように変更した場合(fail-softと呼ばれます)、どのような性質を持つでしょうか?

fail-softについてはWikipediaのNegascoutの項目に少し説明があります。
http://ja.wikipedia.org/wiki/Negascout

fail-softにしてもalpha以下の値が返ってきた場合、その値の信憑性には乏しいですが、しかしこれが詰みのスコア(Bonanzaで言うところの-score_mate以下)であれば話は少し違ってきます。

この場合、この子ノードを選んだ場合、詰むことはたぶん言えます。(たぶん…)

ゆえに、fail-softにしてある場合で、探索ルートにおいて2番目に大きな評価値が-score_mate以下であれば、1番目以外の指し手ではどうやっても詰むということであり、それ以上探索せずに探索を打ち切り、1番目の指し手を選択すれば持ち時間が節約できます。

いや、セコイことを言えば探索を打ち切るのではなくそのX.8秒ギリギリまで思考はしてから探索を終了したほうがコンピューター将棋選手権での消費時間的には得かも知れません。(よく知りません。)

そんなわけでfail-softにするわけですが、この性質を活かすと中間ノード(探索ルート以外のノード)でも実質的にone replyであるノードはそのノードからreturnするときまでにわかります。その情報を置換表に書きこんでおいて、次回訪問時に指し手生成を省略したり(置換表に登録されている指し手以外は詰むので)、one reply延長をしたり(実質的にone replyなので)することは出来るのかも知れません。これについても効果のほどは私はよくわかりません。

まあともかく、ある一手以外は5手ぐらいで詰むことが明らかなのにすぐに指さないソフトを見つけたら「いまどきfail-softにしてないんですか?」と言ってやりましょう。ちなみにひよこ将棋はさっきまでfail-softにしてませんでした。すみません。