Splendor AIでランダム補充の探索を工夫したが、単純なPUCTの方が強かった

Splendor をプレイする policy-value model を、PUCT というゲーム木探索と組み合わせて強くしている。

Splendor は宝石を集めてカードを買い、買ったカードを次の購入の割引として使いながら得点を伸ばすゲームだ。場にはカードが公開されていて、カードを買ったり表向きで予約したりすると、空いた場所へ山札から新しいカードが補充される。

この補充が探索では少し厄介になる。同じ「このカードを買う」という手でも、その後に何が補充されるかで次の局面が変わるからだ。

今回は、このランダム補充をもっと賢く読むことで探索を強くできないか試した。結果は逆だった。補充結果の推定誤差を小さくすることには成功したが、実際の対局では単純な探索より弱くなった。

まずは単純に1つずつ補充結果を引く

現在の PUCT では、1回の simulation ごとに補充候補から1枚を一様ランダムに選ぶ。

同じ枝を何度も読むと、毎回独立に別の補充結果を引く。ここではこれを IID sampling と呼ぶ。

例えば補充候補が16枚あって、あるカード購入の枝を8回読んだ場合、同じカードが複数回選ばれることもあれば、まだ一度も見ていない補充結果が残ることもある。

そこで最初に考えたのは、少ない simulation でも補充候補を広く見ることだった。

重複しないように補充結果を読む

一つ目は、最初の数回だけ補充候補を重複なしで読む方法である。

16通りの補充候補から8回読むなら、同じ結果を何度も引くより、まず8種類を1回ずつ見た方が期待値を正確に推定できそうに見える。

実際、既知の平均値を推定するテストでは効果があった。

誤差は27.6%小さくなった。

さらに終盤では探索回数を128から512へ増やす構成も試した。簡単な tactical test では正しい手を選ぶ割合が91.02%から96.09%へ上がった。

ただし、同じ512回を使って普通の IID sampling をした場合も96.09%だった。しかも普通の IID の方が平均探索深度は17.73 ply、重複なし sampling は16.09 plyと深く読めていた。

つまり、このテストで効いていたのは補充 sampling の工夫ではなく、単純に探索回数を増やしたことだった。

実際の対局でも、新しい探索は固定128回の探索に対して89勝2分109敗だった。pair score は0.450で、強くなったとは言えなかった。

重要そうなカード購入だけ丁寧に読む

次に、全部の chance branch を広げるのではなく、policy が高く評価しているカード購入・予約だけを丁寧に読む方法を試した。

上位2つの対象手について、最初に選ばれた補充枝を8種類まとめて重複なしで評価する。

計算量を揃えた比較でも、補充価値の RMSE は0.10797から0.07820へ改善した。

しかし tactical selection は91.02%のままで、平均探索深度は12.93から12.83へわずかに下がった。

対局結果はさらに明確だった。

新しい探索 176勝 2分 222敗
pair score = 0.4425
95% interval = [0.3962, 0.4888]

推定値は正確になったのに、プレイヤーとしては弱くなった。

終盤だけ探索量を増やす方法も再現しなかった

もう一つ、補充方法は普通の IID のままにして、終盤だけ探索回数を増やす方法も試した。

得点が低い間は112 simulations、どちらかのプレイヤーが11点以上になったら256 simulationsにする。過去の自己対局データ上では平均126.76 simulations相当になり、固定128とほぼ同じ計算量になる設定だった。

最初の200 pairsでは pair score 0.50625だったので、別の初期配置で800 pairsの確認を行った。

結果は0.48531だった。95% interval は [0.4607, 0.5099]、強さ判定に使う one-sided lower bound は0.46466だった。

最初の小さい positive result は再現しなかった。

なぜ推定精度が上がっても弱くなったのか

今回の結果で面白いのは、chance value の推定を改善することと、探索全体を強くすることが同じではなかった点である。

PUCT の simulation 数は有限なので、ある補充枝を広く均等に読むほど、その分だけ他の候補手との比較や、同じ有望手をさらに深く読む回数が減る。

補充結果を広く読む
        ↓
chance value の variance は下がる
        ↓
しかし使える simulation は増えない
        ↓
有望な枝を深く読む回数が減る

今回の protected sampling はまさにこの trade-off に負けた可能性が高い。

一部のカード購入について Q value を正確にしても、他の候補手は相対的に noisy なまま残る。しかも強制的に補充候補へ使った visits は、より深い continuation を読むためには使えない。

結局、単純な IID PUCT を残した

試した chance-aware sampling、重要枝の bundle sampling、終盤への budget 再配分はいずれも採用しなかった。

現時点では、1 simulation につき1つの leaf を評価する構成では、補充結果の variance が探索品質を制限している主因ではなさそうだ。

そのため探索 semantics は、固定 budget で補充結果を独立に sampling する単純な方式へ戻した。

コード側で最終的に残したのは、補充候補の successor state を最初から全部生成せず、実際にその補充結果が sampling されたときだけ作る変更である。これは探索の確率分布を変えず、使わない chance branch を事前に materialize しないための実装上の整理になる。

今回の実験から、少なくとも「chance node をもっと均等に読めば強くなる」という方向は優先度が下がった。

将来、1 simulation の中で複数 leaf をまとめて batch 評価できるようになれば、複数の補充結果を同時に読むコストは変わる。その時には exact expectation や部分的な chance evaluation を再検討する余地がある。

今の実装では、推定器を賢くするより、限られた simulation をどこへ配るかの方が重要だった。

この記事は、実装・実験記録をもとに、本文の大部分をLLMが執筆し、筆者が内容を確認・編集しています。