元々はchokudaiサーチとビームスタックサーチの比較記事にするつもりだったのですが、割と別物だということに気がついて頓挫したので、一部だけを活かして枝刈りだけを書いてみることにしました。
付け焼き刃の知識で書いたので、なにかおかしなことを書いてたらすみません。
アルゴリズム概要
chokudaiサーチ
chokudaiサーチ(ビームサーチ亜種)の利点の話 - chokudaiのブログ
簡単に書くと、ビーム幅を1づつ増やしながら探索処理を反復するビームサーチ。
途中の状態を全部バッファしないといけないのでメモリ使用量が多くなるが、比較的実装が楽で、なおかついつでも探索を打ち切れるので計算時間の調整がしやすいのが特徴。
ソースがリンク切れしているのでideoneのソースを勝手にバグ修正して転載(駄目だったら教えてください)
State ChokudaiSearch(State FirstState)
{
Heap<State>[] HStates = new Heap<State>[MaxTurn + 1];
for (int i = 0; i <= MaxTurn; i++) HStates[i] = new Heap<State>();
HStates[0].push(FirstState);
int ChokudaiWidth = 1; //通称chokudai幅
while (TimeCheck())
{
for (int t = 0; t < MaxTurn; t++)
{
for (int i = 0; i < ChokudaiWidth; i++)
{
if (HStates[t].top == null) break;
var NowState = HStates[t].pop();
foreach (var NextState in NowState.GetAllNextState())
{
HStates[t + 1].push(NextState);
}
}
}
}
var BestState = HStates[MaxTurn].pop();
return BestState;
}
ここで言うHeapというのはいわゆる優先度付きキューのことです。
Beam-Stack Search
一応この項目も残しておく、ただしヒューリスティック法ではなく、どちらかといえば木探索の亜種に近い。
ビーム幅のあるスタックを利用して一定の幅を優先しつつ探索する事と、途中で見つけた解候補と予想値を比較して分枝を枝刈りすることが特徴。（あんまり良くわかってないです）
ビーム幅が1だと深さ優先探索に、最大値だと幅優先探索になるらしい。
ジャッジケースごとにビーム幅を調整して嘘解法で誤魔化すにはいいかもしれない
参考文献
枝刈りchokudaiサーチ
全く違う性質のアルゴリズムとはいえ、途中で解候補を出すのはchokudaiサーチも同じなので、同じ様な方法で一応枝刈り自体は可能。
先程のソースを例にするとこんな感じになる？
State EstimateValue(int t, State NowState) {
// 予想上限値を算出する処理
}
State ChokudaiSearch(State FirstState)
{
Heap<State>[] HStates = new Heap<State>[MaxTurn + 1];
for (int i = 0; i <= MaxTurn; i++) HStates[i] = new Heap<State>();
HStates[0].push(FirstState);
int ChokudaiWidth = 1; //通称chokudai幅
State BestState;
while (TimeCheck())
{
for (int t = 0; t < MaxTurn; t++)
{
for (int i = 0; i < ChokudaiWidth; i++)
{
if (HStates[t].top == null) break;
var NowState = HStates[t].pop();
if (EstimateValue(t, NowState) <= BestState) break; // prune
foreach (var NextState in NowState.GetAllNextState())
{
HStates[t + 1].push(NextState);
}
}
}
// save BestState
BestState = HStates[MaxTurn].top;
}
return BestState;
}
この例では解の最大化を目的としているので、各ターン毎に最良解を記録し、予想値の上限が以前の最良解以下にしかならない値からは次のターンの解候補を生成しない。
予想値で除外されるような解候補はどのみち探索中に候補から外れてしまうので、あんまり意味が無いといえば無い。
実際に過去のマラソンの提出結果で試してみたもののほとんどスコアは伸びなかった。そりゃそうか…
まとめ
実際マラソンマッチで枝刈りが有効なケースというのはあんまりないので、競プロであんまり活用する機会がなさそうだけど、chokudaiサーチの意外な底力を知れて良かった（？）