2009-02-13

_ Bonanzaの探索時間の制御方法のメモ

軽く読んだので紹介します。craftyと大枠は対応しているので、craftyを読んだ経験があれば容易に読めると思います。

  1. 思考時間の割り当て
    set_search_limit_time (time.c) で、手数に応じて、time_limitとtime_max_limitを割り当てる。基本的に前者の5倍が後者。
    craftyではTimeSet (time.c) に同様の関数があるが、少なくとも固定持時間に関してはbonanzaの方が凝っている。
  2. 打ち切り判定
    detect_signals (search.c) で時計をみて探索を止めるかどうかを決める。tcountが使った時間、tlimitとtmax が微調整したtime_limitとtime_max_limitで、終了条件は、
    1. tcount がtmax を越える
    2. stable && tcount > tlimit
    3. stable && (tmax_limit_count*3U<(time_last_search-time_start)*5U))
    4. stable && easy_abs > abs( last_value ) && easy_min > last_value - easy_value && easy_max > last_value - easy_value ) かつさらに条件
    stableの条件は
    • tlimit != UINT_MAX && (
      • ( root_alpha == root_value && ! root_nfail_low ) ||
      • last_pv.type == four_fold_rep ||
      • ( root_nfail_high && root_value + MT_CAP_DRAGON/8 >= last_value ) ) );
    (fail high/low は root でaspiration 探索をしている => iterate.c)。
    craftyの場合は TimeCheck (time.c) で同様の判定をしている。
  3. easy 関係 (当然と思われる手は浅い読みで指してしまう)
    make_root_move_list (=> root.c) rootで指し手を作った時に、各指手について静止探索を呼び値(asort[i])をつける。
    • ( asort[0] > asort[1] + ( MT_CAP_DRAGON * 3 ) / 8 )
    • ( asort[0] > asort[1] + ( MT_CAP_DRAGON * 2 ) / 8 )
    • ( asort[0] > asort[1] + MT_CAP_DRAGON / 8 && asort[0] > - MT_CAP_DRAGON / 8 && I2From(pmove[0]) < nsquare )
    の場合に、上記2-4.の判定を有効にする。3番目には、形勢がそれほど悪くなく(さらに駒打ちでない時?)という条件が入っていて興味深い。
    craftyの場合はRootMoveList (root.c)に同様のものがあるが、easyの判定はbonanzaの方がずっと凝っている。

_ Bonanzaの探索時間の制御感想

経過時間を見ることで、序盤は流して中盤に時間をかけることを実現しているようです。進行度を持っているプログラムは、進行度が使えるかもしれません。

難しそうな局面で時間をきちんと使っているようにみえるのは、stableやeasyの判定の効果でしょうね。パラメータが色々あるので、どのように決めたのか興味深いです。

ソースコードが綺麗で読みやすいです。

GPS将棋もそろそろ時間制御を頑張ると効果がでるのかも。

_ コンピュータ将棋同士の棋譜の類似性

コンピュータ将棋スレッドを見ていたら、gps_lはbonanza 1.2 と似ているというデータを見かけました。残念ながらその後特には盛り上がっていないようですが、コンピュータ将棋同士の棋譜の一致率の大規模な調査はまだ行われていないと思うので、統計データをとれると興味深いと思います。たとえば、仮説として学習で評価関数を作っているプログラム同士はそうでないプログラム同士よりも似ているか、とか、一致しなかった局面にそれぞれの個性は現れるか? (例えばBonanza4は3駒の関係が重要な局面で、gps_lは利きが重要な局面で評価が変わるとか)、色々調べてみたいことがありそうです。類似性に意味を持たせるためにはどのプログラムも一致率が高い局面は除いた方が良いでしょうが、定跡や詰み以外でそのような基準を作れるかどうかも面白そうですね。

ところで、gps_lには飛車や角を切るのが大好きな印象を持っているのでbonanza 1.2と似ていると聞くとある程度なるほどと思います。floodgateのBonanzaはBonanza4とピッタリ一致するわけではなさそうだとか、十分な量のデータがない段階でも、あれこれ想像して楽しめそうです。

[]