コンピュータ将棋は来年プロ4段に追いつく

情報処理学会の機関誌「情報処理」の2009年9月号の小特集「コンピュータ将棋の新しい波」がおもしろい。

機械学習に基づく局面評価関数のパラメータ(重み)調整を取り入れた Bonanza が話題をさらったのは記憶に新しいが、今年の世界コンピュータ将棋選手権ではソースコードまで全部公開された Bonanza を用いた手法が多数登場したらしい。(というのはtihara さんの日記で知っていたが) ちなみに優勝したのは GPS 将棋であり、p.871に ktanaka 先生や@shnskさん、@gyoshiki さんたちの写真が掲載されている :-)

棋譜や全体の結果は特集を参照してもらうとして、興味深いのは勝又6段の「プロ棋士から見たコンピュータ将棋」と伊藤さんの「合議アルゴリズム文殊』」。先に後者のほうについて話すと、文殊は多数のプログラムの合議をして多数決で差し手を決めるシステムで、単にアンサンブル学習のことなんじゃないかと思うのだが、このアイデアが出てから実際に効果があることを示すまでの長い道のりについて書いてあって、びっくり。曰く、

 このアイディアは,当初ひどく評判が悪かった.「そんな単純な方法で強くなるはずがない」「個性の違う(棋風の異なる)プログラム同士が,単純に多数決を行っても,一貫した思考が行えず,却って弱くなるのではないか」といった批判が大勢を占めた.将棋プログラマの多くは,自分の開発しているプログラムに愛着が強く,強くするには,いかに精度の高い評価関数を設計して,より早く深く読む探索技術を磨くのかということの方が本筋だと考えていた.

とのことで、合議のアイデアを認めさせるために、「ヒントモード(局面を与えて候補手のみを返してくれる機能」を使って人手で(つまり各プログラム間で候補手出すプロトコルがないのでマニュアルでやるしかなかったそうだ)合議システムを実現して勝率を計算したりしていたのだが、あまり協力してくれる開発者がいなくて、そこに Bonanzaソースコード公開したのでなんとか動くプログラムが作れた、という話。合議の方法も本当は性格(棋風)の違う複数のシステムでアンサンブルしたほうがいいと思うのだが、とりあえず Bonanza の評価関数に異なる正規乱数を加えただけのものを6システム用意して合議させたそうで、それでオリジナルの Bonanza より強かった(直接対決ではたまたま負けてしまったが、全体の成績では5位の Bonanza を抜いて3位)、とのこと。

もちろん実際に実験するまでは確かなことは言えなかったわけではあるが、合議でよくなるのは(ランダムよりはいい予測を返す弱学習器を多数組み合わせれば高精度の学習器が作れるというブースティングなど、機械学習のバックグラウンドある人には)割と自然な話で、異議を唱える人いないんじゃないかと思っていたが、それに反対する人を説得するためにそこまでするか、というのが意外であった。(ちなみに3位以上は翌年の選手権のシード権があるのだが、「単純多数決の合議システムをアピールするだけに参加したので、シード権は放棄する」ことにしたそうだ)

もう一つの勝又6段の文章(エッセイ?)は、プロ棋士の視点から書いてあるものの、機械学習(統計的手法)を用いたコンピュータ将棋(もしくは自然言語処理も似たようなものだが)の直感的な説明をしてくれているので、非常によい解説だと思う。

 評価関数で苦しんできたプログラマが,機械学習による自動生成でその苦労から解放されたのが大きい.
 評価関数はいわが形勢判断(+大局観)で,コンピュータ将棋のキモになる.いくら読みが深くとも評価関数がつたなかったら意味がない.
(中略)
 特に囲いの堅さを数値化するというのは絵の美しさを点数にするようなもので,ちょっと局面が変われば数値が変わるため,非常に難しい.(中略)
 そこで今までは数値化しやすい駒の損得に多くウェイトがかかっていた.(中略)
 ところが今回の大会では駒の損得よりも効率を重視することが非常に多く見られた.(中略)従来のソフトの欠点であり限界にもなっていた駒得至上主義の呪縛から完全に解き放たれたようだ.
(中略)有効パラメータ数が100万〜80万という膨大な量で,これらの大量のパラメータでプロの感覚という質を手に入れた.まさに「量から質への転換」というべきものだ.(後略)

ちょうど我々はコンピュータ将棋の転換点にいるのでこういう驚きを共有できるのだが、数年もしたら当たり前になってしまって、それからあとこういう流れを知る若い人たちは、「評価関数の重みを人手でチューニングする時代なんてあったの???」って思ったりするんだろうなぁ〜……。

具体的にどういうパラメータ数で、どれくらい非ゼロの値がついていて、どういう正則化(評価関数)をしているか、なんて技術的な話は金子さんの「最近のコンピュータ将棋の技術背景と GPS 将棋」に詳しいので、突っ込んで知りたい人(機械学習のバックグラウンドはあるけどコンピュータ将棋はしたことない人)はそっち読むと「将棋でも同じテクニックが有効なのか」と分かって興味深いと思う。逆に将棋は知っているけど機械学習とか統計とか分からない、という人は GPS 将棋の評価関数(機械学習の用語で言うと素性)を見ると、どんな情報を使って学習しているのかが分かっておもしろいだろう。

実際初期の段階の GPS 将棋と何回か対戦したことがあるのだが、あのころからするとこんなに強くなるというのはすごい。やっぱり現在の精度や速度がどうかってのが重要だというビジネス(開発)の立場も分かるが、将来よくなることを信じてコツコツと続ける研究というのはすごいなぁ(結局そういうのが現状から先へ進むために必要)、と改めて思うのであった。