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

　本日の日記はコンピュータ将棋にモンテカルロ法を適用してみたという話である。ずいぶんと間が空いてしまったが、それだけ苦労したということである。第一回目の日記の内容から考えるとずいぶんと進歩した気がする。

　さて、コンピュータ囲碁の世界でモンテカルロ法（この日記では「モンテカルロ木探索」と区別せずにこう書く）が活躍しているが、コンピュータ将棋では依然としてminmax法の考え方で作られたソフトが活躍している。それがいいとか悪いとかという話とは無関係に、私はモンテカルロ法をコンピュータ将棋に適用しようとしている（この動機はあとで書く）。ただし、最初から８１マスの本将棋に適用するのは大変なので、まずは１２マスのどうぶつしょうぎで試している。実は前回はそこから２５マスの５五将棋に挑戦してみたのだが、どうにもうまくいかないので再び１２マスの将棋に戻った。なお、モンテカルロ法を将棋に適用しようと開発・研究している先輩たちはすでにたくさんおり、おそらく私のプログラムが最弱である。

　それから、この日記の末尾にプログラムを公開しているが、私のスタンスとしてはどうぶつしょうぎは木や紙で手で遊んでほしいと思っている（ボール紙で自作してもいいと思う）。もしパソコンで遊びたいという人は81-Dojoというサイトで対人戦ができるのでそこに行くことをお奨めする（どうぶつしょうぎのルールを作った女流棋士が秒読みの声を担当しているくらいなのでおそらく公認である）。

　ここから技術的な話になる。

　コンピュータ将棋を語る上でminmax法は避けて通れないので、遠回りではあるがそこから語る。まず、現在の局面があるとする。この局面に合法手(ルール上指せる手)がN個あったとすると次の局面はN通り存在することになる。図にすると次のようになる。

　この「次の局面」に対してさらに数通りの合法手が存在するのでその数だけ枝分かれし、さらに次の局面も同様に枝分かれする。図では仮に全ての枝分かれを2としているが、実際には様々な数の枝分かれがあり得る。こういう図を「木」という。

　ここで仮にこの深さ3の枝分かれで勝敗が決するとする。次の図のように勝敗が決するとしよう。この勝敗は一番上の「現在の局面」で手番を持っている方から見たものとした。

　この深さ3に至る一手は自分の手番なので、当然勝てるならば勝つ方を選ぶ。そうすると、深さ2の勝敗が決まる。

　深さ2に至る一手は相手の手番なので、当然負ける方（相手から見たら勝つ方）を選ぶ。こうして深さ1の勝敗が決まる。

　ここまで来るとどの次の一手を指せばいいのかも分かり、また「現在の局面」が勝ちなのか負けなのかも分かる。重要なことは、木の末端の勝敗が全て分かっていればその局面の勝ち負けと次に選ぶべき一手が分かるということである(厳密にいえば、末端の勝敗が「全て」分かっている必要はないのだがここではややこしいことは言わないことにする)。

　理想的には全ての末端の勝敗が分かれば必勝法(や必敗かどうか)が分かるのだが、コンピュータ将棋の場合は計算量の都合でそうはいかない。そこで、途中の深さまでで読みを打ち切ってそこでの局面の評価値(勝ちやすさみたいなもの。駒の損得とか囲いの堅さとか)を計算することになる。仮に次の図のように深さ3の評価値が分かったとする。

　先ほどは深さ2から深さ3に至る一手で勝ちがあれば勝ちとしたが、今度は評価値の大きい方の手を選ぶ(実際にはもっと多くの手から選ぶことになるがそのときには最大の手を選ぶ)。また深さ1から深さ2に至る一手では評価値の小さい方(最小)の手を選ぶ。すると、どの次の一手を選べばいいのかということが分かる。

　つまり、ある深さまでの評価値が信じるに足るものであれば、次に選ぶべき一手が分かる。この最大最小の計算方法が「minmax法」と呼ばれている。なお、全ての末端の評価値を計算する必要がないことが知られているが、そのあたりの説明はややこしいのでしない。この考え方に基づく実装法には本当に様々な実用的な工夫がたくさんあるのだが、ここでは説明する必要がないので説明しない。

