MCTSの評価伝達遅延を防ぐ方法(MCTS-Solver)
ネタバレ
ぼくのかんがえたさいきょうの手法は既出で、MCTS-Solverというようです。
はじめに
モンテカルロ木探索(MCTS)は、ゲーム木の各ノードを評価しながら探索を行える優秀な探索アルゴリズムです。
しかしCodinGame*1のUltimate Tic-Tac-ToeというゲームでMCTSを使っていたところ、シミュレーション結果が優勢にも関わらず、ある瞬間に劣勢に反転して負けてしまうことが多々ありました。ある手を指されると劣勢なのに、それが評価に反映されずに優勢と勘違いしている状態ですね。
一般に、MCによるプレイアウトはランダムに行われるため、1つだけ良い手(または悪い手)があるのに弱いとされているようです。今回の問題はそれに加えて正しい評価を親ノードに伝える力が弱いためではないかと推定し、その改善を図ったものです。
前提
説明をシンプルにするため、以下の前提とします。
・二人零和有限確定完全情報ゲームである
・ゲーム結果は「勝ち、負け」のみが存在する
・ノードの選択はUCB1-Tunedを使用する*2
また、木の階層によって手番プレイヤーが入れ替わりますが、手番が入れ替わっても解説における主語は同じプレイヤーを指すものとします。階層が変わるたびに主語を入れ替えると書くのも読むのも大変そうなので…!
MCTSの動作の特徴
MCTSは対戦シミュレーションを繰り返すことで良い手を探し、以降のシミュレーションではその“良い手”を選択することでよりシミュレーション精度を上げることができます。
しかしこれだけでは隠れた良手を探すことが難しいので、UCT (Upper Confidence Tree)などを用いて探索が不足しているノードの探索を行います。結果そのノードが良い手であれば選択されやすくなり、徐々に各ノードの評価が調整されるという挙動になります。
MCTSの動作の欠点
前述の通りノードの評価はシミュレーションを繰り返すことで徐々に調整されますが、浅い階層の”良い手”が変化するのにかなりの回数のシミュレーションを要します。例えば、良い手だと思って探索を深めたが実は負け確定である、という場合を想定してみましょう。
上の図は、シミュレーション結果が500/1000で負け確定のノードAと、シミュレーション結果が10/100でまだ勝敗が確定しないノードBを持つツリーの例です。*3
ノードBが多く選択されるようになるにはノードBの評価がノードAの評価を上回る必要がありますが、ノードAの評価を0.1に落とすには最低でも500/5000とするために4000回のシミュレーションが必要です。*4
それまでは評価0.1のノードBを探索する頻度は低くなり、ノードBの探索が不充分になってしまいます。ノードBを充分に探索して親ノードの評価を正しくするには、更に多くのシミュレーションが必要になるでしょう。これが根ノードまで再帰的に発生します。
MCTSの動作の改善
上記の欠点を改善するため、勝敗確定時の評価をシミュレーション外で親ノードに伝えることにしました。動作の変更点は以下の通りです。
- 決着ノードまで展開したとき、決着状態を親に伝播する
ゲーム木の本質として、手番プレイヤーは選択肢の中で一番良い手を採用します。*5最高評価(必勝)が1つでもあればその手を採用し、全ての手の評価が確定したときはその中で一番評価が良い手を採用します。
よって手番プレイヤーが必勝の手を選択できる場合は必勝、全ての手が必負であれば必負で決着済とみなせます。バックプロパゲーションに似た方法で、決着ノードから親を辿りながら決着したことを設定していきます。*6
- 決着済のノードを選択から除外する
決着済ノードを探索することを回避して、未決着ノードの探索に専念できるようにします。必勝のノードは親ノードも必勝になりますし、必負のノードはいくら探索が不足していても絶対に採用することは無いので、選択する必要はありません。*7
- 手の採用では決着も考慮する
採用という言葉はオリジナルで出しましたが、ここでは根ノードから実際にプレイする手を選ぶ行為を指します。
ここまでの動作変更により、勝敗確定がシミュレーションの成績に反映されていない状態になるので、手の採用時にそれを考慮する必要があります。私の場合、決着を親に伝播する時点で過去のシミュレーション結果を書き換えて、シミュレーション結果(=勝率)だけ見て採用するようにしました。
以上により、変更前よりも高速に親ノードのシミュレーション結果を正しい値に近づけることができるようになりました。下の図では互いのシミュレーション勝率の合計が約100%になるはずが135.5%と大きく齟齬があり、中盤以降のシミュレーション能力が大きく違うことが分かります。*8
検討した事項
それって正しいの?シミュレーションが改悪されない?
伝播対象のノードは『選ぶべきでない子ノードの結果』というノイズが混ざらなくなるため、兄弟ノード間でシミュレーション精度が変わることは予想されます。ただMCTSは兄弟ノード間で子の展開状態が違うものなので、精度が違う情報同士で比較するというのはMCTSが元々持っている性質なんですよね。シミュレーション全体の精度がどう変わるかはケースによるため厳密に回答できませんが、MCTSやUCTが本来したい事を阻害してはいないと判断しました。
なお、この記事を書いている終盤で判明しましたが、この手法は既出でMCTS-Solverというようです。参考論文はもうちょっと後の方に記載しています。
過去のプレイアウト結果を改竄するのは美しくないのでは?
プレイアウト結果と選択用のスコアを別で持っても良いと思います。過去のプレイアウト結果を見たいこともあるかもしれません。例えば完全に負け確定のときに、相手のプレイミスに期待するため少しでもシミュレーション結果が良い手を選ぶとか。
引き分けがある場合は?
ゲーム結果が3値以上の場合、決着済みのノードを選択から除外するだけでは本来よりシミュレーション結果が悪くなることがあります。具体的には、引き分け確定の手があるのに他の手を選択して負けたというケースです。
しかしその場合も、「引き分けの子を持つノードに引き分け未満の結果が伝播された場合、自身と自身より親のノードでは引き分けと扱う」とすることで、最低結果を保証しつつそれ以上の結果を出せないか探索することができました。(ここは正しいのか自信が無いです…)
ゲーム結果が4値以上でも、最低保証の値を記憶することで同様の処理ができます。
この処理って重くないの?
決着の親への伝播はシミュレーション終了時、かつ末端ノードまで展開した場合にしか行われないので、私のケースでは他の処理と比べてとても軽かったです。(標準的な対戦で全体の1%未満)
ノード選択時に決着の判断をするのは多少コストがかかりましたが*9、私のケースでは処理全体の3%未満であり、性能の上昇で充分に回収できたと考えています。
でもこれ、未決着ノードには何も伝わってないよね?
はい。
当記事では、決着ノードより親のシミュレーション結果まで手を加えると、探索と知識利用のバランスがあまりに崩れるのでは?と懸念し、決着ノードより親に対しては、MCTS本来の、シミュレーションを重ねることでの修正能力に期待することにしました。
おそらくここの手法次第で探索の性質が変わると思いますが、その点は検証しきれていません。あえて何もせず兄弟ノードとの精度差を出さない方がいいのか、本来勝っていた分を負けに塗り替えるのがいいのか、必敗ノードの探索自体を無かったことにするのがいいのか、はたまた何をしようがそこまで差は出ないのか…。*10
この点については数学や選択関数に強い方の見解を聞いてみたいです…!
と思いましたが、論文を見つけました。
情報学広場:モンテカルロ木探索における子孫の勝敗確定時のプレイアウト結果の修正
「結果を塗り替える 」「無かったことにする」それぞれが選択関数に与える影響を分析しており、別の手法の提案もあります。素晴らしいですね。ここでMCTS-Solverの存在を知りぐぐってみましたが、日本語の情報は少ないようです。
更に上手く活用するには
ノードを決着まで展開させなければこの手法は使えないため、ゲームの決着判定自体に先読み機能を持たせることが有効でした。*11
例えば神経衰弱なら、『相手の獲得枚数+場の枚数<自分の獲得枚数』であれば最後までプレイしなくても勝利確定であることが分かります。
終わりに
手法の正しさに確信が持てない状態で記事を書き始めましたが、裏付けを取っていくうちにそれなりに実績のある手法であることが判明しました。
MCTS-Solverより先のステップについてはまだ調査を進めていない状態ですが、MCTS-Solver相当でも一定の性能向上は見られたため、1つの区切りとしてここまでの車輪の再発明記録を残しておく次第です。
*1:ゲームAI対戦プラットフォームです。
*2:UCT系列であればなんでも良さそうです。
*3:数値は説明のための適当な値です。
*4:説明のために簡略化しましたが、実際にはノードAを探索して勝ちの葉ノードに到達することもあるでしょうし、ノードBのシミュレーション結果も変化するのでもっと複雑です。
*5:貪欲法という意味ではなく、深く探索した結果が一番良い手という意味です。
*6:うちの場合は決着フラグを立ててどちらが勝ったかを設定しました。
*7:勝ちが確定しても最後までプレイする必要はあることに注意しましょう。
*8:レート0.7差と僅差の相手で、中盤までは合計勝率がほぼ100%になることから、序盤性能の差は小さいと推測しました。
*9:フラグを見るだけのシンプルなif文なので、データ構造とメモリアクセス効率の問題かもしれません。
*10:私のケースでは決着ノードの親にも「結果を塗り替える」を適用してみましたが、さほど差は出ませんでした。兄弟ノードとの差を無視すれば、「無かったことにする」が一番正しそうに見えますね…。
*11:勝ちが判明しても最後までプレイする必要はあることに注意しましょう(2回目)