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にしてませんでした。すみません。

週刊ひよこ将棋創刊号plus2を公開しました。

週刊ひよこ将棋創刊号plus2(v1.46)を公開しました。

floodgateには
・shuukan-hiyoko-146_PhenomII_6c6t
という名前で投入しておきました。

今回の修正箇所
・Bonanza6からKKPの評価関数のテーブルがうまく抜き出せていない箇所があったので修正しました。
・fail-softな探索にして、ある1手以外はすべてN手で詰むとわかった時点でその1手をすぐに指すようにしました。
・思考時間を少し調整しました。安定ノードでは少し早めに指すようにしました。
・ponderhitしたときに時間を通常と同じように使うのがもったいないと思ったので前回のiteration回数を基準に今回のiteration回数を決定して探索を打ち切るようにしました。

自己対戦では前のバージョンに6割強勝ち越します。これは本来ならR70ぐらいに相当するはずなのですが、どうせ備後将棋(現在R2361)には歯がたたないでしょうから、floodgateでのRは前のバージョンとほぼ変わらないような気もします。

KKPだけでもまだR50か100ぐらいは強くできそうな気はしているのですが、お手軽に出来る範疇ではないのでどうしようか考え中です。

なお、思考時間の調整は真面目にやりだすと大変難しく、まだまだ改善の余地があります。


追記。いま200戦、前のバージョンと持ち時間4分で対戦させ終わったところなのですが、前バージョンに7割ぐらい勝ち越してました。R150ぐらい上がって…ませんよね。はい。

思考時間制御のこと

思考時間制御、真面目にやると本当に難しいですね。しかし、うまくすれば2,3割持ち時間が長いのと同じ効果があるので探索部を改良するよりよほど即効性があります。

Bonanzaの思考時間制御はCrafty風になっているようです。以下の金子さんのメモが参考になります。

Bonanzaの探索時間の制御方法のメモ
http://www.sgtpepper.net/kaneko/diary/20090213.html#p01

ちなみに上の記事の2-4.の「easy_min > last_value - easy_value」は符号が逆で、正しくは「easy_min < last_value - easy_value」です。


ざっと見たところルートノードでそれぞれの指し手の静止探索の値を求めて、1番目の評価値と2番目の評価値との差によって、局面が安定ノードかどうかを判断するという考え方のようです。

・1番目と2番目の評価値の差が小さい = 安定ノード ≒ 序盤

ってことなのでしょうか。よくわかりません。

ルートノードでのそれぞれの指し手の静止探索の値の分布の仕方で判定するだとか、静止探索ではなく2手か3手の読みのあとに判定するだとか何かもう少し改善のしようはありそうです…が、真面目にやりだすとこれはキリがなさそうだということだけわかりました。

簡単で効果がある方法があればコメント欄で教えてください。

GPS将棋とBonanzaとではどちらが強いのですか？

評価関数の改善
序盤で穴熊に組むと1000点近くになっていた現象は消えた模様
対Bonanzaの勝率は一手15秒64 bit Linux, GPS将棋だけプロファイルフィードバック最適化コンパイルという有利な条件で0.47程度(1000局)
Windows配布版は、上記の実験より速度が劣る分だけ弱くなります。

GPS将棋ダウンロード
http://gps.tanaka.ecc.u-tokyo.ac.jp/gpsshogi/index.php?%A5%C0%A5%A6%A5%F3%A5%ED%A1%BC%A5%C9

0.47ですか…。最新のGPS将棋でもBonanza6に負け越すようです。

GPS将棋の評価関数の設計や実装に天才的な設計能力と実装能力、そして恐ろしい手間暇がかかっているわりには報われていないなぁというのが私の感じるところです。


私はGPS将棋を応援するために、GPS将棋を改良して、改良パッチなどを提供して差し上げたいのですが、しかしVisual C++でビルド出来ない＆ソース解読がしんどいのでなかなか容易ではありません。

そういう意味ではBonanzaはソースが平易で、Visual C++で簡単にビルドでき、多くの協力者に恵まれたというのはあると思います。

GPS将棋が数人で作っているのに対して、Bonanzaのほうは数十人でバグ探しをしたり改良したりしているのに等しく、本当はGPS将棋のほうがポテンシャルがあるのだとしても、Bonanzaの進化のスピードのほうがはるかに速く、Bonanzaに勝つのは容易ではありません。

それでまあ、そういう事情を廃して、GPS将棋の評価関数がどれくらい優秀なのかどうかを判断するため、Bonanzaと同ノード数の探索をさせてBonanzaに勝ち越すかどうかを見たいのですが、それ自体が大変なことでして。

いや、同ノード数ならば当然GPS将棋の評価関数を使ったほうが勝ち越すでしょうから、Bonanzaの評価関数を使う側とGPS将棋の評価関数を使う側とのノード数をどれくらいの割合にすれば互角になるのかを調べてみたい気はしています。

しかし、この問題について考えれば考えるほどBonanzaの3駒評価が決定打のように思えてきます。

GPS将棋のここ数年の進歩を見ていると、あれやこれやいろんな特徴因子を考えたり追加したり差分計算用のコードを書いたりする手間に全然見合っていないように思うからです。

だとしたら、Bonanzaの3駒評価を学習部を改良したり、入玉用に少しだけ改良したりするほうが正しいアプローチのような気がするのです。