課題

2人のプレーヤーが相手の状況を全て把握しながら交互に手を打って、競い合う、戦略ゲームは「完全情報ゲーム」と呼ばれ伝統的に世界各地で行われてきました。インドのチャトランガが同一の起源と考えられているチェスや将棋、中国発祥の囲碁などのゲームが代表例です。

チェスに関しては人工知能の研究者が電子計算機発祥の当初から研究テーマとして研究し、1997年にIBMのチェスコンピュータ・ディープブルーが当時の世界チャンピオンのカスパロフを破り世界中に衝撃を与えました。また、将棋ではプロの棋士との対戦が行われるようになると2007年には当時の渡辺竜王とBonanzaが対戦しかろうじて渡辺竜王の勝利となると、2011年には電王戦が始まり、米長永世棋聖から当時の名人であった佐藤叡王まで多くのプロ棋士が対戦し、人工知能が圧倒的な実力を持つことが明らかとなりました。囲碁の世界では、2016年、2017年にイ・セドルや柯潔といった当時の世界最高とされる棋士を破って話題になりました。

ただし、アルゴリズムの変遷はありつつもそれぞれのゲームにはそれぞれの戦略があり、ゲームに性質に合わせて手法を考えて実装しなければならず、研究者や技術者にもそれぞれのゲームへの理解が必要でした。例えば、チェスや将棋では部分的な駒の配置（多くは３つの駒の配置）が全体の局面の評価にどのように影響するかを数多くの棋譜から学習し盤面全体の評価関数を作成して、その評価関数を相手は最小として、自分は最大になる手を効率的に探索し、翻って評価が最大となる次の手を決定し、さらに最終局面では詰将棋などのプログラムに適切に切り替えて勝利を目指すアルゴリズムが長く主流となっていました。また、囲碁ではランダムに交互に手を打つシミュレーションを行い、自分にとって有利な配置となると予測される経路を探索して、次の一手を決定すりモンテカルロ法と呼ばれる手法が主流になっていました。その後、ディープラーニングをメインとする手法が現れましたが、多くの棋譜が必要だったり、それぞれのゲーム特有の設計が必要であることは変わりませんでした。

もし、ゲームの性質にあまり依存せずに人工知能のみで強いプレイヤーが作れるようになれば、その手法は他のより役に立つ領域でも応用が期待できます。

解決方法

2018年12月、DeepMindは囲碁、チェス、将棋をそれぞれの領域特有の知識をほとんど使わずに自己対戦のみから強い人工知能プレイヤーを作るための手法AlphaZeroをScience誌に発表しました。

AlphaZeroは畳み込みニューラルネットワーク（コンボリューショナルニューラルネットワーク）を用いて、将来この状態から勝つかどうかの確率を計算するネットワークとどの手が最善かを確率的に推定するネットワークから構成される強化学習のモデルで、自分自身と対戦しながら強くなっていきます。

ゲームの当初は確率的に示された手をその確率にしたがってランダムに打っていきますが、ゲームの手数が増えてくるとより最大値をとる手を優先的に打つようにスケジューリングされています。これにより、ゲームの最初のランダム性により幅広い経験ができ、どちらかの勝ちやすさが偏るため勝敗に繋がる手がどれだったかが自動的に認識されることになります。

AlphaZeroはそれぞれのゲームに合わせた以下の情報のみでプログラムを修正しています（論文の補助資料より）。
（1）ゲームの盤面に合わせたネットワークの構造
（２）完全なゲームのルール（ルール違反となる手は探索されない）
（３）ゲームの状況を表す入力（盤面の駒の配置、将棋の場合：手持ちの駒、将棋とチェスの場合：千日手を判断するための繰り返しの回数）
（４）その時点での合法的な手の数（ノイズのスケールを決めるため）
（5）将棋とチェスでは512手で引き分けと判断し、囲碁では722手で終了する
これ以外の棋譜や定石、詰将棋・詰碁などの特殊なプログラムなどは一切使用していません。

どうなったか

AlphaZeroは以前、DeepMindが提案し世界チャンピオンを倒した囲碁の手法であるAlphaGO Zeroをベースに改善したもので、囲碁だけなく、チェスや将棋でも人間を凌駕する性能を示しました。実際には人間のチャンピオンを凌駕した先行手法を圧倒することが示されており、囲碁ではイ・セドルに勝利したバージョンのAlphaGO Zero、チェスでは2016年バージョンのStockfish、将棋では2017年の世界コンピュータ将棋選手権で優勝したElmoが対戦相手となっています。

学習にはDeepMindのグループ会社であるGoogleが提供する第一世代と第二世代のTensor Processing Unit (TPU)を用いて高速化を図っています。具体的には、第一世代5000個を用いて自己対戦のゲームを生成し、第二世代16個を用いてニューラルネットワークの学習を行いました。その結果、チェスでStockfishを凌駕するのに約4時間（30万回の対戦）、将棋でElmoを凌駕するのに約2時間（11万回の対戦）、囲碁でAlphaGO Zeroを凌駕するのに約30分（74000回の対戦）がそれぞれかかり、人間を凌駕する人工知能に勝つのにはデタラメなモデルから初めたとしても、1日もかからないことが示されています。

最終的に、それぞれの競技のチャンピオンプログラムに対して圧倒的な性能を示しました。チェスではStockfishに1000回のゲームで155勝-6負-839分、将棋では先手で98.2%、全体で91.2%の勝率となりました。

学習が早い理由はハードウェアの向上だけでなく、ニューラルネットワークによりより有望な手のみを探索するためであると主張されています。例えば、1秒間に探索する数に関して、Stockfishは6千万、Elmoは2.5千万の手をそれぞれ探索するのに対して、AlphaZeroは1秒間にたった6000の手を探索するのみとなっています。これはモデルそのものの性能も向上していることを示しています。

まとめ

チェスと将棋は同じ起源をもつゲームとして同様の仕組みが使用できることは、機械学習を使用してコンピュータ将棋に革命を起こしたBonanzaがチェスの手法を取り入れていたことからもわかりますが、囲碁も同じモデルで学習できることは驚きでした。今回の対象は完全情報ゲームでしたが、（以前からのこの類のモデルと同様に）確率的なモデルとして実現しているため麻雀のような不完全情報ゲームでも、大きな修正が必要なく応用できる可能性があります。

今回は、統一的なモデルといっても入力の構造やゲームのルールは厳密に与える必要はあります。今後はさらに設計者の負担が軽くなるように進歩していくと考えられます。具体的には、ゲームのルールを強化学習の報酬計算に組み込んで、ルール違反には罰を与える形で自動的にルール違反を避けるモデルも考えらrているようですし、それぞれのゲームが行われる盤面をカメラで撮影した状況で判断ができるようになれば、入力もゲームに合わせる必要は無くなります。そのようなモデルが登場すれば、ゲームだけでなく様々な用途に同じアルゴリズムで対応するようになっていくでしょう。

参考資料

David Silver et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play, Science, 2018

研究室紹介OPAL-RING　保木研究室　[電気通信大学]