Ponanza開発者が語るディープな将棋AIの話 第1回

電王・Ponanza開発者が語る、理由がわからないけどスゴイ“怠惰な並列化”

　皆さんこんにちは。

　私は将棋プログラム「Ponanza」の作者、山本一成と申します。Ponanzaは初めてプロ棋士を破った将棋プログラムで、近年最も強い将棋プログラムと言えると思われます。また、2017年もトッププロ棋士の方と対局することが予定されています。Ponazaの改良のための機械学習に現在ジサトライッペイさんのPC「大紅蓮丸」の計算リソースを借りているのですが、その関係で原稿を書いてとお願いされたので、3回に渡って将棋プログラムの今について、書いていきたいと思います。

ジサトライッペイの自作PC「大紅蓮丸」。Xeon E5-2699 v4×2、128GBメモリーを搭載する、44コア/88スレッドのモンスターマシン。

フリーランチの終焉、並列化の効率問題

　アスキー読者の方々には言うまでもないのですが、まずは近年のCPU事情について解説していきたいと思います。ちょっと昔まではCPUはシングルコアが当たり前で18ヶ月経過すればCPUのトランジスター数は倍になり、性能が向上するという流れが続いていました。ソフトウェアはその性能向上に伴い、同じコードでも勝手に高速に動くようになる、俗にいうフリーランチ（タダ飯）状態だったわけです。

　しかし、Intelを含めるCPUベンダーの巨人たちは10年前ぐらいに、1コアあたりのCPU性能向上にある程度見切りをつけました。性能向上を支える、回路の微細化による性能向上が技術的、あるいは科学的な限界に近づいてきたからです。その代わり、マルチコア化に流れ、さらにSIMDなどの命令レベルでの並列化も進んできました。その一方で、並列化が難しいプログラムのほうはあまり発展しませんでした。

　そんな中、将棋プログラムも最近までは残念ながら並列効率が悪かったのです。読者のみなさんの多くは直感的に、それぞれの指し手に対してCPUコアを割り当てることで、最適な並列効率が得られると思われるかもしれません。しかし、2つの理由からそう簡単には性能が上がらないのです。

　ひとつは粒度の問題です。あるCPUコアの指し手は簡単に悪い手を判断できますが、別のCPUコアの指し手はいい手か悪い手かの判断が難しい、というシーンが出てきます。そうすると結局難しい指し手の結論が出るまで、全CPUコアの動作が律速されるのです。もちろん、各CPUコアは計算が終わっていても常に作業を探しているので、CPU使用率は常に100％ですが、実際は指し手を計算しているCPUコアは限られているということです。

　もちろん、難しい指し手を探索しているCPUコアを暇になったCPUコアが助けにいくということもできるのですが、とんでもなくめんどうで複雑なコードになる上、そこまでやってもなお性能向上は限られているので、見合わないというのが現状です。

　もうひとつは非常に良い手をどこかのCPUコアが発見した場合、他のスレッドの計算がすべて無効になるということです。作業の並列化はできていますが、これではあまりに計算リソースに対して得る結果が見合わない。つまり、並列効率が悪い、ということになります。

Ponanzaが自己対戦しているところ。

なぜうまくいくかわからない“怠惰な並列化”という手法

　しかし、ここ2年くらいで新しい探索方法が生まれました。正確には昔からあった方法が見直されたというのが正しいかもしれません。探索方法の名前は“LazySMP”、日本語に直すと「怠惰な並列化」といったところでしょうか。

　この手法は凄まじくプログラムが単純で、各スレッドがほかのCPUコアの計算が終わるのを待たずに、つまり律速せずに、動作できるのです。探索結果をメモリーに書き込んで全スレッドで共有し、他のスレッドはそれ以外のスレッドの探索結果が参照可能な場合は、それを利用して探索をスキップするなどして動きます。

　実はこの手法ではスレッド数が8ぐらいまでの場合は従来手法に比べて、それほど効果が出ません。しかし、驚くべきことに8スレッド以上なら従来手法よりも高い並列効果が得られるのです。LazySMPはスレッドがいまのところ（88スレッド）は順調に伸びています。

　なぜこの手法がうまくいくのか。原因は色々考えられますが、ひとつには同期が存在しないのである種のアンサンブル効果（同じ問題に対し、解法の違う複数人の回答で多数決を取ると正答率が上がるという現象）というものが得られるから、ではないかと思います。同期を取らないことで同じところを何度も探索することになるのですが、その結果がある種の多数決的な動作となって、アンサンブル効果が生まれるのだと推測しています。正確な理由は残念ながら不明なんですけどね……。

PonanzaがLazySMPで探索している様子。

わからないけどスゴイ、それが正当進化なのかも

　話は変わりますが、ディープラーニングの躍進は読者の記憶に新しいところだと思います。やや乱暴な意見を言えば、理論の原型は何十年も前からあったと思います。しかし、最近になってここまで盛り上がってきたのは、CPUとGPU、とりわけGPUの性能向上が大きな理由でしょう。膨大な計算量があることで膨大な試行錯誤が可能になり、そこがノウハウの蓄積に繋がりました。

　また、機械学習やディープラーニングで育つ人工知能（将棋プラグラムを含む）は、このままいけばハードウェアの進化で2045年に人類すべての知性の総和を超えると予想されています。人間一個人の話でなく、人類すべてです。もしそうなればその後の歴史はどうなるのか。残念ながら人類にはわかりません。これは人類の知性による未来予測が及ばない人工知能が生まれる日、特異点（シンギュラリティー）なんて呼ばれていますね。

　話を戻しますと、つまりLazySMPで得られる成果はこれと似た現象だと考えております。体感で言えば、LazySMPは実はプログラマーには人気がない手法です。なぜかと言えば、前述のように結局のところどうしてうまくいくのか、その正確なところがプログラマーにはわからないからです。ディープラーニングも本質的にどうしてうまくいくのかわかっているプログラマーがいません。あくまで将棋プラグラム業界では、という話ですが。

　私は自分が作った将棋プログラムに勝てません。ある意味当たり前です、なぜなら私自身よりも遥かに強いプロ棋士達に勝てるように作成するわけですから。もちろんアルゴリズムは全部自分で記述したものなので、細部までよく考えて、かなり深く理解しています。しかし、どうしてそれが強いのか真の意味では理解しているとは言えません。せいぜい経験的、あるいは実験的にこうしたら強かったと言える程度です。

　近代科学は対象を分解して、理由を解明していくことで世界を解き明かしてきました。しかし、近年の情報科学は人間の解釈性が著しく悪いアルゴリズムが時代の先端を走り始めています。要素を分解していっても、そこに本質を発見できていないのです。人間にはある程度以上の複雑な挙動がわからないのです。

　しかし、です。これが正しい進化の流れなのかもしれないとも考えてしまうのです。作ったプログラマー本人の理解や直感を超える動作こそが、今の人工知能に求められるからです。

　次回は近年のコンピューター将棋の急成長を支える「機械学習」について解説します。

ASCII倶楽部

お知らせ