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

　日記をさかのぼると、「モンテカルロどうぶつしょうぎの試み２」は五月の記事のようである。今回の記事も本当は９月にアップロードしようと思っていて、９月には実験が終わっていたのだが、実験が終わった途端にいろいろと忙しくなり、１０月になってしまった。

　この記事のシリーズは要するに、コンピュータ囲碁などのほかのボードゲームで活躍している「モンテカルロ法」を将棋にも応用してみようというものである。そして、最初から９×９の将棋に適用するのではなく、３×４の「どうぶつしょうぎ」から始めてみている。まだ決して強くはないが、なんとなく続けてみている。

　さて、モンテカルロ法を将棋に適用するときの最も原始的な方法からおさらいしよう。まず、「現在の局面」が与えられている。そうしたら、とにかく終局するまでランダムに駒を動かす。終局したら、その「現在の局面」からの最初の手に勝敗を記録しておく。そのランダムな対局を何度も重ねて、最も勝率のよかった最初の手を次の一手として選ぶ。なお、このランダムな対局のことをプレイアウトと呼ぶ。

　この原始的な方法を改良するための（私が知っている）代表的なアプローチは三つである。一つは、プレイアウトの精度を高めることである。簡単な例を挙げれば、駒をとる手の指す確率を高くし、玉が敵陣に近づいていく手を指す確率を低くしたりと、そういうことである。そうすると、プレイアウトから得られる勝ち負けの信頼度が高まる。もう一つのアプローチは、ゲーム木探索を導入することである。プレイアウトを重ねれば、指し手の勝率が分かる。その勝率のよい手に関して、さらに一段階深いところからモンテカルロ法を適用するのである。最後の一つは、ある計算式に従って、勝率の高い「最初の手」から優先的にプレイアウトを始める手法である。この三つのほかのアプローチとして、囲碁では、プレイアウト中に打った全ての手を「最初の手」とみなすという方法も採られているらしい。これは、プレイアウト数を節約するのに有効である。ほかにもいろいろと研究されているはずだが、私が下敷きにしているのはこれくらいである。

　私が過去の日記で実験してきたのは、プレイアウトの精度を高めるためのものだった。ただし、手作業や学習であらかじめ高い確率で指す手の種類や低い確率で指す手の種類を決めておくのではなく、プレイアウトを重ねてその結果から指す手の確率をその場で計算することにした。あらかじめ学習しておくよりも、局面に柔軟に対応することができるのではないかと考えたためである。

　五月の日記の時点までにやっていたことというのは、次のようなものだった。まず、プレイアウトが始まる前に、勝率テーブルを確保しておく。テーブルの要素は「移動元の座標」「移動先の座標」「移動元の駒」「移動先の駒（または空白）」「移動先の利きの種類」「そのプレイアウト中で何手目か」というそれぞれの特徴量の組み合わせの数だけある。そして、プレイアウトを一回終えるごとに、その勝率テーブルの勝率を更新していくのである。プレイアウトは、そうやって学習した勝率テーブルの勝率の数値をもとに、指す手を偏らせることにした。これにより、事前の学習なしにプレイアウトの精度を上げることができた。

　さらに、それでは勝率テーブルが広すぎて空白の要素や学習不足の要素が多くなってしまうので、狭い勝率テーブルも別に用意することにした。こちらは、「移動元の利き」「移動先の利き」「移動元の駒の種類」「移動先の駒の種類（または空白）」という特徴量を持つ。これとさきほどの広い勝率テーブルを線形結合させることで、学習不足の問題を補った。これは、自然言語処理でいうスムージングの概念に近いと思う（音声信号処理の人や画像信号処理の人が思い浮かべるスムージングとはかけ離れているのだが）。

　ここまでが、五月までにおこなった主な作業である。実はその後、５五将棋にこのアルゴリズムを移植してみたのだが、まるで思うようには動作してくれなかった。５五将棋の詳しい説明はしないが、初手で飛車が歩をとってしまうという最悪の手を選んでしまうのである。読み筋を表示させてみると、どうやらいわゆる「勝手読み」をしているようだということが分かった。相手の応手を気にせずに好きな手のみを読むというものである。言い換えれば、プレイアウト中の局面の把握ができていないということである。

