From YouTube

スーパーマリオでゆるーくわかる！AlphaGoが世界最強棋士に勝利した意味＝東条雅彦

2017年6月8日ビジネス・ライフ

モンテカルロ木探索をざっくりと理解する

モンテカルロ木探索をおおまかに理解するために、「スーパーマリオ」を例にしてざっくりと説明していきます（あくまでもざっくりとしたイメージを掴むことを目的に記しています）。

＜手順1. マリオを20体、生成する＞

まず、20体のマリオにランダムに動く遺伝子を与えます。

170608tojo_t1

例）
マリオ1は次のような動作をします。

最初の1秒間：「←A」（左にジャンプする）
次の1秒間：「→B」（Bダッシュで右に進む）
次の1秒間：「←B]（Bダッシュで左に進む）
次の1秒間：「→A」（右にジャンプする）
次の1秒間：「A」（止まったままジャンプする）

＜手順2. 優秀なマリオを評価する＞

これら20体のマリオを実際にプレイさせて、より距離が進んだマリオが優秀なマリオだという評価を下します。スーパーマリオは右スクロールのアクションゲームなので、より右に進んだ方が優秀だと判定できます。

＜手順3. 20体のマリオから優秀なマリオ2体を選出する＞

20体のマリオから優秀なマリオ2体を親として選びます。この2体の親マリオが持つ遺伝子データを交叉させて、子マリオを2体、生成します。

親マリオ1×親マリオ2＝子マリオ1（遺伝子1＋遺伝子2）
親マリオ2×親マリオ1＝子マリオ2（遺伝子2＋遺伝子1）

そして、手順1から手順3を10回、繰り返して、子マリオを20体、生成します。

＜手順4 20体の子マリオができたら世代を交代させる＞

20体の子マリオができたら、世代を交代させます。

ポイントは子マリオは優秀なマリオの遺伝子（ゲームをプレイする操作手順）を引き継いでいるため、世代が進めば進む程、どんどんマリオが優秀になっていくという点です。

ゴールできるまで永久にこの世代交代を繰り返します。

＜番外編＞

基本的には手順1から手順4の流れとなるのですが、時々、ランダムで遺伝子データを変異させることもします。この突然変異は、局所的な最適解からの脱出を図ることを狙っています。

例えば、1匹目のクリボーはうまく踏みつけてやっつけられるけど、その直後にキラー（弾丸のような形をしたキャラクター）に当たってしまうような場合、この突然変異が有効に機能します。

近視眼的にはクリボーをやっつけた方が良いように見えても、長期的にはそのクリボーは無視して、キラーに当たらないようにした方が良いということがよくあります。

実際にスーパーマリオのプレイを動画で見てみよう

YouTubeで実際に「モンテカルロ木探索」で学習したプレイと、「評価関数」を使って学習したプレイ（従来の手法）がアップされています。

それぞれ2分程度の動画なので、実際に再生して見比べてみましょう。難しい理論を理解するよりも「百聞は一見にしかず」で、見た方が絶対に早いと思います（両方ともバックミュージックがかかるため、音量にはご注意願います）。

＜動画1：モンテカルロ木探索で学習したプレイ＞

上記のモンテカルロ木探索で学習した方は、敵がいると途中で立ち止まったりしながら、慎重に進んで行くという感じです。ゲーム開始18秒前後で、大勢の敵に囲まれて、突進するとまずいと思ったのか、一旦、止まって後ろを振り返っています。

（動画1の0:18）

170608tojo_3

中には危険なプレーもあるのですが、一瞬でもいいから「立ち止まる」という動作をしており、より人間に近いプレイをしているという印象を受けます。

次に、モンテカルロ木探索を使わない、従来の評価関数を使って学習したプレイを視聴してみてください。

＜動画2：評価関数を使って学習したプレイ（従来の手法）＞

こちらの動画では素人が見ても、人間らしくない操作が目立ちます。

特に特徴的なのが、敵がいようがいまいが、ひたすらBダッシュで突進していく所です。そのマリオの姿は一瞬、無敵のスターマリオなのかな？と錯覚するぐらい最初から最後まで終始、全力疾走で駆け抜けています。ぎりぎりのジャンプで敵を避けたり、敵に激突する寸前でファイヤーを出してやっつけたりと、驚きのファインプレーを連発しています。

私が一番、ビックリしたのはゲーム開始45秒前後で自ら地下に落ちに行って、命からがら這い上がるプレーです。しかも後ろ向きになって這い上がりながら、直前に放っていたファイヤーで画面の右側にいるノコノコをやっつけています（もはや神業です！）。