fruit chessにおける多重反復深化とFutilityPruning

http://chocobo.yasuda-u.ac.jp/~nisimura/mymove/index.cgi?no=443

>あと、Bonanza が部分的に多重反復深化にされているのは、よく意味がわからずスッキリしないなあと思いながらも無理やり真似しているので>すが、先日 Fruit のソースを少し読んでみて、Fruit も部分的に多重反復深化になっていましたが、スッキリと実装してあって、

Bonanzaの高速化の謎ですが、
自分の方としては、コードの実装方法が正しくないってのも、かなりありそうな感じです。
私も以前からfruit chessのソースをときおり見ているんですが、
けっこう自分で勘違いしている部分とかもありました。

多重反復深化は、
search_full.cppのこのへんですね

   // Internal Iterative Deepening

   if (UseIID && depth >= IIDDepth && node_type == NodePV && trans_move == MoveNone) {

      new_depth = depth - IIDReduction;
      ASSERT(new_depth>0);

      value = full_search(board,alpha,beta,new_depth,height,new_pv,node_type);
      if (value <= alpha) value = full_search(board,-ValueInf,beta,new_depth,height,new_pv,node_type);

      trans_move = new_pv[0];
   }

IIDReductionは2、IIDDepthは3です。
要するに、残深さ3はあるときに、深さをひとつ下げて探索って感じですね。
なぜ、value＜alphaで再探索してるのかはよくわかりませんが、
↑ようするに、aspiration Searchみたいなもんですね。

このコードは、hashに手が無いときに、多重反復深化でhash手を作ってるわけですね(tras_move)
多重反復深化は、うさぴょん育ての親さんのコンピュータ将棋のアルゴリズムを見て、いままで参考してましたが、
こういう書き方もあるんだなあと思いました。

Bonanzaの探索ロジックは、fruit chessとかなり似てると思いますね。
ただ、Futility Pruningの実装方法は違う部分も多いと思います。
Bonanzaは、loop前にstand_pat-MARGINがbeta超えてればbetaカットしてるみたいですが、
fruit chessにはそういうコードが無いみたい（静止探索ではβカットはやっている）
loopの中で、

        if (!in_check && new_depth == 0 && !move_is_tactical(move,board) && !move_is_dangerous(move,board)) {
            if (opt_value == +ValueInf) {
               opt_value = eval(board) + FutilityMargin;
            }
            value = opt_value;
            if (value <= alpha) {
               if (value > best_value) {
                  best_value = value;
                  PV_CLEAR(pv);
               }
               continue;
            }
         }

とαカットしてる部分はBonanzaと近いですね。
ただ、自分にとって良さそうな手とか、相手の良手になりそうなものはカットしないように注意してますね。
fruit chessは海外では「疑い深いchessプログラム」と呼ばれてるようです。
要するに、安易に処理せずに、疑って探索するプログラムみたい。
（nullMoveも単純にカットせずに確認している。詰めが見つかってもより深さが浅いものを優先している。随所で疑いの目が利いていると思います）

futilityも、
自分で実装してると、上の例ではevalつかってますけど、
それだと、静止して無いのでかなりマージンをとらないと副作用がきついです。
かといって静止探索を呼ぶとオーバーヘッドが高いし……。

>マージンが多少大きくても残り深さが０になる少し手前で読み筋がおかしくなるだけなので、致命的にはなっていないということだろうと、

　私の方は、futilityの関係で大駒がただで突撃したりして末端が暴れて、まだなかなかうまく行って無いです(´･ω･`)