レートの持ち時間依存性から考える技巧の敗因と探索部最適化

前の記事でも述べたとおり、探索部の最適化を阻む最大の壁は最適な探索パラメータ(アルゴリズム)が持ち時間に依存することです。本番の長い持ち時間(WCSCでは1試合1時間程度、電王トーナメントでは4時間)で探索パラメタを最適化するのは尋常じゃない計算リソースが必要となるため、探索部の最適化は十分な計算リソースを持った強豪ソフトがほぼ独占的な強さを持っているのが現状です。この差を埋めるには、短い持ち時間でも探索部を最適化できる方法を探す必要があるのですが、其のためには、探索部の持ち時間依存性の出処を探る必要があります。

というのも、第四回電王トーナメントでの技巧は、風のうわさに0.1秒から1秒程度の対局で探索部を最適化してたと聞いていますが、これが本当なら、技巧がトーナメント本番で頓死を重ねたのは、技巧の不運だけではなく、最適化の手法にも問題があったのではないかと思っているからです。

そこで、本稿ではweb上に存在するレートの持ち時間依存性のデータを元に、できるだけ少ないリソースで探索部を最適化する方法について幾つかの予想を垂れ流してみます。

注:あくまで私の予想です。正しいという保証はありません。

1.既存の実験データ
やねうらお氏の実験結果

yaneuraou.yaneu.com

1手1秒-8秒ぐらいの間での実験結果をまとめています。

 

uuunuuun氏の実験結果

http://www.uuunuuun.com/single-post/2016/07/09/%E8%AA%AD%E3%81%BF%E3%81%AE%E6%B7%B1%E3%81%95%E3%82%92%E5%88%B6%E9%99%90%E3%81%97%E3%81%9F%E6%8A%80%E5%B7%A7%E3%81%AE%E3%83%AC%E3%83%BC%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0


探索深さを変えながら技巧を戦わせることで、技巧の勝率のdepth依存性を求めています。depthは厳密には持ち時間とは異なるパラメタなのですが、雑に言えば探索時間はdepthに対して指数関数的な形を持つため、depth差を持ち時間差に焼き直して考えることが可能です。

やねうらお氏のコメント
やねうら王のコメントに

// 終盤で大きく持ち時間を変えると、勝率が5割に寄ってしまうのでそれには注意。

という書き込みがあります(source/extra/timeman.cpp)。


2.なぜ、depthに対して線形にレートが変わるのか
実験データ1,2によると、レート差は持ち時間の比率(≒探索深さ)で近似的に表せるようです。持ち時間2倍ならパワーは2倍と言われると何となく納得してしまいそうですが、実際何が起こっているのでしょうか。

持ち時間を長くすると強くなるということは、幾つかの局面の評価が持ち時間に依存して異なり、また、長い持ち時間のほうが正確な予言ができているということを意味します。

中終盤の勝負所では、正しい手を選べば勝てる一方、間違った手を選べば負けるという少々強引な仮定をしてみましょう。このとき、両者の勝率差は、各々が其の局面を正しく評価できる確率の差となります。言い換えれば、小さいdepthにおいては、局面を正確に読める確率はdepthに線形依存しているというわけです。
加えて、やねうらお氏のコメントから、終盤の詰みが絡んだ局面のほうが、depthに対して急な傾きをしていることが予想されます。

また、depthが増えると正確さの上昇率は鈍ることが予想されます。というか、最後まで線形でい続けると、どこかで読みが正しい確率が1になってしまうので、鈍らざるを得ないはずです。以上をまとめると下のような感じになります。

f:id:qhapaq:20170116002610p:plain


3.探索部を最適化するコツ
探索部の最適化は総じて深さと正確さの損益分岐点を求める問に帰着します。持ち時間が一定とすれば、深く読めるようになるほど、局面を読み落とすリスクが高まるため、両者が釣り合う点を探す必要があるのです。

グラフを見直すと、短い持ち時間での探索最適化でありがちなミスは、depthを上げることによる正確さの上昇を過剰に見積もってしまう(特に終盤)ことであると予想されます。こうした傾向は第四回電王トーナメントでの技巧の頓死や真やねうら王の探索パラメタのstockfishとの比較(+vs魔女の持ち時間依存性についての考察)とも一応合致しています。

以上を踏まえると、短い持ち時間で探索部を最適化する際には、以下のような手が有効であること予想されます。

・複数の持ち時間(3点以上)で勝率を測定し、持ち時間が長くなるとともに勝率が落ちている場合は最適化をやり直す

・終盤は最適化をoffにして比較する

・評価値解析ツールQhashimaを使って、勝率の上昇において、逆転勝利の数がどの程度あるかを確かめる

・評価値が一定値になったら自動投了するようにする(終盤の過大評価による逆転を防ぐため)


4.おまけ:Qhapaqの追加検証
探索部の最適化については、まだ深くやっていない+詳細に書くと大会で勝てなくなるので書けませんが、depthの重要さの局面依存性を確かめるべく、全ての手を1秒で指すソフトに対し、30-60手目だけは1秒で指すソフト、60-90手目だけは2秒で指すソフトを戦わせ、各々の勝率を測定してみました。

30-60 370-42-295
60-90 380-50-270

双方において勝率が上がる一方で、1秒程度の持ち時間では、まだまだ終盤のウエイトが大きいことがわかります。(0.5秒でやると、もっと差が開くのですが、ハードの事情でデータが回収できないのです orz)