Futility Pruning大研究！

日本語世界で検索しても情報があまり無いんですが、
amazonで品切れになってる洋書とかに書いてるようですが、
GPS将棋さま関係の情報では、

http://d.hatena.ne.jp/tawake/20050705/1120562557
http://www.sgtpepper.net/kaneko/diary/200507.html
http://www.sgtpepper.net/kaneko/diary/20050706.html

>世間で多く信じられているように、コンピュータチェスの方式は単なる全幅探索方式である、*わけではない*。
　↑amazonの例の洋書の書評ですが（うさぴょん育ての親さんの文章）
　全幅探索といっても、素直に全部探索してたら、とくに将棋は絶対無理と思う。
　Bonanzaはどうして1秒で9手とか読めるんだろ？　謎だ……
　込み合ってくると、可能な手が200手とか行きますからね。
（将棋の場合、可能手が、１局面で、理論上は最大600ぐらい出る可能性があるそうですが。一応、配列は600で取ってる）

通常、PVS探索の末端で、

if( depth==depthMax )
    return negaMaxQui( SorE,-MUGEN,+MUGEN,depth,depth+2);

のように、静止探索を読んでるのですが、

一手前で静的評価値が探索ウィンドウを十分外れていたらカット(Futility Pruning at Frontier Nodes)、
もう一手前でも大きく外れていたらカットすると効果あるね(Futility Pruning at Pre-Frontier Nodes)、
そのさらに一手前でもとても大きく外れていたら探索深さを減らしても良いかな(Limited Razoring at Pre-Pre-Frontier Nodes)

という3本立てらしい。（但し王手は除外）
チェスの場合、上記の「外れる」をあらわすマージンには、それぞれ、ポーン、ルーク、クイーンの駒価値数を使うとうまくいってるらしい。

>どのみちリスクを避けられないならばProbCutの方が扱いやすい可能性もある。
　ProbCutってオセロの解説で見た覚えがありますね。えーとなんだっけ？

>静止探索で、パスをしたら評価値をそのまま使う(``stand pat'')を前提としているようで、GPS将棋にはそのままでは適用できない。
　うーん。意味がわからない。なぜだめなんだろう。

具体的にコードで書くと……（だいぶ変だったのでやや修正）

#define MARGIN1 KomaValue[ FU ];
#define MARGIN2 KomaValue[ GI ];
#define MARGIN3 KomaValue[ HI ];

int negaAlphaBeta(alpha,beta,depth,depthMax)
{
  int temp = negaMaxQui( SorE,-MUGEN,+MUGEN,depth,depth+2);

  if( depth+3==depthMax && temp+MARGIN3 < alpha ) depthMax--;
  else if( depth+2==depthMax && temp+MARGIN2 < alpha ) return temp;
  else if( depth+1==depthMax && temp+MARGIN1 < alpha ) return temp;

  if( depth==depthMax ) return temp;

  tp=generateAllMoves();

  for(i=0;i<tp;i++) {
    move(i);
    v = -negaAlphaBeta(-beta,-alpha,depth+1,depthMax);
    undo(i);
    if( v>alpha ) alpha=v;
    if( v>beta ) break;
  }
  return alpha;
}

みたいな感じで動くのかな？
よし、今夜、帰宅したらやってみよう！