モンテカルロ木探索で一人不完全情報ゲーム「計算」を賢くする[1]

最近、将棋や囲碁のプログラムが非常に強くなった。将棋は機械学習を取り入れるようになったのだが、囲碁は「モンテカルロ木探索」という方法を取り入れて、一気にアマチュア高段者レベルに達した。

難しいと言われる囲碁でこれだけ成果を出した「モンテカルロ木探索」を、別の分野で試し、有効性を検証してみることにした。

ゲームをプログラムにプレイさせるとき、一般にはゲーム木なるものを作り、それぞれの手を選んだ時の勝率を計算し、より勝率の高い手を選ぶことで実現するのが一般的だ。木を完全に展開できる場合、つまり全ての可能性を読み切れる場合はそれでお終いなのだが、ほとんどのゲームは読み切れるほど木が小さくないので、適当なところで盤面を評価し、各葉ノード値とし、それを元に次の一手を選ぶ。このとき、盤面評価の性能が強いか弱いかを決めることになる。

しかし、盤面評価は難しい。この難しい部分を、定石などに基づいてガチにプログラムを組むことが行われていたが、なかなか成果が出ないのが現実である。そこで、当然考えられるのが、盤面評価が面倒なら、面倒なこと自体を放棄しよう。どうせ無駄だ、、、という考えがある。

面倒なプログラムを書くには、対象にしているゲーム（課題）を十分に研究しないといけないが、全部やめてしまうとどうなるか。でも、最後までプレイして、勝ったか負けたか、あるいは成功か失敗かくらい分かれば何とかなるかも知れないではないか。ということで、何の知識も持たない、ただルールを厳守するだけのどうしようもないプレイヤー・プログラムを用意し、これとモンテカルロ木探索を組み合わせて、十分強い、十分賢いプログラムができるかどうか検証してみる。

囲碁は、二人完全情報ゲームである。類似のものとして、オセロがあり、これは本ブロクでも紹介されているので別のことを考える。まず、二人でないゲームとして、一人と多人数という選択肢があるが、一人の方がプログラムが楽そうなので、一人ゲーム、一人遊びを選択する。完全情報ゲームはやめて、不完全情報ゲームを選ぶ。また、はっきり有限手数で終わるものを選ぶ。つまり、一人有限完全情報ゲームでモンテカルロ木探索の有効性を検証する。

さて、利用するひとり遊びは、トランプのひとり遊びの中から「計算」を選んだ。このひとり遊び（ソリティア）は、数学者＆コンピュータ研究者として著名な野崎昭弘氏の「とらんぶ」ダイヤモンド社、初版昭和４９年により知った。

一度絶版になったが、今は朝日選書として復刊しているようだ。

　　　

計算のルール

準備：

ジョーカーを除いた５２枚のカードを使用する。ただし、スーツ（種類）は無視する。

A,2,3,4の４枚を取り出し、並べる。これらが台札である。

４つの台札の下に、４つの屑札をおける場所を確保しておく。

のこり４８枚のカードは、しっかり切って、重ねて手札とする。

各台札の上には、それぞれ最初の台札(1,2,3,4)だけの間隔を開けてカードを重ねることができる。

つまり、次のようになる。Kの次には、A,2,…と繋がると考える。

なお、全ての数字を１文字表示にしたいので、１０はTで示している。

プレイ:

手札を１枚めくる。

表になった手札は、台札に重ねるか、屑札に重ねることができる。台札に重ねるときは、指定された間隔を保たなければならないが、屑札に重ねるときには、どの屑札でも構わない。

屑札の一番上のカードは、台札にいつでも重ねることができる。もちろ、、指定された間隔を保たないといけないが。

手札を台札か屑札の上に移動し終えると、手札をめくることができる。

以上が、可能なカードの動かし方の全てだ。

　　　　　　　　　※上図の手札は最初（一番上）の５だけが見えていて、それ以降は本当は見えていない。

目的：

この遊びは、以上のルールに従ってカードを動かし、全てのカードを台札に重ねることができたら成功である。

そのとき、どの台札も、一番上はKになる。

例：

次に、「計算」の最初の方のカードの移動を図で示す。ほとんど台札に重ねられる数字が手札から出てこなかったため、延々と屑札の上に積み重ねている。

最初の方だけ、実際にどのようにプレイが進んでいくかを示す。図についての説明は面倒なので省略するが、分かると思う。

今回の説明はここまでにしておく。

まず、この一人遊びを実際にプレイしてみて、自分の頭でどのくらいの成功率になるか確認していただきたい。

もし１割以上の成功率ならば、相当優秀である。

モンテカルロ木探索では、戦略は無視なのだが、次回は「計算」の戦略を紹介する。その戦略を使うと、人手でプレイしても一気に成功率が上昇する。