　さて、ここからようやくモンテカルロ法である。ただし、どこまでが既知でどこからがオリジナルなのかは私自身も分かっていない。まず最も原始的なモンテカルロ法から語る。「現局面」と呼ばれるべきものが与えられたとして、そこから全くランダムに手を指していき、終局にたどり着かせる。図にするとこんなイメージになる。

　このどんどん手を指していって終局させることを「プレイアウト」という。そうして何回もプレイアウトを繰り返して結果的に最も勝率のよかった最初の一手を実際に指す手として選ぶ。

　この方法のいいところは、終局結果を指し手の評価の最も重要な要素として扱う点である。逆にいうとそこだけしか美点は思いつかず、欠点ばかりが目につくのであるが、やはり終局を考慮するのは重要なのではないかと思うのである。

　ところがこの方法だと問題が出る。minmax法のところで説明したような木だと、最初に右の指し手を選んでも左の指し手を選んでも勝率が5割になってしまうのである。

　同様に、仮に深さ3のところの勝率が与えられていたとして、最善手を指したときの勝率はminmax法と同じになるべきなのに、ランダムにプレイアウトさせるとそれとは違う勝率が出てきてしまう。

　この問題を考えるために、木から部分的に次の図の部分のみを取り出す。minmax法と同じ勝率がほしいので、ここでは(最大値がほしいとして)0.7が上に伝わってほしいことになる。そのためには上側の局面のところから常に最大の(0.7の)局面を選ぶようにすればよい。すると、下の0.7という勝率が上に伝わっていくことになる。つまり、ランダムに手を選ばずに、常にその局面のその時点での最大勝率の手を選んでいけば最適な勝率が得られる。なお、たどった全ての局面の勝率を保持していることを前提としている。

　ただし最大値のみを選ぶことにも問題がある。例えば、次の図のように0.6の勝率を持つ手ばかりを選んでしまって、0.7の勝率を本来なら持っている指し手を選ばなくなってしまうことがある。これを防ぐために一定の割合でランダムに指し手を選ぶことが必要になる。ただしランダムに選んだ場合には、その結果の勝敗を深さの浅いところには反映させないことにした。また、今回の実装ではランダムにせずに二番目に勝率の高い指し手を選ぶということにした。

　勝率の更新方法であるが、全ての指し手について分子分母を保持し、「勝ったら分子分母に同じ定数を足す」「負けたら分母のみに同じ定数を足す」という操作をしたのち、分子分母の両方を分母の値で割るということをしている。そうすると結局、分母の値を保持しなくてもよくなる(ややこしいことを書いているが要するに分母の値は保持していない)。また、こうしておくとプレイアウトの回数によらず常に勝敗結果が勝率に対して一定の影響を持つことになる。また、深い指し手ほど分子分母に足す定数を大きくし、木の浅い部分の変動を遅くした。

　ここまでが基本的な探索方法である。ここから先は勝率の初期値についての話になる。

　本当は勝率に初期値を与えたくなかったのだが、そうもいっていられないので初めてたどり着いた局面について局面に依存した勝率を計算することにした。指し手に依存した(実現確率のような感じの)勝率ではなく、あくまで局面評価による勝率を初期値とした。

　局面に初期値を与えるためには特徴量が必要である。特徴量はそれっぽければおよそなんでもよい。実際に試してみた最も簡単な特徴量は、盤面12マスに自分の駒(および敵の駒)の利いているマスがいくつあるかということを数えるというものだった。これだけのことでどうぶつしょうぎではそれっぽく動いてくれた(それっぽくどころではなくかなり有効であった)。特徴量が敵味方二つしかなく、それぞれ13種類しかとる値がないので、手作業で勝率の初期値を割り振ることができるのもよいところだった。

