囲碁とコンピューター - 越境するコンピューター

コンピューターが囲碁名人に勝ったというのがニュースになってます、面白そうなので調べてみました。

囲碁、将棋、チェス、チェッカー、三目並べは仲間です

どれも”二人で対戦する”、”どっちか勝てば、もう一人は負ける”、”相手の情報は全て分かる”、”手数の組み合わせは有限”という点で同じ分類になります。こういうゲームを「二人零和有限完全情報ゲーム」とよびます。

「二人零和有限完全情報ゲーム」は先手、後手が最善手を指すと必ず”先手必勝”、”後手必勝”、”引き分け”のどれかになることが証明されています。三目並べ、チェッカーはその手順が発見されていますが、囲碁、将棋、チェスではまだ発見されていません。

三目並べをコンピューターにやらせるには？

三目並べは最善手の手順（結果は必ず引き分けになる）が発見されています。コンピューターに三目並べをやらせる場合はその最善手のロジックをプログラムすればいいですね。

* 最善手はリンク先「戦法のこつ」を参照ください　三目並べ - Wikipedia

最善手が発見さている三目並べだとこの方法がとれますが、囲碁・チェス・将棋の場合最善手はわかっていません、手数も段違いに多いです。ではどうすればいいか？

チェス・将棋をコンピューターにやらせるには？

次の一手のパターン、その次の一手のパターン、…　こうやって終局までの全てのパターンを調べようとすると、指数的にその対象が増えていくのでどんな優秀なコンピューターでの現実的な時間で全てのパターンを調べて評価することはできません。

そこでチェス・将棋で一般的に使われるのが評価関数です。

評価関数とは？

終局までのパターンを調べる替わりに、数手先までのパターンを調べてそのそれぞれのパターンを評価して最善手を決める方法です。なんらかの基準（例えば持ち駒の種類、数など）によるその時点での優劣が評価関数に使われます。

囲碁をコンピューターにやらせるには？

囲碁も基本的にはチェス・将棋と同じなんですが、違いもあります。

ひとつは手数の組み合わせが多いこと、囲碁の盤面は 19 x 19 手順の組み合わせはチェス・将棋と比べても段違いに大きいです。

もうひとつは”評価関数の作成が難しい”ということ、将棋・チェスの場合は持っている駒である程度優劣が判断できますが、囲碁の場合はみんな同じ石、しかも囲碁は終盤まで優劣が明確にならないという特徴があるので評価関数を作るのが難しいとされてきました。

この課題を解消するため使われているのが「モンテカルロ木探索」という手法です。

モンテカルロ木探索とは？

モンテカルロ木探索をざっくり”木探索”と”ロールアウト”というキーワードで説明します。

ロールアウト

評価関数作るのが難しいなら実際にそこから囲碁やってどうなるかみてみよう、というアプローチです。ある局面からコンピューターにランダムに手を打たせて（最低限の囲碁のルールは守って）最終的にどのくらい勝つ確率が高いか調べようという発想です。

木探索

先読みの手数が多くなるほど選択枝は増えていきます。１手先に４つの選択枝があるとしてその先のそれぞれに４手あるとすると１手先：４手、２手先：１６手、３手先：６４手、このように指数的に増えていくので全部調べていたら大変だから有望な手筋だけしらべるようにする仕組です。枝を選定していくイメージですね。

この方法で作った囲碁プログラムは強くなったけどトッププロにはまだまだ遠く及びませんでした。

AlphaGoのアプローチ

まだトッププロに勝つには１０年くらいかかるといわれていた中、トッププロに勝利したAlphaGoはどんな仕組みになってるのか、ざっくり説明してみます。

仕組み

モンテカルロ木探索をベースに機械学習を追加して機能強化した作りになってます。

木探索

機械学習（畳込みニューラルネット）を使って実装された"Value Network" を使用して最適な探索を決定。

評価

機械学習（畳込みニューラルネット）を使って実装された"Policy Network" とモンテカルロ木探索で一般的に使われているロールアウトを併用して局面を評価

学習方法

学習を二段階に分けて行っています。

第一段階　教師有り学習

過去のプロの対戦棋譜を入力データとして使い教師有り学習を実施。

第二段階　強化学習

次にコンピュータープログラム同士を対戦させて学習を実施。とてもざっくり簡単にいうと勝った方にご褒美あげていく方法。

ここで使われている機械学習の手法は特別なものではなく一般的なものです。これは機械学習の特徴（ロジック自体はシンプルで汎用的、特徴抽出とデータによる学習が重要）を表していると思います。

＊誤りあればご指摘いただければ幸いです

参考書籍

計算科学：ディープニューラルネットワークと木探索を用いた囲碁の習得