探索における枝刈りの階層性

電王トーナメントのときにtanuki-.さんとの会話から。

やね「PCのメモリって、階層化されてるじゃないですか?CPUに近いところには、高価だけど高速で、小さなメモリを配置して、CPUから離れたところほど、安価だけど、低速なメモリ(ストレージ)――例えば、HDDを配置する、みたいな?」
たぬき「はい」
やね「将棋の探索も、残り探索depthによって、このような階層化がなされてると考えるとわかりやすいと思うんです。残り探索depthが極めて少ないときは、評価値の見積りが大きく変動しかねないような駒の取り合いや1手詰みを調べるのが有効で、これは静止探索(qsearch)のなかでやっていますよね。そして、残り探索depthが比較的小さいときはfutility pruningとか、razoringが有用で、残り探索depthがかなり増えてくるとsingular extensionやら何やらが有用になってくる。」
たぬき「ほほー。わかりやすいですね。」
やね「でしょ?この説明を閃いたとき、俺、天才とちゃうかなーと思ったんですよ。マジで。」
たぬき「……」

これさえ言わなければ、この人、本当に天才かも知れないのに…という残念そうな瞳をしていた、tanuki-.さんであった。


探索における枝刈りの階層性” への5件のコメント

  1. デカいデータに対していかに手を抜きながら精度を上げるかってことですよね。
    愚直に全探索なんぞやってたら時間足りないですから。
    データに重みを振るのもデータの中に偏りが少なからずあってその偏りを数字化するっていうのが本質でしょうし。
    その重みを振るのもデータがデカくなると手間で自動化したいっていう再帰的ルーチンというか。
    まぁ、どっかで中抜きできるようになるかもですが。

    • > デカいデータに対していかに手を抜きながら精度を上げるかってことですよね。

      そこはもちろん大前提としてあるんですが、本記事の残り探索depthによって有効な枝刈りの性質が違うというのが探索上の面白い特徴かと思いますけどね。

      • 最低起動コストと最高パフォーマンスのバランスですかね。
        燃費が線形じゃないエンジン的な。
        立ち上げてしまえばそれなりに仕事をするけど、立ち上がらないとポンコツっていう。
        得意分野ってあるんですねぇ。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です