この木なんの木？ モンテカルロ木と最良優先MiniMax木の"間"に存在する名もなき木々
概要
この記事ではまだ名前が無いと思われるゲーム探索木をいくつか紹介します。この記事では具体的な実装は示さず、概念の紹介にとどめます。
この記事を読むために必要な知識は以下です。
・モンテカルロ木探索＋UCB1
・MiniMax探索
・ボンバーマンの基本的なルール
名のある木々
名もなき木々を紹介する前に、まずは名のある木々を紹介します。
MCTS
モンテカルロ木探索。簡単に言えば、評価関数を使わず、ランダム試行を繰り返して勝率の平均が高い手を調べる手法です。
有名な木なので、検索するとたくさん解説がヒットするのでこの記事では説明を割愛します。
一応参考として、私が初めてMCTSを実装したときに参考にした論文を載せておきます。
→A Survey of Monte Carlo Tree Search Methods
最良優先MiniMax
最良優先MiniMax探索についてはこちらの論文が参考になります
名前にMiniMaxとついていますが、モンテカルロ木探索のような木の伸び方をします。*1
具体的には以下の手順です。
①ルートノードからMiniMax値が最もよい経路を辿って葉へ向かう
②葉に到達したら、子を全て展開し、評価する
③子のMiniMax値（自分の行動の場合はすべての子の最大値、相手の行動の場合はすべての子の最小値）をそのノードの評価値とする
④MiniMax値を親に伝搬させる。このときも、③と同じように評価値がすべての子の最大値、最小値になるようにノードのMiniMax値を更新していく。
⑤ ①～④を繰り返す
以下の図は、①～④のセットを４回繰り返している図です。自分の手番では赤矢印は最大値を親へ返していて、相手の手番では青矢印で最小値を親へ返しています。数字は、葉ノードからルートノードまで評価値を返した後の値です。
簡単に言うと、その時点で分かっている中で最良の選択肢だけを調べて深く伸ばしていくという探索です。これだけ聞くと効率がよさそう＆無駄がなさそうで強そうです。しかし、もちろん弱点はあります。
この探索が弱くなる例を考えてみます。ボンバーマンで、マップ上のブロックを一番多く壊した人が勝ち、ただし爆風に当たると即負けというゲームを考えます。置いた爆弾が爆発するのは３ターン後とします。
評価関数として、以下のようなものを考えます。
・自キャラが爆弾の攻撃範囲に入っていたらマイナス10点
・壊したブロックの数×1点
自キャラが爆風に当たらないことを最も重要視しつつ、ブロックを壊したいという気持ちです。
しかし、最良優先MiniMaxでこの評価関数を使うと一切爆弾を置きません。なぜなら、爆弾を置くとマイナス10点になるので爆弾を置かない枝だけを無限に伸ばし続けるからです。
（相手の手番は図から割愛しています）
このように最良優先MiniMaxは「いったん評価が下がるけど将来的に評価が高くなる」という性質を持った評価関数との相性が悪いのが特徴です。ところで、このような評価関数は出来が悪いです。理想的な評価関数は「１手先の評価値がゲーム終了時の勝敗と一致する」というものだと思っていて、一度下がった評価値が後で上がるのは良くないです。今回の例で言えば、爆風の範囲内に入ったブロックはいずれ破壊されるので加点すべきであるし、爆発の前に自キャラが爆風範囲から脱出可能であればマイナス評価すべきではないでしょう。もし出来の良い評価関数であれば爆弾を置く選択を調べることができます。最良優先MiniMaxの性能は評価関数の出来の良さに大きく影響されます。
余談ですが、最良優先MiniMaxと比べて通常のMiniMax探索は評価値の一時的な減少の影響が小さいです。例えば３手読みなら３手先までの行動を全て調べるので、「いったん評価が下がるけど将来的に評価が高くなる」が３手以内の話であれば評価値が高くなったところを評価してくれるからです。もちろん「２手先で悪化して５手先で良くなる」とかは３手読みでは気づくことができませんが、それでも最良優先MiniMaxほど破滅しません。MiniMax探索は評価関数の出来の悪さを吸収してプログラマを助けてくれる優しい探索です。
本題 -名もなき木々-
さて、MCTSと最良優先MiniMaxを紹介しましたが、どちらも用途がけっこう限られています。MCTSは評価関数を作るのが難しい難解ゲーム、最良優先探索は完成度の高い評価関数を作れる分かりやすいゲームに対して有効でした。しかし、そういったゲームは世の中にあまり多くありません。たいていのゲームは「ほどほどの性能を持つ評価関数が作れるゲーム」が多い印象です。では、そのようなゲームに有効な木はどんな木でしょうか？
ここで、普通のMiniMax探索木が有効なのでは？と思った人がいれば、それはもちろん正しいです。ただしMiniMax木は特定の深さまで全探索する木であり、あまり深く探索できないという欠点を持つため、それを克服できるもっとすごい木がないか、考えてみたいと思います。*2
さて、ここからが本題です。いまからMCTSを最良優先MiniMaxに近づけるように少しずつ変えていきます。その過程で見えてくる木々を見ていきましょう。
※以下、単にMCTSと書いた場合UCTを指すこととします。
木１ MCTS - ランダム
↑MCTS 引く ランダム と読みます。
この木、非常に強いです。いつも愛用しています。
MCTSの最も売りポイントとも言えるランダム性ですが、消します。MCTSのうちランダムな要素とは、プレイアウトを指します。プレイアウトをやめて、評価関数を書いて評価値を計算するように変えます。
子ノードを１つ展開するところも子をランダムに１つ選ぶのではなく、子を全部評価して最も評価値が高いものを返すように変えます。
評価関数を書ける内容のゲームならば、こうしたほうが強くなることが多いです。プレイアウトはゲーム終了までプレイするのを何回もやらないとまともな評価値が得られないので、収束が遅いです。複雑すぎて人間には評価関数を書けない、というようなゲームでもない限りは評価関数を書いたほうがよいでしょう。
また、ランダム性を無くす別の方法として、強いルールベースAIを持っている場合はそれを使って１回だけプレイアウトするという方法もあります。ルールベースAIの行動がランダムでなければ１回プレイアウトするだけ勝敗が分かるので、収束が速いです。
木２ 木１ - 平均化 + MiniMax上書き
評価値を平均するのをやめて、最新のMiniMax値を持ちましょうという変更です。具体的には、UCB1の第一項を評価値の平均ではなく、最新のMiniMax値で上書きするように変えます。つまり、評価値の更新及び親への伝搬を、最良優先MiniMaxのやり方でやるということです。
この木は最良優先MiniMax+UCB1第二項とも言えます。
最良優先MiniMaxであるということは、つまり評価関数の質が要求されるということです。評価値の質が低い場合、具体的には将来的に評価値が高くなる盤面を低く評価している場合や、その逆の場合に性能が下がります。しかしUCB1の第二項があるおかげで性能の低下をある程度抑えることができていて、ちょっと優しい性格にした最良優先MiniMaxともいえます。
木３ 木１ - UCB1
マイナスUCB1と書きましたが、具体的にはUCB1の第二項（探索項）を無くします。
正直、この木はあまり使いどころが無いです。
評価関数の質が非常に高い場合は無駄な探索が減るので強くなりますが、現実的にはそこまで質の高い評価関数は書けないことが多いです。
UCB1第二項は完全に消すのではなく、
・木の浅いところでは普通に使うが深くなるにつれて影響を小さくする
とか
・焼きなましみたいに探索時間内で最初はいっぱい探索するけど最後はほとんど探索しない
というように部分的に変えてあげると良くなることが多いです。
最良優先MiniMax = MCTS - ランダム - 平均化 + MiniMax上書き - UCB1
さて、お気づきの方もいらっしゃるかもしれませんが、ここまで紹介したものを全て組み合わせると最良優先MiniMaxになります。
つまり最良優先MiniMaxとは「MCTSからランダム性を取り除いて評価関数で評価するようにし、評価値の平均をやめてMiniMax値を持つようにし、UCB1の探索項を無くしたもの」だったのです。
まとめ
モンテカルロ木を最良優先MiniMax木に変える過程に、たくさんの有用な木が存在していることがわかりました。
使いどころとしては、評価関数の質が高いほど最良優先MiniMaxに寄せ、質が悪いほどMCTSに寄せるのが良さそうです。評価関数を書けないような理解不能ゲームのときはMCTSを使うとよいでしょう。
とはいえ、各々の木で要求される"評価関数の質"というものがどの程度のものなのかは判断が難しいので、結局いろいろ試行錯誤してみるのが良いのかなと思います。
最後に、この記事は最良優先MiniMaxやMCTSについて私の理解で書きましたが、もし間違っているところがあればご指摘いただけると幸いです。
