原始的なモンテカルロ探索を示したが、これは成功率が１％にも満たないものである。

もっと高い成功率を求めて、囲碁プログラミングで使われだした「モンテカルロ木探索」を、「計算」でも使えないか試してみよう。

ゲームやパズルでは、状況を分析するために、現在の盤面をルート（根）とする木を作るのが一般的である。

３手先までの木を作るとこんな感じになる。

これは標準的な木で、一番下の葉のところでプレイアウトして、それぞれの成功確率を計算し、上に遡りながら一番良い手を選ぶというやり方があるが、ここではそれは説明しない。

枝の伸ばしについて、どの場合も同じ割合で伸ばしているが、これで良いのだろうか？

囲碁や将棋を考えてみれば分かるが、これはと思う枝はどんどん深く読んでいくが、これは論外だなというのはさっさと切り捨ててしまう。つまり、こんな感じの木ではなく、特定のところが深く探求され、かなり「いびつな木」が出来上がっている筈だ。それをこれから説明していこうと思う。

モンテカルロ木検索がどのようなアルゴリズムであるかについては、色々なところに説明があるので、ここに説明を長々と書くよりも、良さそうな情報源を紹介する方が役に立つし、こちらは楽なので、紹介するに留める。

モンテカルロ木関連情報

『コンピュータ囲碁におけるモンテカルロ法〜理論編』美添一樹(pdf)

とても丁寧な説明なので、十分理解できると思う。ただ、囲碁に偏った説明が多くなっているが、元々囲碁で使われだしたので、当然囲碁を使って説明が進む。とくに囲碁を理解していなくても大丈夫なのだが、囲碁の説明部分を十分に理解したい場合は、この際囲碁をマスターしてしまおう。

理論的な基礎は、このPDFだけで十分ではないかと思う。というか、それくらいしか読まずに「計算」に適用してみようという大胆なことをやっているのが実情である。

これで書ける「囲碁講習会」全４回＠電気通信大学

こちらは、２０１５年夏に電気通信大学で行われた囲碁プログラミングの講習会で、
実践編2 『UCTアルゴリズムで打つ』の中で説明されている。

実際に強いプログラムを作っている人が、囲碁プログラミング初心者向けに、多数のソースコードを用意し、実際の動きを体験させる講習会で、ビデオ、資料も充実しているので、とても参考になった。

ビデオはとても長い。１本約３時間であるが、十分に見る価値がある。

JavaScript でオセロを実装する(モンテカルロ木探索AI編)

こちらは、本ブログのもので、囲碁ではなくオセロで試みた例になっている。

「囲碁」と「計算」での相違点

モンテカルロ木探索を使うのだが、ほとんどの説明は囲碁の場合であるが、計算にそのまま適用できない部分がある。
まず、囲碁は、「二人完全情報ゲーム」であり、計算は「一人不完全情報ゲーム」である。 これから、２つの相違点があることが分かる。

二人 vs 一人

二人での対戦型では、プレイヤーが替わる度に盤面評価が逆になる。 自分に良い手は相手にとっては不都合であり、 相手の良い手は自分にとって不都合である。 つまり、一手打つ度に、評価を反転しなくてはならなくて、 そのために、Min-Max法とかαβ法とかいろいろ工夫されている。

しかし、今回は一人ゲームなので、常に自分の手番である。なので、可能な手から一番良い手を選ぶだけでよいので、この点ではとても簡単になる。

完全情報　vs　不完全情報

囲碁は、全ての情報が完全に見えているゲームである。偶然が入る余地はなくて、強い人と弱い人が対戦すると強い人が勝ってしまう。つまり、偶然勝てるなど、ないのである。

しかし、計算は手札を一枚ずつめくってプレイしていくが、どの数字が出てくるかはプレイヤが決めることができない。残りの手札の中のどれかが出てくるのだが、それ以上は決めようがなく、実際には乱数を使って残り手札の中からランダムに選んでおり、不完全情報ゲームになってしまう。

不完全情報ゲームになるのだが、カードをめくる部分なので、最大１〜１３通りしかありえない。この不完全な部分も木に組み込むことになる。プレイヤに選択権がある場合は最適な手を選べば良いだけだが、不完全な部分に対して予測を立てる必要があり、そこで枝分かれが増えるために木が横に広がってしまう。

というのが基本的な相違点である。

今日はここまでとし、次回からは、以上を考慮に入れて、ソースコードレベルで実装していく。