　再びどうぶつしょうぎに戻って考えてみて、勝率テーブルをもう一つ用意するしかないだろうと思った。五月のときには、勝率テーブルが広すぎるからということで、もう一つ狭い勝率テーブルを用意したのだが、今度用意するのはさらに広い勝率テーブルである。すなわち、その局面にのみ依存する勝率テーブルである。これではさらに学習が足りなくなりそうなものであるが、それは狭い勝率テーブルが補ってくれるのできっと大丈夫である。また、この「局面にのみ依存する勝率テーブル」がおそらく最も広い勝率テーブルである。

　実際に実装してみたところ、どうぶつしょうぎでは格段に強くなった。五月の時点ではmin-max法（将棋やチェスで最も有力な手法・コンピュータボードゲームの基礎的手法）にはまるで敵わなかったのであるが、駒割のみの５手読みのどうぶつしょうぎといい勝負をしてくれるようになった。

　ここで少々、私なりのモンテカルロコンピュータゲームに対する考え方を書いておく。まず、ゲームの勝ち負けを最重視するのであれば、理想論ではあるが、途中まで読んで評価関数を使うよりは、終局のかたちを考慮すべきだと思う。そのためにはいかに精度よく細長く読んでいくかが生命線になるのだろうと思う。ただし、「精度よく細長く」が妥当な考え方であるかどうかは分からないし、妥当であるかどうかは大した問題ではない。重要なのは、私が「精度よく細長いモンテカルロ」を目指しているということである。方向性を決めておけば正解か不正解にたどり着くことができるが、方向性がないとどちらにもたどり着くことができない。

　話を戻す。局面にのみ依存する勝率テーブルを導入したことで、これまでモンテカルロっぽかったものが、急にmin-maxに近くなってきた。とりわけ、実現確率探索に近くなったように思う。「評価関数」「実現確率」「探索」の三つが継ぎ目なしに絡み合っている実現確率探索である。継ぎ目なしに絡み合っているからいいとか悪いとかいう問題ではなく、そういう印象のものになったということだ。

　なお、上記三つの勝率テーブルのほかに、もう一つ勝率テーブルを使用している。「移動元の座標」「移動先の座標」「移動元の駒」「移動先の駒（または空白）」「移動元の利き」「移動先の利き」を特徴量とするテーブルである。手数に依存していないところがポイントである。このテーブルの導入によって強くなったのか弱くなったのかは今のところよく分かっていない。

　それから、これは仕方なく導入したことなのだが、最初に四つの勝率テーブルの線形結合で、かつ、緩やかな指し手の偏らせ方でプレイアウトを50000局させたのちに、局面依存の勝率テーブルのみで（ただし、補間はする）ベストの指し手のみを選んで400000局のプレイアウトをした。局面依存の勝率テーブルのみを用いたのは、「細長く」ということをさらに突き詰めて実装したかったからである。ただし、安直すぎる実装である。

　さて、現段階での強さを書いておく。ｎ手読みのmin-maxに何勝何敗したかという数値である。千日手の実装をしていないので、手数が八十手を超えた場合には引き分けとしている。プレイアウト数は合計で450000局である。後手を持ったときにはとられたひよこをらいおんでとり返す傾向があり、結果としてぞうの進出が遅れて負けるようである。また、min-maxには静止探索を実装していないので、奇数手読みのときには駒損しやすくなる。

表：min-maxのｎ手読みに対するモンテカルロの勝敗（勝-敗）

min-max読みの深さ	4	5	6	7
モンテカルロ先手	12-10	16-9	12-11	6-17
モンテカルロ後手	6-16	13-11	5-19	3-19

　これからやろうと考えているのは、現在雑に実装しているところを丁寧に磨き上げることと、「精度よく細長い」の「精度よく」の部分の「精度」の方向性を考えることである。

　さて、今回もSkyDriveにソースコードをアップロードしておく。関係各所（LPSA・幻冬舎エデュケーション・北尾まどか氏など）に怒られない程度に自由に使用してよいです。ただし、（いつものように）そのままｇｃｃでコンパイルしても動かないように、合法手生成などのルールに関係する部分をとり除いておいた。

　将棋や将棋以外のコンピュータボードゲームの方の見解や、モンテカルロ法・機械学習の方の見解をブックマークのコメントやトラックバックでいただければ幸いである。

以下おまけ（実戦譜）