将棋や囲碁で用いているMCTS(Monte Carlo tree search)では、末端の局面でplayout(rollout)として局面評価のためにNN(ニューラルネット)を呼び出している。つまりは、実際にはplayoutは行っていない。

NNを呼び出しているなら、これは「モンテカルロ」と呼ぶにふさわしくないという声がある。

しかし、NNを呼び出さずに実際に対局シミュレーションを行っている場合であっても、そこにランダム性があるとは限らない。

// 例えば、やねうら王で1スレッドで探索深さを指定して対局シミュレーションを行う場合、指し手に再現性がある。

なので、「対局シミュレーションにランダム性がある」ことを前提にして、NNを呼び出すなら「モンテカルロ」の名にふさわしくないと主張するのは誤り。

次に、MCTSのMCは「モンテカルロ」だけども、それがモンテカルロ法のことであるなら、MCTSにそもそもランダム性があるのかどうかという話になる。

現在、将棋や囲碁AIで使われているMCTSだと、UCB1(Upper Confidence Bound 1)で有望な子ノードを選択するので、子ノードの選択部分にはランダム性がない。上で書いたようにplayoutにも(NNを呼び出そうが、呼び出すまいが)ランダム性はないのだが、では、どこにランダム性があるのかという話になる。

そこでMCTSの歴史について紐解くと、MCTSはもともとRémi Coulomさんが発明したものである。MCTSに関する最初の論文は、おそらく以下のもの。

// Rémi Coulomさんは、WCSC(世界コンピュータ将棋選手権)の方にも何度も参戦されている。

Rémi Coulom (2007). “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search”. Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006.

// PDF → https://hal.inria.fr/inria-00116992/document

この論文を見ると、MCTSの骨子としては、ランダムに指し手を選んで木(モンテカルロ木)の末端でplayout(対局シミュレーション)を行いながら、木を成長させていくことのようである。

// この論文ではランダムに指し手を選ぶという意味でモンテカルロ法っぽいものになっている。(playoutもランダムプレイヤー)

また、この論文のなかで、Crazy Stone’s algorithmとして、子ノードの選択アルゴリズムとして、現在の最善手よりも優れている確率に従って、各手にシミュレーションを割り当てていることが説明されている。MCTSではroot nodeから木を成長させていくが、その木のなかの子ノード選択のところは、最善手よりも優れている確率に従うようにランダムに選んでいるのだと思われる。完全にランダムに選ぶと効率が悪いことはこの当時にすでにわかっていたようだ。

UCTが発明されたのは2006年(UCB1アルゴリズムを探索木に適用したものはUCTと呼ばれる)なので、MCTS論文発表と同じ時期のようだ。

// Bandit based Monte-Carlo Planning : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296

まあ、MCTSでUCTやら(これは早い段階で囲碁のソフトには導入されたはず)、それを改良したPUCT、それをさらに改良されたものが使われるようになって現在に至るわけである。

名前の由来や歴史的なことはともかく、AlphaZeroの登場以降、MCTSとセットで使われるのはUCT/PUCTかその亜種で、そこにはランダム性はすでに存在しない。

なので、日本語のWikipediaにあるように(MCTSは)「モンテカルロ法を使った」と説明するのは誤りである。

// 現代で普通使ってもいないようなものを、使うのがさも当たり前かのように(あるいは100%使ってあるかのように)説明するのは良くないと思う。逆に、「UCT/PUCTを使うようなMCTSはMCTSと呼ぶにふさわしくない」という主張であれば理解できる…が、まあ、みんなすでにそれをMCTSと呼んでるんだからいまさら変えられんわな…。

ちなみに英語のWikipediaの説明はこうなっている。「モンテカルロ法を使った」などという記述はない。

Wikipediaの誤りについて

Wikipedia、言語によって情報量が異なるのはどうにかならないものなのだろうか。今回のように、コンピュータ・サイエンス関係のページは、たいてい日本語のページが間違ってるのだが…。

// ある用語のページ、複数の言語で用意するなら、どちらかをマスターと固定して、残りの言語はその忠実な翻訳に徹して欲しい。あるいは自動翻訳がもう少し発達したら、英語以外のページをなくしたほうが良いのではと思う。

2021/05/15 13:50 追記

先に挙げたMCTSの論文、囲碁のために発明されたアルゴリズムで、囲碁はplayoutを小さなコストで賢くやる手段が当時発明されていなかったのでplayoutはランダムプレイヤーで行うのが普通であった。

// 将棋だと「ひよこカルロ将棋(2011)」では、playout時には浅い探索をしているのでそこにランダム性はなく、ランダム性は必須ではないとの考え。

囲碁だとAlphaZeroが出てくる直前まで、playoutはランダムプレイヤーなのが普通だった(多少、実戦で起こりやすそうな手を優先して選ぶことはあっても)という将棋との違いがあるようだ。

なので、囲碁界隈の人からすると、playoutがランダムであることがMCTSのモンテカルロたる所以でしょう！という考えがあるようだ。

この点、私は将棋のことしか考えてなかったので、前提となるものが異なっていたようだ。