モンテカルロどうぶつしょうぎの試み。

　本日の日記は、専門外のコンピュータ将棋・コンピュータ囲碁の話である。先日コンピュータ将棋のデモンストレーションを見て、やっぱりモンテカルロ法を将棋にも応用したいなと思った。ただし、将棋の場合は細長い読みをしなければならないためモンテカルロ法が適用しづらいらしい。でもなんとかして将棋に適したモンテカルロ法を作りたいと思ったので作ってみた。細長く読めるモンテカルロ法が目指すところである。

　いきなり９×９の本将棋で実験をする自信がなかったので、まずは３×４の「どうぶつしょうぎ」で実験をすることにした。どうぶつしょうぎの利点はルールに反則がないので実装が簡単であることと、それなりに奥が深いことと、本将棋と同じく細長い読みが要求されることである。どうぶつしょうぎはＬＰＳＡのオンラインショップから買うことができるが、私は駒込のサロンに直接赴いて買いに行った。１２００円である。なお、ルールも含めて商品の一部であると解釈したので、ここではルールを明示することはしない。それから、ルールの作者は北尾まどか女流初段であり、絵を描いたのは藤田麻衣子女流１級(id:pie_co)であるらしい。

　まずは、原始モンテカルロ将棋を作った。プレイアウトを数回おこなって、相手の玉（ライオン）をとることができたら勝ちである（自殺手も生成する）。その局面からの初手に対して勝率を計算し、最も勝率の高い初手を実際に指す。どうぶつしょうぎは探索空間が狭いので、1000回のプレイアウトで、全くのランダム指しに対して、100局中100勝することができた。ただし、棋譜を見てみると詰ましているわけではなく相手の自殺手に対して的確に対応しているだけであるということが分かる。

　さて、この原始モンテカルロ将棋をどう発展させれば、細長く読むことができるのか。それはやはりプレイアウトの精度を高めることが近道だろう。でも、プレイアウトの精度を高める方法を手作業や教師あり学習で教えることは（有効ではあっても）面白くなさそうなのでしたくない。

　そこで、ランダムなプレイアウトによってプレイアウトの精度を高めることにした。最初に試したのはこういう手法である。プレイアウトのときに初手から最終手まで全ての「移動元の座標」「移動先の座標」「移動した駒の種類」「とった駒の種類（または空きマス）」の組み合わせに対して勝率を計算し、その勝率に従って次からのプレイアウトを偏らせるのである。プレイアウトをすればするほどどんどんプレイアウトの指し手は偏っていく。これで原始モンテカルロに対してはかなり勝ち越せるようになった。

　その後、特徴量として「移動先の利きの種類」「手数」も加えた。手数（何手目に指した手か）という特徴量を入れてしまうと通常のゲーム木探索に近くなってしまうので抵抗があったが、ぐんと強くなるのも事実である。

　あとは細かい改良として、短手数でプレイアウトが終わったときの更新の影響を強めたり、前の局面で計算した勝率表を次の局面でも使えるようにしたりした。

　人間（私）が対戦してみた感触では、まだ悪手を指してしまうものの、意味のない捨て駒（原始モンテカルロ将棋に多いといわれている）は劇的に少なくなった。また、三手詰めくらいならば100000プレイアウトくらいで読んでくれる（詰んだあとにこちらが自殺手を指してコンピュータがそれをとるというところまで読む必要があるので、五手読んでいる）。なお、試してはいないが、今のところやはりmin-max法には敵いそうにない。

　原始モンテカルロとの対戦勝率は以下のとおりである。各プレイアウト数に対して100局指している。なお、プレイアウト数が増えてくると、探索空間が狭いので、終局のパターン数が非常に少なくなってしまい、（実感できる）強さと勝率の間に隔たりが生まれる。

表１．先手改良法・後手原始モンテカルロ。１００局中の先手勝利回数。PO数はプレイアウト数。

PO数	100	1000	10000	100000	1000000
先手勝数	93	93	87	86	73

表２．後手改良法・先手原始モンテカルロ。１００局中の後手勝利回数。PO数はプレイアウト数。

PO数	100	1000	10000	100000	1000000
後手勝数	84	82	87	68	100

　ところでこの手法というのは要するにプレイアウト時の特徴量をプレイアウトで学習するようにしただけである。これによって、その局面に特化した特徴量にすることを狙っている。もちろん、事前に用意しておいた特徴量を使ってもいいと思うので、ある特徴量に対して「事前に用意しておく」と「その場で学習する」の二つの選択肢が考えられることになる。

　また、モンテカルロ法そのものの理論はどうやらかなり奥が深そうなので、モンテカルロ法の結果をモンテカルロ法に反復的に使用するというアイディアはきっと相当古くからあることと思う。それが囲碁や将棋に応用されているかどうかは知らない。強化学習をコンピュータ将棋に応用している人や、モンテカルロ法をコンピュータ将棋に応用している人などに聞いてみたいところである。

　この手法の有効性はまだ未知数であるが、大きな問題点が少なくとも一つ見つかっている。メモリ使用量が大きいということである。もしもどうぶつしょうぎでなかったら、プログラムを走らせることすらできなかったところである。どうぶつしょうぎに感謝。なお、私はデータ構造とかそういうのを作るのが苦手なので、自力で本将棋に適用することはできそうにない。

　さて、CのソースコードをいつものようにSkyDriveに置いておく。ただし、このコードをコンパイルしても指せるようにはしていない。どうぶつしょうぎのルールに関する部分を意図的に削ったからである。ルールが知りたい方は、どうぶつしょうぎを買ってください。

　ところで、その手法はすでにあるとかそういうことがあったら、トラックバックで知らせてください。私自身は記事を修正しませんが、読む人がトラックバックをたどっていくことと思います。