パズドラ風マッチ3パズルのルート解析プログラムについて

Question

前提・実現したいこと

質問に不慣れなため、ルール違反していたら教えて下さい。

パズドラ風マッチ3パズルのルート解析プログラムを書いています。

ソースコードにも書いていますが、なるべく少ない時間でなるべく大きいコンボを出したいです。

printf("TotalDuration:%fSec\n", t_sum);
printf("Avg.NormalCombo #:%f/%f\n", avg / (double)i, MAXCOMBO / (double)i);

ソースコードの#defineのところは変更しない条件の下で、これらが指標となります。

課題としては、盤面の大幅改造が最適解のときに、改造途中で一時的にコンボ数が低下し、枝刈り対象になることです。

いいアイディアや改善点がありましたら教えて下さい。

ちなみにCUDAでGPU処理しようか計画しています。

該当のソースコード

言語
C++

ソースコード
https://github.com/koduma/puzzdra_solver/blob/master/puzzdra_solver.cpp

解説

概要：
乱数で盤面を生成し、ビームサーチというアルゴリズムでマルチスレッド(openmp)でコンボ数を最大にするようなルートを探索し、出力

評価関数：
1コンボにつき、3消しだと+30点、それ以外だと+20点
2つの同じ色のドロップのマンハッタン距離*2/3点がペナルティ

その他：
盤面数はデフォルトでは1000個に設定してある
理論コンボ数は厳密ではありませんが、16個以上同じドロップがある確率はとても低いので信頼していいです