min-max 探索 vs モンテカルロ
そろそろ言及しておかないとな。
私はゲーム研究者でも何でもない、ただの大学院生ですが、この辺のネタに興味がないわけではない。最近は、特にコンピュータ囲碁でモンテカルロ囲碁というのが既存の min-max search にとって変わられようとしているそうだ。ただこのモンテカルロ囲碁って言い方、汎用じゃないのでモンテカルロゲーム木探索とか何か別の呼び名はないのだろうか。
まず、肝心のモンテカルロ○○。私が理解している範囲では、これは局面の評価値計算の手法で、対局者がある確率分布で確率的に手を打つと仮定して、つまりある局面から始めて、以降の局面の遷移列が確率的に得られるとしたとき、最終的なゲームのスコア（石差とか、あるいは勝ち負け）の期待値を、その局面の評価値にするという手法*1。モンテカルロ〜と呼ぶのはかなり微妙な気がしますが、上記の期待値計算にモンテカルロ法を使うため、そう呼ばれるようです。ふつうは、1 手ごとにサンプルして、特に初期の頃は各局面で一様分布というなめたことをやっていたみたいで、最近はヒューリスティックに分布を決めているみたいです。もっとふつうに学習して確率分布を計算しない理由としては、ちゃんと収束するくらいのサンプリングをするには重すぎるのが原因なのかなぁと妄想しています。
この辺おもしろいのは、min-max 探索が argmax 的なことをしているのに対して、モンテカルロ○○が E(*) している点とか、収束させるのにどのくらいのサンプリングが必要なのかとか、どれくらいまで複雑なモデルなら収束できるのかとか、いろいろありそうで楽しげですね。これ以上は諸事情でいわない。
こういう確率的な議論に持って行くのはわりと現実的だと思っていて、特に例えば min-max 探索はふつう leaf で探索とは関係のない評価関数（オセロだと素性の線形和など）を使うわけですが、min-max が「正しい」のは評価関数（の大小）が正しいという条件がなければ保証されません。しかも、前向き枝刈りというさらに正しさの保証をなくす手法を入れているにもかかわらず、min-max を盲信するのはどうかなと思います。以前 min-max は評価値をちょっと間違えたときこわいので、N-best の平均をとったらどうかなんてことを考えたことありますが、ちょうどモンテカルロ○○と min-max の間くらいの手法なのかなぁと、今更ながら考えているところ。
だからといって、min-max がダメかというとそういうわけではなくて、上記の通り評価関数の精度に依るんじゃないのかなというのが私の予想。オセロなんかの場合、終盤の予想石差はかなり精度が高いですし、割りと深く読めるのでそのままいい結果につながりそうという感じがします。なので、min-max してもいい精度がでそう、さらに評価関数が良ければ move ordering がうまくいってさらに深く読める。モンテカルロ囲碁の方がうまくいってしまう背景に、評価関数の精度が低いことが絡んでいるんじゃないのかなぁと妄想しているところ。
何のためにこんなこと書いたかというと、「モンテカルロ○○はランダム打ちしてうさんくさい、何やってるのかわからなくて気持ち悪い」みたいな論をたまに見ますが、確率的な説明をすれば割りと何をしているのかはわかりやすく、見えやすいんじゃないのかなと思った次第。
*1:と思っているんだが、そういうことを意識していないのかもしれない
