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

　前回に引き続き、モンテカルロ将棋の話である。最近巷ではどうぶつしょうぎが話題になっており、その検索語でここに来る人もいるかもしれないので先に断っておくが、本日の日記はどうぶつしょうぎをコンピュータで解析し尽くそうという話ではない。コンピュータ囲碁で使われているモンテカルロ法という手法をコンピュータ将棋にも使ってみたいと考え、その第一歩としてミニチュア将棋の一種であるどうぶつしょうぎを使っているにすぎない。以下に書く手法よりも、古くから将棋（やチェスなどのボードゲーム）で使われているmin-max法の方がずっと強くて動作も速い。本日の日記は実験的なことをしてみたというエントリだと思ってほしい。どうぶつしょうぎのルールはここに明示されている。それから私はコンピュータ将棋は専門外であり、あくまで音声工学が専門である。なお、従来から本将棋でのモンテカルロ法の試みもなされており、実戦投入されている。

　さて、どうして将棋にモンテカルロ法を使いたくなったのかというところから書こう。それはずばり、先日の人間対コンピュータの対局を見て、終局図からの逆算が必要だと感じたからである。特に、馬を作られたのを見て、末端ノードが詰みではなく評価関数の値であることの限界を感じた。かといって、終局図の勝敗から手の善し悪しを評価するモンテカルロ法が強いと主張したり実証したりしたいわけでもない。モンテカルロ法を突き詰めていくと、どこかでmin-max法に使える知見が出てくるのではないかというくらいの気持ちで、モンテカルロどうぶつしょうぎを試している。

　本題に入る。前回のエントリでは、プレイアウトの結果から反復的にプレイアウトの精度を上げるということを書いた。その後ブックマークのコメントやトラックバックで指摘していただいたが、コンピュータ囲碁ではすでに広く使われている手法のようである。すでに使われていようがいまいが、改良するつもりだったので、さらに改良をする（速度が遅くなったので改良になっているかどうかは分からないが）。前回のエントリでどういったことを試したのかを忘れてしまったり読んでいなかったりする人は、前回のエントリをざっと眺めてほしい。

　前回の特徴量は次のようなものだった。「移動させる駒の種類」「移動先にある駒の種類（または空白）」「移動元の座標」「移動先の座標」「移動先の利きの種類」「何手目の局面か」。これらは、いかにモンテカルロ法で細長い読みを実現させるかということを念頭に置いて作った特徴量である。この特徴量の中で「何手目の局面か」だけ異質である。ゲーム木を思い浮かべてほしい。mim-max法というのはこのゲーム木をノードや辺をばらばらにせずに丁寧に辿っていく手法である。一方、原始モンテカルロ法は前後の脈絡を無視して辺をばらばらにして集めてきていると見なせる。そして、特徴量ごとに手の勝率を計算するのは、ばらばらに集めてきた辺をカテゴリ分類することに相当する。このとき、「何手目の局面か」という特徴量があると、辺をばらばらにするときに、ゲーム木上の深さの情報だけは保持していることになる。つまり、親子の辺は混ざり合わず、兄弟の辺だけ混ざることになる。ゲーム木上の辺の関係をその特徴量だけで保持しているという意味で、「何手目の局面か」という特徴量は異質なのである。

　この「何手目の局面か」という特徴量は細長く読むという意味では有効であるが、少なくとも短所が二つある。一つはコンピュータのメモリが有限であるために、特徴量を保持しておける深さも有限になってしまうということである。このため、保持しておける深さを超えると、手の選び方が原始モンテカルロと同じ振る舞いになってしまう。もう一つは、特徴空間がスパース（まばら）になってしまうということである。プレイアウト数が足りないと、未知の特徴空間ばかりになってしまう。

　これを克服するために、「何手目の局面か」という特徴量を含まず、且つ、特徴空間が狭い、もう一つの勝率テーブルを用意することにした。新しい勝率テーブルは「移動させる駒の種類」「移動先にある駒の種類」「移動元の利きの種類」「移動先の利きの種類」という４種類の特徴量で構成した。特徴空間の広さは６００要素である。手数に依存する古い勝率テーブルと、手数に依存しないこの新しい勝率テーブルを線形結合して、あらためてその手の勝率とし、その勝率に従って手を偏らせることにした。なお、線形結合するときには、深さが浅いときには手数に依存する勝率テーブルを優先させ、深くなるにつれ手数に依存しない勝率テーブルの影響力を強めた。

