1.はじめに

　囲碁AIのAlphaGoやそこから派生したAlphaGo ZeroやMuZeroにも用いられているモンテカルロ木探索についてできるだけわかりやすく解説した記事となります。イメージをつかんでいただく用なので割とざっくりした記事になると思います。また、動画でモンテカルロ木探索の動きを出しているのはおそらくこの記事のみなのではないかと思っています。友人に説明するときにも、モンテカルロ木探索の動きを視覚化したかったので今回Unityを用いて視覚化してみることにしました。

2.モンテカルロ木探索とは

　まず、文章のみで概要を説明します。視覚化された方がわかりやすいという方は3.モンテカルロ木探索のうごきの視覚化まで読み飛ばしてください。
　モンテカルロ木探索は、囲碁や将棋などの完全ゲーム木を書くことが難しいゲームを学習可能とした木探索の一種です。完全ゲーム木とは取りうる可能性のあるすべての盤面を木で表したものです。〇×ゲームとかなら最初はどこに〇を書くかで、9通り、次に×をどこに書くかで8通り…と完全ゲーム木を書くことがで来ますが、将棋や囲碁ではすべて書くことは困難です。気になったので調べたのですが、将棋は初手30通りあるそうです。ただ、持ち駒があった場合それを空きマスどこに置くか、持ち駒が複数種類あるのなら持ち駒の種類×空きマス通りの置き方があるわけですから、木を書くことは不可能に近いです。そこでモンテカルロ木探索の出番です。モンテカルロ木探索はモンテカルロ法に基づいた木探索です。モンテカルロ法はランダムに点を打ってその点がどんな割合で円に入っているかで、円周率を求めるやり方で有名な手法です。このモンテカルロ法に基づいた木探索であるモンテカルロ木探索では、最初の一手は価値が高くて、より選ばれていない行動を選択し、その後ランダムにシミュレーションします。また、一定回数同じ行動を選んだ場合、その行動の次の行動も価値が高く、選ばれていないものを選んでランダムシミュレーションします。こうすることで、効率よく木を広げていくことができ、将棋や囲碁も学習できるようになるというわけです。さて、ここまで文章のみで説明してみましたが、やはり文字だけでは正直何を言っているかわからないと思います。次の章からはお待ちかねのモンテカルロ木探索の視覚化に入っていきたいと思います。

3.モンテカルロ木探索の動きの視覚化

　概要を文字だけでも説明されてもわかりづらいと思うので、モンテカルロ木探索の動きを視覚化してみました。こちらはニムという石取りゲームの例です。最後の石を取った方が勝ちで、同じエリアからはいくつ石をとってもいいというルールがあります。このゲームをモンテカルロ木探索で行った動きのイメージをGIFにしてみました。左上のnが試行回数、水色の丸が石を表しています。ノードがオレンジ色になっている部分では先手の勝ち、ノードが水色になっている部分では先手の負けを表しています。

厳密な計算をしていないのであくまでイメージですが、勝率の良いものが優先的に選択されて木が大きくなります。また、選択されていない行動も探索するので負ける手も優先度は低いですが、展開されていきます。木が展開されている部分では価値が高くあまり選択されていない行動をとり、展開されていない部分ではランダムシミュレーションを行います。動画にしてみると、オレンジ色のノードが先に展開され、最後に水色のノードを展開していくのが見て取れます。このようにモンテカルロ木探索では勝ちにつながるノードはどんどん展開され、負けにつながるノードは後から展開して木を大きくしていくイメージになります。このようにしてモンテカルロ木探索では木を大きくして、完全ゲーム木が書けない問題でも学習を可能としています。

4.参考にした記事のリンク

ニムを用いての説明はこちらのサイトから頂戴いたしました
https://www.brainpad.co.jp/doors/contents/01_tech_2018-04-05-163000/
より詳しく解説してほしいという方はぜひこちらの記事を読んでみてください
https://qiita.com/pocokhc/items/392a7f89c79f5e1e6bca