オッズの魔法使いが気になる~モンテカルロ探索を説明しよう!~(コンピュータ将棋選手権)
オッズという名前に、皆さんは心当たりがあるでしょう。
何?オズの魔法使いをおしゃれに言っただけだろって?
お得意のwikiからの引用をしましょう!
ギャンブルにおけるオッズ
オッズは競馬などギャンブルのブックメーカーが見込みを示す方法として、長らく使われてきた。
wikiより
ところで、ブックメーカーって何かって?
ここはギャンブルを解説するブログではないので、
ないので…
オッズ比
まぁ、正直ギャンブルの話はいいんだ。オッズというのは、ある出来事が起こりやすいかどうかを示す。「起こりやすいことが起こった!予想してた!」というのは大したことじゃない。
当たり前だ。
だから、起こりやすいことを予想しても、ギャンブルだと配当はあんまり貰えない。起こりにくいことを予想していた人、すごい。配当がたくさんもらえる。
つまり、皆が「なかなか起こらないだろう」と考えていることには、配当が高くつく設計になっているのだ。
気になったのは、モンテカルロ木探索という部分。
そうだよ!モンテカルロ木探索を説明するためだけにこの前置きがあったんだ!
今回はモンテカルロ木探索について説明していきたいと思います。
この手法、囲碁で効果を上げたことで名高いですね。この手法が出てきた当時、コンピュータ囲碁業界は悲しみの時期にありました。
オセロはとっくに攻略された。
チェスもごり押しだったけどなんとか人間のトップに勝った。
当時は、革命を起こしたボナンザの影響で、将棋が人間を蹴散らす時期に来ている。
囲碁は…
この理由や背景は他の記事に解説を譲ります。
ざっくりとした解説だけしましょう。
まず、囲碁は盤面が大きすぎます。
オセロやチェス、将棋は8x8とか9x9とか、そういう次元でした。
でも、囲碁は19x19。飛びぬけて大きいのです。
これが何を意味するかというと、コンピュータ得意のごり押し(ひたすら計算して未来を見る!)が通じないということになるのです。
『どういうことですか?』
これを業界用語(?)で言うと、
「囲碁は合法手が多すぎる」という話になるわけです。
その合法手についての話もここでしておきたいと思います。
合法手とは、ルール上可能な手のことです
将棋で言えば、二歩や、動けない位置にコマを動かすといった反則がありますね。そういった反則以外の、指していい手を、合法手といいます。
将棋や囲碁で貴方が普段指したり打ったりしている手、それはほとんどが合法手です。これが、コンピュータが探索する範囲になります。
囲碁の問題は、それがとてつもなく複雑であるということだ。チェスの平均的な手数はおよそ35通りだが、囲碁のそれは250通りである。それぞれの手のあとには、さらに250の選択肢がある。そのため最も強力なスーパーコンピューターでさえ、すべての手の可能性を見通すことはできない。ハサビスが言うように「宇宙の原子の数よりも囲碁の打ち手の数の方が多い」のだ。
から引用。ハサビス氏は、かの有名なAlphaGoの開発者である。
更に、囲碁は同じ型の反復が存在する。
これを、コウという。
そっくりな局面が繰り返すことで、これもコンピュータの探索を複雑かつ負荷の多いものにしている。
将棋には、千日手をいうルールがあり、これを回避している。チェスは、試合が進むに従って駒が減るので、同じ形が訪れることはほぼない。
それに、評価関数が作れない。駒を取ったら優勢とか、そういう分かりやすい基準がないのだ。広い場所を占拠していると思っても、その石が死んでいたら何の意味もない。
これらの問題によって、コンピュータ囲碁はなかなか発展できずにいた。
その膠着状態を破ったのが、モンテカルロ木探索である。
評価値が作れないなら、なくてもいいようにすればいいのよ!
というと大袈裟だが、要するに、勝ち負けを見ればいいというは究極の発想に至るのである。
「さっきコンピュータで読み切れないって言ったじゃないか!」
その通り。だから、全部は見ない。
自分がいい局面とは、
「ランダムに手を打ちまくって、勝負が決まった時に勝ってるのが多いやつ」
という考え方なのである。もちろん、説明は極端なくらいに簡単にしたものだが、このランダムなところが、モンテカルロの名を持つ由来である。
モンテカルロ法というものがあってそこから命名されている。
元来物理の世界で、細かいものが沢山ある中から一部をピックアップして割合をざっくりつかむという用途で使われているものです。
正直関係ない気がしてきたし、なんか説明がめんどいので需要があれば説明を後日書く。
この手法をイメージとしてつかむには、くじを考えるといい(適切な画像があれば、円周率を求めるやつが一番わかりやすいんだが、そちらはwikiにあるので私の説明で分からなかったらそちらを参照してほしい)
5000兆本のくじがあると考えてくれ。
当たりが何本入ってるかな~?
この時、本数をざっくり考えるなら、とりあえずたくさん引いてみればいい。
1000本引いて500本当たりだったとしたら、大体この中に当たりは2500兆本入ってるんじゃないかという予想ができる。勿論、正確ではないけれど、十分満足な予測だと考えられると思う。
この方法、試行回数を増やせば、よりその予想は正確になる。
「有利な局面と不利な局面があったら、有利な局面からの方が沢山勝ちがある。」
と考える。だから、「ランダムに手を指して、終局したときに勝ちが多い局面は、『有利!』」としてしまう。そして、その『有利』な局面を目指すように指す。これがモンテカルロ系の探索だ。
※仮定であるから、これが合っていようが間違っていようがどちらでもいいのだ。この手法が上手くいかなかったら手法を切り替えるか、改良する。こういう考え方がいい。この考え方でソフトを作っていると何が起こる?そう。「どうして上手くいっているのか、分からない」上手くいくと思って入れたものが、結局上手くいくとは限らない。AIはブラックボックスなんだという話の理由の一つがここにある。
ちなみに、木というのは樹形図みたいなものだと思ってほしい。局面が進むにつれて枝が分かれていく。この木を、「ゲーム木」という。
最後に
モンテカルロが上手くいくかどうかは分からないし、個人的には将棋では上手くいかないように思っている。でも、頑張って欲しい。今まで数多の人が挑戦して、現在強豪の中にはモンテカルロは残っていない。逆説的に、ブレイクスルーは常に今までの手法じゃないところから現れる。実際、囲碁のモンテカルロも、最初は弱かった。でも、改良することで劇的に強くなった。
やっぱり、今いる強豪と根本から違うと期待しちゃうわけです。
私は、全てのコンピュータ将棋開発者を応援しておりますよ