　ところで上記の改良というのは、細長く読むための改良ではない。細長く読もうとした弊害をフォローするための改良である。以降では、さらに細長く読むための手法について語る。

　ここまで「勝率によって手を偏らせる」という曖昧な書き方をしてきた。具体的にはどういうことをしていたかといえば、勝率（０から１）から0.4くらいを引き算して、それを手を選ぶ確率に比例させていた。たとえば、勝率0.5、勝率0.6、勝率0.4の三つの合法手があったとする。そうしたら、それぞれの手を１：２：０の割合で選ぶようにしていた（実際には０にはしなかったが）。しかしながら、これでは勝率0.5の手が必要以上に選ばれやすく、その結果、より深いノードで勝率0.5の手から来た局面と勝率0.6の手から来た局面が衝突する。極端にいえば、モンテカルロ法の趣旨とは反するが、一つの局面からは一つの手しか選ばないようにしたかったので、「１：２：０」の割合をさらに次のように書き換えることにした。まず、最大の割合をmaxScoreとする。そして任意の係数をalphaとする。そして、それぞれのスコアをこう書き換える。

(更新したスコア) = ((更新前のスコア) - alpha * maxScore) / (1 - alpha)

たとえば、alpha=0.2とすると、「１：２：０」は「0.75:2:(-0.5)」となる。最大のスコアが変化することなく、ほかのスコアが下がる。この割合で手を選ぶことにした。なお、alphaはプレイアウトを重ねるごとに大きくなるようにした。つまり、初期のプレイアウトではあまり手が偏らないようにしている。また、手数に依存する勝率テーブルのみにこの式を適用し、手数に依存しない勝率テーブルには手を加えていない。

　この二つの改良で処理は重くなったものの、同一プレイアウト数では強くなった。前回と同様にプレイアウト数ごとに原始モンテカルロと１００局の対局をしたときの勝利数を示す。参考のために、前回の勝利数も併記する。

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

PO数	100	1000	10000	100000	1000000
先手勝数（今回）	92	89	93	94	99
先手勝数（前回）	93	93	87	86	73

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

PO数	100	1000	10000	100000	1000000
後手勝数（今回）	91	95	89	95	96
後手勝数（前回）	84	82	87	68	100

　この一ヶ月間、ここまで手を動かしてみた感じでは、やはりmin-maxの方がずっと強い。また、手を加えれば加えるほど、モンテカルロ法がmin-max法に近づいていく。結局はmin-max法をじわじわと改良していった方が強いのだろうとは思うが、そんなことは気にせずに、今後もモンテカルロ将棋を断続的に続けていくつもりである。次は、どうぶつしょうぎではなく、５五将棋か本将棋にするつもりである。また何か致命的な問題点が浮き彫りになってくることと思う。

　さて、いつものようにソースコードをSkyDriveに置いておく。ただし、コンパイルをしても動作するようにはしていない。前回の日記の直後に公式にルールが発表されたが、やはり、動いてしまうものを勝手に配布するのははばかられる。

　最後に、棋譜の一例を載せる。

先手、後手ともに1000000プレイアウト
先手：今回の改良法
後手：原始モンテカルロ

持:
  ３  ２  １
+---+---+---+
|v麒|v獅|v象|一
+---+---+---+
| 　|vひ| 　|二
+---+---+---+
| 　| ひ| 　|三
+---+---+---+
| 象| 獅| 麒|四
+---+---+---+
持:
初期配置である

持:
  ３  ２  １
+---+---+---+
|v麒|v獅|v象|一
+---+---+---+
| 　|vひ| 　|二
+---+---+---+
| 　| ひ| 麒|三
+---+---+---+
| 象| 獅| 　|四
+---+---+---+
持:
先手のきりんが上がる

持: ひ
  ３  ２  １
+---+---+---+
|v麒|v獅|v象|一
+---+---+---+
| 　| 　| 　|二
+---+---+---+
| 　|vひ| 麒|三
+---+---+---+
| 象| 獅| 　|四
+---+---+---+
持:
後手、一手損ひよこ換わり

持: ひ
  ３  ２  １
+---+---+---+
|v麒|v獅|v象|一
+---+---+---+
| 　| 　| 　|二
+---+---+---+
| 　| 象| 麒|三
+---+---+---+
| 　| 獅| 　|四
+---+---+---+
持: ひ
先手のぞうがひよこを捕食

