置換表に経路に依存する局面のスコアを書き込まない
将棋では連続王手の千日手は王手をしている側が負けです。だからと言って連続王手のループを見つけた時点で攻め方の負けと判断したのではGHI問題を引き起します。
さて、いま、定跡を自動構築することを考えます。ここで言う定跡とはプロ棋士の棋譜の何手目までという話ではなく、与えられた局面を通常探索で探索した結果をそのまま定跡として書きだすわけです。
これを定跡と呼ぶにはいささか精度の問題があるかも知れませんが、それでも事前に10分でも20分でもその局面についてじっくり考えられるわけですから、その結果をファイルに書きだしておけば、コンピューター側が実戦でその局面に遭遇したときにノータイム(1手1秒)で指せるわけで、これの効果がないと唱える人は居ないでしょう。(プロ棋士の棋譜から構築する定跡DBは別途持っているものとします。)
ところが、このように局面の情報を書きだすときに経路(そこまでの手順)に依存する場合があります。例えば、その局面に至る前の手順を含めると連続王手の千日手が成立してしまうので次の一手が指せないが、しかしその局面に至る前の手順さえなければ、この局面は攻め方の勝ちという場合です。
定跡ファイルに書き出すときに、経路に依存する情報は書き出すべきではなく、その局面自体の勝ち/負けを書き出したいのです。これはどうすればいいのでしょうか？
実は通常使用している置換表に関しても同じ問題があります。普通、置換表には経路に依存する局面のスコアも書きだしてしまっています。千日手で循環していたので、「この局面は互角」だとか書きだしてしまっています。実際は千日手で循環するのは特定の手順でその局面に到達したときだけです。要するに嘘の情報です。
こういう嘘の情報を書きだしてしまうと、置換表に書いてある評価値を信じていいのかという話になってきます。そこで、置換表の値はあまり信じずに、置換表に書きだしてある指し手だけを信じたほうが勝率が上がったりします。
例えばBonanzaでは、non PV node(α==β-1のnode)でしかhashcut(置換表の値を信じてそのノードの探索を打ち切ること)はしません。PV nodeではhashcutしません。
これは置換表の値が信用できないという問題以外の要因もあるのかも知れませんが、ここでは深く追求しないことにします。
ともかく、置換表にどうやればそれが千日手絡みのスコア(評価値)かどうかを書き出せるのかを考えてみます。
まず、α値を更新したときに、それが置換表絡みのスコアであれば、スコアの上位bitを使って「これは千日手絡みのスコアですよ」(本当のスコアは不明ですよ)とフラグを立てます。次にα値を更新したときにも、直前のα値のこのbitが立っていれば、さきほどの千日手絡みのスコアが、本当はもっといい値かも知れないので、この更新されたαも信用できる値ではないという理由で同じく、このbitを立てる必要があります。(細かい議論は割愛)
このようにしてあれば、千日手絡みのスコアが出てきた場合、それが上位ノードに伝播されていきます。
千日手絡みのスコアであれば、置換表に書き出すときに、スコアは書き出さずに指し手のみ書きだすだとか、まあ何かそういうことは出来ます。
ところがこうやって千日手絡みのスコアを置換表に書き出さないと千日手のスコアに汚染されて、ほとんど置換表にスコアが書き出せない状況が起こりえます。こうなると探索効率は悪化します。
そこで、この方法はおそらくまずいのだと思います。(私はこの方法は実際に実装して試していないのでよくわかりませんが、おそらくあまり効率がよろしくないはずです)
よって、千日手によってスコアが汚染される範囲をもっと明確にすることを考えます。
例えば、次のように局面X,A,B,Cがあったとして、Aの局面へ循環している場合を考えてみます。
X→A→B→C→D→A
Dの局面からAへの指し手は千日手を引き起こす手です。3手前の局面と循環しているからです。ゆえに、ここでは「3手前」(-3)という値をDで得られた評価値の上位bitに格納しておくことにします。
Dの上位ノードであるCではスコアが伝播されてきたときに、ここをインクリメント(たとえば上位8bitを用いるならば0x01000000を加算)し、「2手前」(-2)になります。
Cの上位ノードであるBでは同様に「1手前」(-1)
Aでは同様に「0手前」(0)
Xでは同様にインクリメントして 0 になります。つまり、Xの局面ではスコアはこれ以前の手順に依存していないので、Xの局面のスコアとしてはこれは信頼できる値だということです。逆にBの局面でのスコアは1手前の局面と手順が循環しているのでこの値は信頼できる値ではなく、置換表および定跡DBにはスコアは書きだしてはならないと言えます。(Aの局面については正しいスコアだと私は思うのですが、自信はありません。)
循環しているかどうかの判定は、スコアのMSB(最上位ビット)を見れば一発でわかるという仕組みです。
また、この実装はGHI問題を引き起こしません。
定跡DBを自動構築するときにはこのような実装が必要で、また、実戦において通常探索した結果を定跡DBに書き出すことを考えているなら、千日手に依存する局面のスコアを書きだすわけにはいかないので、このように実装してなければなりません。(たぶん)
df-pnの詰将棋ルーチンにもこの方法が応用できるかどうかについてはいずれまた。
