PV-MCTSの最大の利点について

簡単な説明は一応やってるんですけどね。

bleu48.hatenablog.com

二番絞りに関しては実行ファイルなんかよりプロジェクト詳細が気になる人が多いみたいです。

二番絞りの件アプローチがあったのは山岡さんだけなんだけど
— 48 (@bleu48) 2020年11月25日

手持ちの計算機だとあんまり高ノードの実験は時間がかかるから好まないんですが一方的に負け越すようなことは少ないようです。浅い探索だと妙に弱いのが持ち味。

RTX2070がちょいと空いたからGCTとdlshogi相手に二番絞りが戦ってみた。エンジンは共通ちょい前に手元でビルドしたもの，時間は15分5秒のフィッシャールール。2勝1敗1分でした。（引き分けはGCT先手） #ある程度時間があると弱いわけないんよね
— 48 (@bleu48) 2020年12月9日

特にfloodgateに流していた時に松下さんの定跡生成ネタと時期がかぶったので、同じ局面で全く同じ手を繰り返すタイプのエンジンではほぼ終局まで定跡でレートを吸い取られることになっていたようで（笑）

で、ここからポエムです。

普段は事実ベースで未検証のネタや妄想の類は抜いてあるのですが、基本的なPV-MCTSの利点についてよくわかってない人が多いようなので漠然とした話をします。

まずMIN-MAX法（αβ法含む）では深さを決めて探索をします。前向き枝狩りがない場合は全探索を行った最適解が得られます。もちろん膨大な局面数を探索することが知られています。これに加えて効率的な前向き枝狩りを進めてきたのが2006年までです。

MCTS法が出たのがこの2006年で、すぐにコンピュータ囲碁界では主流がこちらになります。というのは探索枝数が多すぎてMIN-MAX法的なやり方ではまともに深く読めないからで、確率的ではあっても深く読んだ方が圧倒的に強いものができました。この後、しばらく改良が進みます。しかしながら、基本的に確率的探索のため読み抜けの保証がなく読み抜け問題は引きずったままです。お互い読み抜けが多いような競技ではそもそも問題にならないというかお互い気づかないというような感じです。

PV-MCTS法についてはAlphaZero型が有名になりましたが基本的なコンセプトが最初に提案されたのはDeepMindでもなかったように思います。その知名度より引用される頻度が高いために知名度の再生産が行われた典型例になります。この際に探索枝の展開手法を持ち込んだのが一番の利点で、そこに深層学習のモデルを利用しています。

つまり、学習することで探索する枝を選択的に行う手法となります。よく言われることは人間的であると・・良い手だけを選んで深く読むと・・・

MIN-MAX法でもそうでしたが、PV-MCTS法においても暴力的な計算能力はその弱点を隠蔽します。深く読めて読み抜けが目立たなくなります。しかしながらPV-MCTS法の利点である探索数に比較した探索深さというものは失われ計算効率ががくっと落ちます。これはゲーム木探索の根源的問題です。

で、進んだモデルはどうなるのかというと囲碁のKataGoが代表するように深層学習モデルを大きく高精度化します。

具体的な実験をすると分かりますが探索が一直線に深く進みます。二番絞りの最も学習が進んだモデルはdlshogiやGCTと比較してノード数は半分以下ですが探索深さは軽く10以上上回ることは珍しくありません。depth60を超えるケースも出てきます。分岐数が極端に少ないと言えば理解頂けるでしょうか。それと評価値の変動です。読み筋が変わるタイミングで大きく評価値が変わりますが読み筋が一致している際は他の探索エンジンに比べ非常にブレがないものとなっています。これはMIN-MAX法のエンジンで枝狩りが多く深く探索するタイプのエンジンの傾向と一致します。ただ本件はさらに随分顕著な傾向が出ています。電竜戦の大会中にここに着目した開発者も多かったのではないでしょうか。

弱点ですか。ええ、探索数が少ない時の読み抜けです。探索優先度を深さ方向に極振りしたために選択肢が減って読み抜けることが多くなりました。これはある程度探索時間を増やせば解決できると思います。（もちろんバランスですが）

まぁ、dlshogiがAlphaZeroより小さな深層学習モデルを用いて探索数の暴力で問題解決しようとしたものに対するアンチテーゼとして始めたものですが想像以上にもうまくいったようです。先日の電竜戦予行４が強化学習一回目で電竜戦本戦が二回目ですからね。

ここまで読めば気づくと思いますが深層学習モデルの精度が優劣を決めることになります。特に読まない枝の精度です。囲碁の大会には出ておりませんが恐らくそういった状況になっていると思われます。大きな高精度モデルを膨大な計算量で学習させていることでしょう。

私も久しぶりに暴力的な計算能力を欲しております。

そういえばこれ本当に過学習だったんでしょうか？検証に入ります。