ヴァルのゲームAI開発記

ヴァルの開発記

コンテスト参加記など

この木なんの木? モンテカルロ木と最良優先MiniMax木の"間"に存在する名もなき木々

概要

この記事ではまだ名前が無いと思われるゲーム探索木をいくつか紹介します。この記事では具体的な実装は示さず、概念の紹介にとどめます。

 

この記事を読むために必要な知識は以下です。

モンテカルロ木探索+UCB1

・MiniMax探索

ボンバーマンの基本的なルール

名のある木々

名もなき木々を紹介する前に、まずは名のある木々を紹介します。

MCTS

モンテカルロ木探索。簡単に言えば、評価関数を使わず、ランダム試行を繰り返して勝率の平均が高い手を調べる手法です。

有名な木なので、検索するとたくさん解説がヒットするのでこの記事では説明を割愛します。

一応参考として、私が初めてMCTSを実装したときに参考にした論文を載せておきます。

 →A Survey of Monte Carlo Tree Search Methods

 

最良優先MiniMax

最良優先MiniMax探索についてはこちらの論文が参考になります

 →N人ゲームにおける最良優先探索

 

名前にMiniMaxとついていますが、モンテカルロ木探索のような木の伸び方をします。*1

具体的には以下の手順です。

①ルートノードからMiniMax値が最もよい経路を辿って葉へ向かう

②葉に到達したら、子を全て展開し、評価する

③子のMiniMax値(自分の行動の場合はすべての子の最大値、相手の行動の場合はすべての子の最小値)をそのノードの評価値とする

④MiniMax値を親に伝搬させる。このときも、③と同じように評価値がすべての子の最大値、最小値になるようにノードのMiniMax値を更新していく。

⑤ ①~④を繰り返す

以下の図は、①~④のセットを4回繰り返している図です。自分の手番では赤矢印は最大値を親へ返していて、相手の手番では青矢印で最小値を親へ返しています。数字は、葉ノードからルートノードまで評価値を返した後の値です。

最良優先MiniMaxの木が成長する様子

簡単に言うと、その時点で分かっている中で最良の選択肢だけを調べて深く伸ばしていくという探索です。これだけ聞くと効率がよさそう&無駄がなさそうで強そうです。しかし、もちろん弱点はあります。

 

この探索が弱くなる例を考えてみます。ボンバーマンで、マップ上のブロックを一番多く壊した人が勝ち、ただし爆風に当たると即負けというゲームを考えます。置いた爆弾が爆発するのは3ターン後とします。

評価関数として、以下のようなものを考えます。

・自キャラが爆弾の攻撃範囲に入っていたらマイナス10点

・壊したブロックの数×1点

自キャラが爆風に当たらないことを最も重要視しつつ、ブロックを壊したいという気持ちです。


しかし、最良優先MiniMaxでこの評価関数を使うと一切爆弾を置きません。なぜなら、爆弾を置くとマイナス10点になるので爆弾を置かない枝だけを無限に伸ばし続けるからです。

最良優先だと永遠に爆弾を置かないの図
(相手の手番は図から割愛しています)

このように最良優先MiniMaxは「いったん評価が下がるけど将来的に評価が高くなる」という性質を持った評価関数との相性が悪いのが特徴です。ところで、このような評価関数は出来が悪いです。理想的な評価関数は「1手先の評価値がゲーム終了時の勝敗と一致する」というものだと思っていて、一度下がった評価値が後で上がるのは良くないです。今回の例で言えば、爆風の範囲内に入ったブロックはいずれ破壊されるので加点すべきであるし、爆発の前に自キャラが爆風範囲から脱出可能であればマイナス評価すべきではないでしょう。もし出来の良い評価関数であれば爆弾を置く選択を調べることができます。最良優先MiniMaxの性能は評価関数の出来の良さに大きく影響されます。

余談ですが、最良優先MiniMaxと比べて通常のMiniMax探索は評価値の一時的な減少の影響が小さいです。例えば3手読みなら3手先までの行動を全て調べるので、「いったん評価が下がるけど将来的に評価が高くなる」が3手以内の話であれば評価値が高くなったところを評価してくれるからです。もちろん「2手先で悪化して5手先で良くなる」とかは3手読みでは気づくことができませんが、それでも最良優先MiniMaxほど破滅しません。MiniMax探索は評価関数の出来の悪さを吸収してプログラマを助けてくれる優しい探索です。

 

本題 -名もなき木々-

さて、MCTSと最良優先MiniMaxを紹介しましたが、どちらも用途がけっこう限られています。MCTSは評価関数を作るのが難しい難解ゲーム、最良優先探索は完成度の高い評価関数を作れる分かりやすいゲームに対して有効でした。しかし、そういったゲームは世の中にあまり多くありません。たいていのゲームは「ほどほどの性能を持つ評価関数が作れるゲーム」が多い印象です。では、そのようなゲームに有効な木はどんな木でしょうか?

