ねね将棋では探索アルゴリズムとしてMCTSを採用しているのですが、今まで1手あたりの思考時間は一定でした。 その結果として、飛車先の歩を交換するタイミングなど、有効な手が1つしかない場合でも10秒以上思考してしまって見栄えが悪いです。
明らかな手がある場合にはさっさと指すようにしたいので、どうすれば実装できるか考えてみました。
αβ法による反復深化探索だと、深さが1つ進むたびに読み筋や評価値の変化を指標として定める方法があるようです。次のリンクは、やねうら王での実装箇所です。 https://github.com/yaneurao/YaneuraOu/blob/9f9fb248177b44046d4f26c6b1480502310695bc/source/engine/2018-otafuku-engine/2018-otafuku-search.cpp#L2738 言葉にするのは簡単ですが、229, 715などのマジックナンバーがあって、これを調整するのは大変そうですが…
MCTSの場合は選択的に探索を行うため、ゲーム木全体の深さが1増加するごとに停止を判定するというやり方が取れません。 どういうときに探索を終了していいか考えると、指し手が今後変化する見込みがないときです。 MCTSでの指し手の決定方法は、ルートノードの子ノードへの訪問回数が最大のものを選択します。 つまり、「訪問回数が最大のノード(bestmove)の訪問回数 >> 訪問回数が2番目のノードの訪問回数」となっていれば指し手が変化する見込みが低いといえるでしょう。
実際に探索を行って、一定探索ノード数ごとのbestmoveを記録しました。そしてある時点でのbestmoveが将来的に変化したかどうかを調べました。 訪問回数を比較するにあたり、絶対数と比率の2つの軸があると考えられます。 そのため、全ての子ノードへの合計訪問回数Nと、bestmoveの訪問回数/Nごとに、合計訪問回数が増えた時の変化をプロットします。
bestmoveの変化は563種類の異なる互角局面からスタートし、それぞれ262144回探索して記録しました。
グラフの左端が現在の合計訪問回数、探索が進むと合計訪問回数が右に進んでいきます。探索が進むにつれて、bestmoveが変化する確率が上がっていきます。 1つの局面に対して変化するかしないかは決定的なものですが、局面によって初期条件が同じでも結果が違うため確率であらわすことになります。 線は現在のbestmoveの訪問回数/全ての子ノードへの合計訪問回数の範囲ごとに分かれています。 例えばprob=0.9~1.0となっているのは、90%以上の探索が現在のbestmoveに向かっており、安定している状況です。 このような状況では、将来的にもbestmoveが変化する可能性は低いという順当な結果になります。 逆にprob=0.1~0.2は、5つ以上の指し手候補で迷っている状態なので変化する確率が高いです。 なお、一度変化してから元に戻ってきても変化したとして扱っていますので、必ず右上がりの曲線になります。 現在の合計訪問回数が多ければ、それだけ変化する確率は全体的に下がります。
このグラフを何らかの関数で近似してやり、残り思考時間が尽きるまでにbestmoveが変化する確率が十分低いと判定すれば探索を終了できます。
今回の実験で計測した範囲よりも大会本番のほうが長時間の対局になるので、外挿しても大きく乱れないような単純な関数にする必要があります。 これを満たす関数として、3つの特徴量「bestmoveの訪問回数/N」・「log2(現在の合計訪問回数)」・「log2(将来の合計訪問回数-現在の合計訪問回数)」を入力として、bestmoveが変化する確率(0～1)を出力する線形モデルを設計しました。学習はロジスティック回帰としました。
学習された関数をプロットします。
測定結果を近似できているような気がしなくもありません。
ねね将棋にこのモデルを組み込んで、指し手が変化する確率が5%以下になったらすぐに指すよう実装しました。 定性的な結果として、わかりやすい局面では早めに指すという挙動が実現できました。
時間管理の本来の目的は、難しい局面で持ち時間を多く使うことで勝率を上げることです。 しかし、これを実現するのは結構難しいです。ちょっとやってみてわかったのですが、指し手が変化しない場合でも無駄に探索を行ったほうが強い場合があるようです。 一見無駄な探索でも、置換表に結果が残るため、将来の思考の時に役立ちます。 現局面に対する指し手が確定した時点で打ち切ることを続けていると、時間を余らせて負けるという問題が生じてしまいます。 この対処のため1手あたりの思考時間の基準値を引き上げる（やねうら王で言えば"SlowMover"）必要があるのですが、持ち時間の絶対量に依存するうえ、ponderを行う場合は対局相手の時間の使い方にも依存するためまともに調整できません。