持: ひ
  ３  ２  １
+---+---+---+
|v麒|v獅| 　|一
+---+---+---+
| 　|v象| 　|二
+---+---+---+
| 　| 象| 麒|三
+---+---+---+
| 　| 獅| 　|四
+---+---+---+
持: ひ
後手のぞうが上がる

持: ひ
  ３  ２  １
+---+---+---+
|v麒|v獅| 　|一
+---+---+---+
| 　|v象| 象|二
+---+---+---+
| 　| 　| 麒|三
+---+---+---+
| 　| 獅| 　|四
+---+---+---+
持: ひ
きりんのひもをつけたまま先手のぞうが王手

持: ひ
  ３  ２  １
+---+---+---+
|v麒| 　|v獅|一
+---+---+---+
| 　|v象| 象|二
+---+---+---+
| 　| 　| 麒|三
+---+---+---+
| 　| 獅| 　|四
+---+---+---+
持: ひ
後手のらいおんが逃げる

持: ひ
  ３  ２  １
+---+---+---+
|v麒| 　|v獅|一
+---+---+---+
| 　|v象| 象|二
+---+---+---+
| 　| 獅| 麒|三
+---+---+---+
| 　| 　| 　|四
+---+---+---+
持: ひ
先手のらいおんが上がる
どうぶつしょうぎでは
「二段目のらいおんに負けなし」
といわれているとかいないとか

持:
  ３  ２  １
+---+---+---+
|v麒|vひ|v獅|一
+---+---+---+
| 　|v象| 象|二
+---+---+---+
| 　| 獅| 麒|三
+---+---+---+
| 　| 　| 　|四
+---+---+---+
持: ひ
後手、ひよこ打ち
これは悪手
これを的確にとがめれば先手の勝ち

持:
  ３  ２  １
+---+---+---+
|v麒|vひ|v獅|一
+---+---+---+
| 　|v象| 象|二
+---+---+---+
| 　| 獅| 　|三
+---+---+---+
| 　| 　| 麒|四
+---+---+---+
持: ひ
先手のきりんが下がる
「渋いですね」
と私が画面の前で独りで呟く

持:
  ３  ２  １
+---+---+---+
| 　|vひ|v獅|一
+---+---+---+
|v麒|v象| 象|二
+---+---+---+
| 　| 獅| 　|三
+---+---+---+
| 　| 　| 麒|四
+---+---+---+
持: ひ
後手のきりんがただ取りされる位置に上がる
ここでは、ぞうときりんのどちらを
ただ取りされるか、という二者択一だった
この局面で、先手必勝

持:
  ３  ２  １
+---+---+---+
| 　|vひ|v獅|一
+---+---+---+
| 獅|v象| 象|二
+---+---+---+
| 　| 　| 　|三
+---+---+---+
| 　| 　| 麒|四
+---+---+---+
持: ひ 麒
先手のらいおんがきりんを捕食
１二のぞうを見捨てたことになる
先手のらいおんが入らいおん目前のため
後手のぞうは動けない

持: 象
  ３  ２  １
+---+---+---+
| 　|vひ| 　|一
+---+---+---+
| 獅|v象|v獅|二
+---+---+---+
| 　| 　| 　|三
+---+---+---+
| 　| 　| 麒|四
+---+---+---+
持: ひ 麒
後手のらいおんがぞうを捕食

持: 象
  ３  ２  １
+---+---+---+
| 　|vひ| 　|一
+---+---+---+
| 獅|v象|v獅|二
+---+---+---+
| 　| 　| ひ|三
+---+---+---+
| 　| 　| 麒|四
+---+---+---+
持: 麒
ひよこで王手

持: 象
  ３  ２  １
+---+---+---+
| 　|vひ|v獅|一
+---+---+---+
| 獅|v象| 　|二
+---+---+---+
| 　| 　| ひ|三
+---+---+---+
| 　| 　| 麒|四
+---+---+---+
持: 麒
らいおんが逃げる

持: 象
  ３  ２  １
+---+---+---+
| 　|vひ|v獅|一
+---+---+---+
| 獅|v象| 麒|二
+---+---+---+
| 　| 　| ひ|三
+---+---+---+
| 　| 　| 麒|四
+---+---+---+
持:
先手１二きりんまで
先手の勝ち