中合い問題の解説 その3
3手詰めで、利きのない場所への打ち中合いが省略できる条件については、いままで十分考えてきました。
1) http://d.hatena.ne.jp/LS3600/20100101 新春お年玉プレゼント 詰め将棋問題
2) http://d.hatena.ne.jp/LS3600/20100105 中合い問題の解説 その1
3) http://d.hatena.ne.jp/LS3600/20100106 中合い問題の解説 その2
私の考えは、1)で、いまも変わりありません。保木さんの追加実験の結果、おそらくこれは正しいようです。以下、その保木さんのコメント。
hoki 2010/01/05 11:29
LS3600 さん、簡単にできそうな以下の実験をとりあえずやってみました。
中合は同○の王手で再帰的に２手延長していく３手詰みで、王手している駒が１つの王手回避の場合に、以下の条件を満たす枡への中合を無視できるか検証する。但し、中合は受け方の利きが無い枡（pin されている駒の利きは除外）への打ち及び移動。
・斜め方向の中合の場合４以上離れている枡
・縦・横方向の中合で盤の辺沿いでは４以上
・それ以外は５以上３日間程度５分切れ負けルールで Bonanza 同士を対局させ、この仮定をした場合としない場合で３手詰み関数が異なる結果を返すかどうか検査しましたが、そんな場合は今のところないようです。
このままもう少し走らせてみますが、１週間待っても反例が出現しなければこの仮定を Bonanza にも採用してみようと思います。
hoki
hoki 2010/01/05 22:41
> 了解です！Bonanzaがまた強くなりますね！！このブログに書かれている情報を参考にしてプログラムを書き直した所、終盤では nps が１割増し程度になる場合があるようです。この調子で改善を進めると、本当に一部 5手詰みまで認識可能になるかもしれません。LS3600 さんにいろいろ教えて頂いて、mate_in3ply() にまだまだ改良の余地があると気づきました。ありがとうございます。
3手詰みを 5手詰みにする改善などは余り華々しい努力ではありませんが、こういう努力をコツコツと積み重ねるのも大切ななずです。。。きっと。
プログラマ向けにもう少し突っ込んだ解説をします。
中合いは、受け方(玉を詰まされる側)の応手なので、これはAND/ORツリーのANDノードです。よって、ひとつでも不詰みの応手が見つかればこのノードは不詰みと判定して良いのです。
このORノードでは、中合いする場合は玉に近い場所から順番に応手を生成していきます。このため、例えば、玉からの距離5マス目に中合いする手を調べているときは、玉からの距離2,3,4に中合いしても詰むことが確定しているのです。(玉からの距離2,3,4に中合いしても詰んでいたので、詰まない手が無いかを探しているわけで)
もし、仮に、距離2,3,4に中合いしても詰むならば、距離5以上の地点に中合いしても詰むという定理が存在するなら、距離5以上は調べるまでもなく詰むのです。よってこれらの応手を省略できます。(Bonanzaの3手詰みに限った話) 今回の思考実験および、保木さんの追加実験により、そのような定理がどうやら存在するのです。(正確な条件については、冒頭にあげた記事urlをご覧ください)
この定理の名前が欲しいので「3手詰みの打ち中合い省略定理」と名付けます。
■ 「3手詰みの打ち中合い省略定理」のORノードへの適用
この定理はORノード(攻め方。王手になる手を生成する側)でも適用でき、玉から3マス離れたところに打って詰まないなら、それ以上離れたところから打っても詰まないのです。よって、それについては王手になる手を生成する必要すらないのです。(ただし、打ったばかりの駒が取られる場合と、4マス以上離れた場所だと飛車が成れる場合は除きます。例えば、玉から5マス離れたところに打った場合、この飛車がとられず、かつここが敵陣で飛車が次に成れるならば、これで3手詰みでなければ、玉から6マス以上離れたところに打っても詰まないことは確定します)
再帰中合いとは、Bonanzaでは、利きのない場所に中合いした場合、その駒を取ってそして再帰的に3手詰み判定ルーチンを呼び出して詰むかどうかを調べます。この再帰的な呼び出しが発生するということは、他の手(玉が逃げる手や、近接合いなど)ではすべて詰みを回避できなかったことを意味します。
ということは、玉から6マス離れたところに中合い→同飛→玉から5マス離れたところに中合い→同飛→… のように何度も中合い判定をするのは無駄です。何故なら、中合いは、玉に近い地点からおこなうため、玉から6マス離れたところに中合いしているフェーズにおいては、それより近い地点(玉から5マス目など)に中合いした局面は詰むことが確定しているからです。
すなわち、6マス離れたところにYを中合いして、同飛→5マス目にZを中合い→同飛 と取らせた局面は、単に5マス目にZを中合いして同飛と取らせた局面より、駒Yを相手に渡しているため、受け方の駒が減っている局面であり、単に5マス目にZを中合いして同飛とさせた局面より受け方にとって劣等した局面です。(持ち駒がひとつ損しているので)
しかも、単に5マス目にZを中合いして同飛とさせた局面は、すでに詰むことが確定しているので、これより劣等している「6マス離れたところにYを中合いして、同飛→5マス目にZを中合い→同飛」は当然詰むのです。
つまり、指し手生成に一定の順序があれば、置換表なしにこのような劣等局面の関係を利用でき、応手を省略することができるのです。
Bonazna 4.1.2ではそのような無駄な処理があり、これがパフォーマンスに深刻な影響を与えていました。私がこれが大変無駄であることを保木さんにお伝えしたのが、今回の中合い問題を詳しく考えるきっかけとなりました。