ここで、普通のMiniMax探索木が有効なのでは?と思った人がいれば、それはもちろん正しいです。ただしMiniMax木は特定の深さまで全探索する木であり、あまり深く探索できないという欠点を持つため、それを克服できるもっとすごい木がないか、考えてみたいと思います。*2

 

さて、ここからが本題です。いまからMCTSを最良優先MiniMaxに近づけるように少しずつ変えていきます。その過程で見えてくる木々を見ていきましょう。

※以下、単にMCTSと書いた場合UCTを指すこととします。

 

木1 MCTS - ランダム

MCTS 引く ランダム と読みます。

この木、非常に強いです。いつも愛用しています。

MCTSの最も売りポイントとも言えるランダム性ですが、消します。MCTSのうちランダムな要素とは、プレイアウトを指します。プレイアウトをやめて、評価関数を書いて評価値を計算するように変えます。

子ノードを1つ展開するところも子をランダムに1つ選ぶのではなく、子を全部評価して最も評価値が高いものを返すように変えます。

評価関数を書ける内容のゲームならば、こうしたほうが強くなることが多いです。プレイアウトはゲーム終了までプレイするのを何回もやらないとまともな評価値が得られないので、収束が遅いです。複雑すぎて人間には評価関数を書けない、というようなゲームでもない限りは評価関数を書いたほうがよいでしょう。

また、ランダム性を無くす別の方法として、強いルールベースAIを持っている場合はそれを使って1回だけプレイアウトするという方法もあります。ルールベースAIの行動がランダムでなければ1回プレイアウトするだけ勝敗が分かるので、収束が速いです。

木2 木1 - 平均化 + MiniMax上書き

評価値を平均するのをやめて、最新のMiniMax値を持ちましょうという変更です。具体的には、UCB1の第一項を評価値の平均ではなく、最新のMiniMax値で上書きするように変えます。つまり、評価値の更新及び親への伝搬を、最良優先MiniMaxのやり方でやるということです。

この木は最良優先MiniMax+UCB1第二項とも言えます。

最良優先MiniMaxであるということは、つまり評価関数の質が要求されるということです。評価値の質が低い場合、具体的には将来的に評価値が高くなる盤面を低く評価している場合や、その逆の場合に性能が下がります。しかしUCB1の第二項があるおかげで性能の低下をある程度抑えることができていて、ちょっと優しい性格にした最良優先MiniMaxともいえます。

木3 木1 - UCB1

マイナスUCB1と書きましたが、具体的にはUCB1の第二項(探索項)を無くします。

正直、この木はあまり使いどころが無いです。

評価関数の質が非常に高い場合は無駄な探索が減るので強くなりますが、現実的にはそこまで質の高い評価関数は書けないことが多いです。

UCB1第二項は完全に消すのではなく、

・木の浅いところでは普通に使うが深くなるにつれて影響を小さくする

とか

・焼きなましみたいに探索時間内で最初はいっぱい探索するけど最後はほとんど探索しない

というように部分的に変えてあげると良くなることが多いです。

 

最良優先MiniMax = MCTS - ランダム - 平均化 + MiniMax上書き - UCB1

さて、お気づきの方もいらっしゃるかもしれませんが、ここまで紹介したものを全て組み合わせると最良優先MiniMaxになります。

つまり最良優先MiniMaxとは「MCTSからランダム性を取り除いて評価関数で評価するようにし、評価値の平均をやめてMiniMax値を持つようにし、UCB1の探索項を無くしたもの」だったのです。

まとめ

モンテカルロ木を最良優先MiniMax木に変える過程に、たくさんの有用な木が存在していることがわかりました。

使いどころとしては、評価関数の質が高いほど最良優先MiniMaxに寄せ、質が悪いほどMCTSに寄せるのが良さそうです。評価関数を書けないような理解不能ゲームのときはMCTSを使うとよいでしょう。

とはいえ、各々の木で要求される"評価関数の質"というものがどの程度のものなのかは判断が難しいので、結局いろいろ試行錯誤してみるのが良いのかなと思います。

 

最後に、この記事は最良優先MiniMaxやMCTSについて私の理解で書きましたが、もし間違っているところがあればご指摘いただけると幸いです。

 

*1:再帰を使った実装もできるらしいです。リンク先の論文の付録で最良優先マックスN探索の再帰実装が紹介されています。

*2:αβ探索を使えば多少良くはなります。

Marathon Match 142 参加記

Marathon Match 142

問題概要

TopCoderMarathon Match 142に参加しました。

 

