jyanjayakaの日記

はやめのリリース、しょっちゅうリリース

モンテカルロ木探索について

手をランダムに選択させて1ゲームをプレイさせる。(もちろんルール上許される手に限る。)

囲碁と将棋が違うのは、このようにプレイさせると囲碁はゲームがすぐに終わるが、将棋の場合はそうはいかないというところ。囲碁は単純に盤上に石が増えていって、それ以上置けなくなる。一方将棋はルール上可能な手を繰り返していつまでもゲームを続けることができる。

ランダムに手を選ばせるだけなら、1ゲームはすぐに終わる。互いに100手打つなら全部で200手がプレイされるが、ランダムに手を選ぶだけなら1秒以下で終わるだろう。

こうしてたくさんのゲーム数をこなさせる。こうすると、数あるゲームの中で、特定のある手を選択した時に白が負けやすいといったことが起こりうる。そうすると、どうもその手は白にとって勝率が低い「悪い手」であるということが言えそうだ。

こうして、各局面でランダムにプレイさせて、その中で最も勝率の高かった手を選択するという戦略が立てられる。

この戦略は強いだろうか?

まず原理的な問題として、ランダムなプレイでちゃんとゲームが終了することが必要だ。人間同士の場合は、ゲームが終了するように手を選択するのが普通だが、それを完全にランダムに選ぶとなるとゲームがちゃんと終わるかどうか保証されない。

実際、囲碁は終わるが将棋は終わらない。

なのでこの戦略はそもそも囲碁のようにランダムな手を選択しても終わるゲームにだけ有効。ここではそれを前提として話を進めよう。

まず考えられるのは、ランダムで選ぶのは適当過ぎるんじゃないか? ということ。これは確かにそうで、勝率が高いとか低いとかいうのはお互いがランダムにプレイした結果であって、もし人間が相手なら(ランダムな方法では「運悪く」選ばれなかった)上手い手があって簡単に負けるかもしれない。

「運が悪い」というのはプレイ数を十分多く取れば防げる問題のような気がする。ただこの「十分多く」というのが問題で、これはそもそも論として、囲碁のようなゲームはルール上許される局面の数が非常に多いから解析が難しいのだった。そのように十分大きなプレイ数を確保できるのであれば、そもそもAIを工夫する必要性があまりない。

 そこでいかに効率よく手を絞ってゆくかといういつもの問題に行き着く。