　この単純な特徴量でもよいのだが、将来の本将棋のことを考えるとそうもいっていられないので、複雑な特徴量を導入する。まず、12マスを筋ごとに分ける。4マス×3筋となる。この4マスについて利きの数を数える(0から4の値をとることになる)。さらに、玉がどの筋にいるかという情報(1から3の値をとる)を組み合わせる。これを敵味方の駒、敵味方の玉について計算する。さらに段についても同様に計算する。といったことをした。複雑なのでこういう分かりづらい説明しかしないが、簡単に言えば「部分的に利きの数を数えた」ということである。

　これくらいの特徴量なら手作業で勝率をつけられないこともないが、やはり将来の本将棋のことを考えて自動学習することにした。自動学習については様々なことを試してみたが、行き着いた先は「学習」というよりは「初歩的な統計」という感じのものである。

　まず局面をランダムに用意する。そしてその局面から今回書いたアルゴリズムで勝率を計算する。このランダム局面を表す特徴量にその計算した勝率を割り当てる。ただそれだけである。機械学習というほどのものではない。

　この学習法で最も注意すべきことは、ランダム局面の生成法である。駒得の度合、持ち駒の枚数、成りゴマの枚数など、人為的に決めなければならないパラメータが思ったよりも多い。人為的な要素を排除するために、初形の局面からランダム対局させて局面を生成してみたが、うまくいかなかった。今回用いた特徴量は部分を表すものであるが、学習に使う勝率は局面全体から求められるもののため、部分の有利不利と局面の優勢劣勢がなるべく一致しなければならないのである。ランダム対局の方では生データを見るかぎりではそのあたりがあまり一致していないように思えた。

　さて、上記のようなことをした結果、どれくらいの強さになったのかということを書こう。今回のアルゴリズムを後手、弱いminmax法(前回と同じベンチマーク)を先手とし、今回のアルゴリズムのプレイアウト回数を1000とした。その結果、720勝165敗115引き分け(勝負が80手を超えたら引き分けとした)となった。前回(2010年5月22日)の実験では同じ相手で10000プレイアウトで16勝81敗3分、100000プレイアウトで61勝35敗4分だったので、とても強くなったことが分かる。また、プレイアウト数が減ったので一手にかかる計算時間も短縮された。

　今回も実験に用いたプログラムをSkyDriveに置いておく。前回までとは異なり、しかるべき環境でコンパイルをすれば動くはずである(ただし、UIが貧弱であり操作性が悪いので遊ぶのには適していない)。なぜ前回までのようにプログラムの一部を削らないのかといえば、これまではライブログさんに遠慮していたのであるが、いろいろあったようなので遠慮しなくてもいいかなと思ったからである。というわけで、どうぶつしょうぎの現権利者のねこまどさんとピエコデザインさんと幻冬舎エデュケーションさんに迷惑をかけない程度に自由に使ってください。

　ところで、半年ほど前にとある女流棋士から「どうぶつと5五と本将棋で同じアルゴリズムを使うのは違和感がある」という内容のことを言われた。これはそのとおりであり、それぞれ似たようなルールであるものの大局観が異なる。また、本将棋であっても、居飛車対振り飛車の将棋と相振り飛車の将棋では感覚が違う。このあたりすっきりとさせたいところではあるが、明解な答えは見つからない。特徴量を変えているからそれでいいのだと考えている人もいるかもしれないが、おそらくこの問題はもっと深い。本将棋も九路盤囲碁も、理論上は必勝法が存在していて盤の広さも同じであるが、それでは本質的に何が異なるのかと問われるとルールが全然違うように「感じる」ということしか言えなかったりする。そして、ルールが違うのはどうぶつしょうぎと本将棋も同じなのである。桂馬が横に飛ぶ変則将棋とどうぶつしょうぎとでは、どちらが本将棋に近いのか。そもそも「近い」という言葉に意味はあるのかという問題でもある。きっとこのあたりのことは明解な解答が得られずに歴史に埋もれていくのだろうと思う。その前に囲碁と将棋でコンピュータが名人よりも強くなるように思えるからである。

　ちょっとこのところコンピュータ将棋に時間をかけすぎていたので、また音声をがんばります。誰か5五将棋でこのアルゴリズムを試してくれたら嬉しいなあ。多分、問題が山積みでまともな将棋にならないだろうけど。