10x10~30x30のグリッド上にプレゼントが置かれており、画面外から湧く複数のエルフを操作してプレゼントを拾って画面外に持ち去るとスコアがもらえる。プレゼントを守るAIが動いていて、グリッド上に木箱を置いてエルフを妨害してくる。エルフは木箱を拾い、持ったまま移動することができる。拾った木箱やプレゼントを再び置くことはできない。

木箱を置くAIにはMarathon Match 131で作られたものが使用されているらしい(私はmm131には参加していないので、そっちの詳細は分かりません。)

 

結果

暫定4位(システムテスト待ち)

順位表(暫定)

考察

まずはBFSかダイクストラで1人ずつ最短経路でプレゼントに向かって進む実装をするのがよさそう。これをやってみると分かるが、あと2歩でプレゼントに届くというところで1歩先に木箱を置かれるとプレゼントには絶対にたどり着けない。これを解決するために、以下の画像のような動きを考える。この場合、相手は①の場所に木箱を置くことはできない。もちろん②の場所に木箱を置かれるとこの動きはできなくなるが、幸いにもそのような木箱の置き方はあまりしてこなかったのでこれがかなり効いた。

 

やったこと

※以下に書くスコアはローカルでseed=1から100ケース回したときのスコアの合計です(途中から1000ケース)。TopCoder上で表示されるスコアとは異なります。

 

[Score: 370581]

・プレゼントを持ったエルフ、木箱を持ったエルフ

 →BFSで箱を避けつつ最も近い画面外へ移動する

・何も持っていないエルフ

 →BFSで箱を避けつつ最も近いプレゼントへ移動する。そのような経路が無ければ箱へ移動する。

 

[Score: 406833]

・プレゼントの横で箱を持った場合その場で待機する。他のエルフはそのエルフを横にどかして進む。

 木箱持ちエルフがプレゼントの横ではない場所にいる場合、画面外に移動する。

 

[Score: 424120]

・BFSをダイクストラに変えて、木箱へ移動する重みを1000にする。

・「閉じ込められたプレゼント持ちエルフ」をプレゼントと同じとみなす。そうすることで、他のエルフは木箱を拾って救出する動きをする。

 

[Score: 425443]

・最後の1個のプレゼントをN*Nターン経過するギリギリまで運び出さない。(その間に相手が木箱を置いたらそのぶんスコアが増えるため)

 

[Score: 450258]

・木箱持ちエルフは横にプレゼントが無くてもその場に立ち止まり、画面外に木箱は持っていかない。→プレゼント横以外に木箱を置いて広範囲を囲うようなAIに対して有効だった。

・何も持たないエルフの経路を改善。木箱の上を通過する場合はその場所の周囲2マス以上が空きマスであるような経路を優先する。もしそこで木箱を拾った場合、周囲2マス以上が空きがあると次のエルフが通るときに避けやすいから。

 

[Score: 466145]

・木箱持ちエルフは相手AIが箱を置いたことがある場所へ移動する。→箱を置く場所がある程度決まっているAIに対して有効だった。

 

[Score: 471159 (1000ケースで計測: 3653118)]

・複数の木箱持ちエルフが同じ場所を目指すのを避ける

 

以下、スコアは1000ケースで計測

[Score: 3687011]

ダイクストラの経路計算で木箱持ちエルフを踏んで移動するコストを1から10に増やした。これにより「木箱持ちエルフをどかして移動する」が発生する回数が減って、木箱持ちエルフがいるべき場所にいれるようになった。

 

[Score: 3729222]

・木箱持ちエルフが他のエルフのために道をあけるとき、入ってくるエルフが進みたい方向以外の方向へ優先的に避けるようにする。

 

[Score: 3748153]

・もうプレゼントに到達できない木箱持ちエルフは邪魔になるだけなのでグリッドの外へ逃がす(到達できない判定は、木、木箱、自分以外の木箱持ちエルフを通行不可のマスとして判定)

 

[Score: 3769886]

・木箱を通過する経路を選択するとき、すぐ隣にプレゼントがある木箱を優先的に経路として選択する。 →木箱を乗り越えたら必ずプレゼントがもらえるから。プレゼントまで距離があるとその道中に木箱を置かれて道を塞がれる可能性がある

・プレゼント持ちエルフは、木箱持ちエルフだけでなく何も持たないエルフもどかして移動する

・プレゼント持ちエルフは他のプレゼント持ちを引き連れて移動する。 →複数のプレゼント持ちエルフが木箱に囲まれた場合、固まって移動することで脱出するとき一気に全員で脱出できる

 

[Score: 3828602]

・id=4の相手AIはエルフが近づくまで木箱を置かない。さらに1ターンに1つずつしか木箱を置かないので、画面端にエルフを貯めて一気に攻めることでほとんど木箱に妨害されずにプレゼントを回収できる。

 

感想

Gridゲーム楽しい。

mm参加は約3年ぶりでしたが、良い成績を出せて嬉しいです。