ディープラーニングを用いた囲碁の最終盤面の予測

先日、コンピュータ囲碁の大会「第10回UEC杯」に参加してきました。このUEC杯で使った囲碁AIがユニークであると評価されまして「独創賞」をいただきましたので、その賞の対象となった部分について解説したいと思います。

# はじめに
現在（2017年3月）、強い囲碁AIの多くはPolicy Network、Value Networkとモンテカルロ木探索を組み合わせて作られているようです。これは2016年に発表されたAlphaGo（Master）に採用されている方式で、現在の囲碁AIの主流となっています。Value Networkは囲碁の盤面データからその盤面の勝率を予測するネットワークで、これとモンテカルロ木探索を組み合わせて盤面の先読みを行います。一方、今回のUEC杯で私が開発した囲碁AIは、Value Networkやモンテカルロ木探索を使わず、盤面データから最終盤面を予測するニューラルネットワークを使って先読みを行っていました。

# やりたいこと
囲碁で先読みをするためには、その盤面が有利なのか不利なのかを判定しなくてはなりません。AlphaGoをはじめとする多くの囲碁AIではValue Networkとモンテカルロ木探索を使って盤面の有利不利を判定しています。しかし、私の囲碁AIでは、Prediction NetworkとTerritory Networkを使って最終盤面を予測し、そこから途中盤面の有利不利を判定しています。

図１はPrediction NetworkとTerritory Networkを使った盤面の有利不利判定方法の概要です。まず、途中の盤面のデータをPrediction Networkに入力して最終盤面を予測します。この予測結果と途中の盤面を比較して、それぞれの石の死活を予測します。次に、途中の盤面データをTerritory Networkに入力して最終的な地合いを予測します。Prediction Networkを使った死活の予測とTerritory Networkを使った地合いの予測を足し合わせることで、入力となった途中の盤面での有利不利（何目差がついているかを含む）を判定します。

![ueccup1.png](https://qiita-image-store.s3.amazonaws.com/0/171281/b8ed2306-9dfe-a29d-bc7a-2afe85cc2066.png)
図１　Prediction NetworkとTerritory Networkの使用目的

# Prediction NetworkとTerritory Network
Prediction NetworkとTerritory NetworkはLayer数以外は同じ構成となっています。図２はPrediction NetworkとTerritory Networkの構成を示した図で、どちらもResidual Network（pre-activation）を使って構成しました。入力データは碁盤の端の情報を含む21x21x?（?の部分は入力データに含めるデータによって変わります。石の情報だけなら2となります。）の行列です。この入力データをResidual Networkで計算して19x19x3の出力データを得ます。この出力データは、盤面(19x19)の黒石・白石・空きの値となっており、それぞれの座標でsoftmaxの計算を行うことで各座標の黒石・白石・空きの確率を得ることができます。

ネットワークのLayer数ですが、Prediction Networkを28層、Territory Networkが24層としました。Residual Networkを少し変形させると必要と思われるLayer数を調べることができるのですが、Prediction Networkは24層程度、Territory Networkは20層程度あれば十分なようです（ちなみに、Policy Networkは18層で十分という結果になりました）。

![ueccup2.png](https://qiita-image-store.s3.amazonaws.com/0/171281/c4df670d-4360-4556-dfe1-8f880a065ddf.png)
図２　Prediction Network/Territory Networkの構成

# 最終盤面の予測結果
約4万5千個のプロの棋譜を使って、Prediction NetworkとTerritory Networkを学習させました。反転回転で8倍にデータを増やし、約3000万件の訓練データ（盤面データ）を使いました。最適化手法はAdam（学習係数等はAdamの論文通り）で、正則化は入れていません。予想精度（各座標で白石・黒石・空きとなる予想の正答確率）ですが、Prediction Networkが約73%、Territory Networkが約84%となりました。

図３と図４は実際にPrediction NetworkとTerritory Networkを使って最終盤面と地合いを予測したデータです（＃が黒石、０が白石、・が空きです）。図３(A)の盤面データをPrediction Networkに入力して得られた最終盤面予測が図４(C)となり、Territory Networkに入力して得られた最終地合い予測が図４(D)となります。また、図３(B)は図３(A)の実戦での終局盤面です。

図３(A)では、下辺の戦いが一段落していますが、上辺の戦いはこれからとなっています。そのため、最終盤面予測（図４(C)）と最終地合い予測（図４(D)）ともに、上辺の予測は不正確なものになっています。一方、下辺の予測についてはそれなりに正確なものが出ているのではないでしょうか。左下に黒地ができるであろうことや、２の九の黒石が死ぬであろうことが予測されています。

![ueccup3.png](https://qiita-image-store.s3.amazonaws.com/0/171281/5f9e33d0-699e-34f9-936d-c9bf91786356.png)
図３　入力データと正答データの例

![ueccup4.png](https://qiita-image-store.s3.amazonaws.com/0/171281/13a32a06-143b-8f2b-fdad-1e240603f506.png)
図４　最終盤面と地合いの予測例

ちなみに、上記のデータは見やすいようにするため、座標ごとに黒石、白石、空きに分類して表示していますが、実際の有利不利の判定計算は座標ごとに黒石、白石、空きの確率（期待値）を使います。

# おわりに
今回のUEC杯では、Policy Networkと上記のPrediction NetworkとTerritory Networkを使って参加してみました。この盤面予測を使って先読みをしようとする試みがユニークであると評価してもらえまして、第10回UEC杯の独創賞をいただきました。ユニークであると言ってもらえることは私にとってはこれ以上ない評価でして、今回の挑戦に大変満足しております。

探索のための評価ネットワークとして構築したPrediction/Territory Networkですが、終局判定にも使うことができます。死活と地合いを判定できますので、新たに置いた石の死活と、それによって増える地合いを計算し、不利なところにしか合法手がないとなると、そこでパスをすれば良いことになります。今回、終局判定のプログラムを作らなくてよくなったので、AI作成が大変楽になりました。

ただ、欲を言えば、もう少し強い囲碁AIを作りたかったなと思ってもいます（私のAIはFuegoと互角ぐらいですので、アマ1-2段程度の実力ということになります）。UEC杯では、絶芸・Rayn・AQなどの上位陣とも戦わせてもらったのですが、まったく勝負にならず負けてしまいました（絶芸の勝負では中盤で私のAIが「100目負け」を予測したので投了しました）。

私のAIが弱かった理由ですが、以下のようなことが挙げられると思います。

(1) Policy Networkの精度が低い
私の囲碁AIのPolicy Networkの正答率は約43%でした。上位陣は正答率が55%以上のPolicy Networkを使っているようです。このPolicy Networkの正答率は探索木の精度に直接効いてきますので、とても重要です。

(2) 地の計算が不正確
Territory Networkを訓練するためには地合いの教師データを作成する必要があるのですが、この教師データを作成するプログラムが不正確ですと、必然的にTerritory Networkが不正確となります。今回、セキを考慮した地の計算プログラムを作れなかったため、セキを判定できないTerritory Networkとなってしまいました。

(3) Policy NetworkとPrediction/Territory Networkの「強さ」がチグハグ
候補手の作成はPolicy Networkが行うのですが、このPolicy Networkによって選ばれる手はあまり強い手とは言えません（おそらく、アマ1-2級程度だと思います）。ところが、Prediction/Territory Networkが予測する最終盤面はプロが進めた場合の最終盤面となっています。つまり、Prediction/Territory Networkが「良い」と判断したとしても、それを活かすだけのPolicy Networkになっていませんでした。実際、Prediction/Territory Networkが有利と判定した場所に石を置いて、上手くすれば生き残れるはずなのに、打ち方を間違えて全滅させられるということが何回もありました。

次回も参加予定ですので、また囲碁AIの開発を計画しています。次回は、少し違う形式のニューラルネットワークを使えればよいかなと思っていますが、まだ基礎評価も終わっていないので、どうなるかわかりません。

# おまけ：第10回UEC杯の所感
今回の第10回UEC杯は、絶芸の強さが際立った大会でした。私も予選で対戦させてもらったのですが、先読みの正確さには驚きました。また、非常にアグレッシブなAIで、半目勝ちではなく、完勝を目指して打ってきます。もし投了しなかったら、私の黒石はすべて消えていたかもしれません。

RaynやAQをはじめとする上位陣のAIとも対戦させてもらいました。どのAIも非常に完成度が高く、スキだらけの私のAIでは勝負になりませんでした。絶芸だけではなく、上位陣の囲碁AIは攻撃的な囲碁をするようで、必然的に完勝か完敗になりやすいように思えます。

DeepZenとは対戦できなかったのですが、予選や決勝を見ていると、良くも悪くも前評判通りの強さだったのではないかなと思います。絶芸に負けてしまったことが大きなニュースとなっていますが、2位のDeepZenと3位以下では大きな実力差が存在しているように思えます。

あと、印象的だったのは、絶芸をはじめとするいくつかの上位チームが個人では到底真似出来ない計算機資源を投入してきたということです。AlphaGoの方式を踏襲し、多くの計算機資源を投入するのが現在の正攻法ということになるのかもしれません。もっとも、どんなに多くの計算機資源を使えたとしても、囲碁や機械学習に関する正確な知識とそれをコーディングする高い技術力がなければ強い囲碁AIを作ることはできないのですが。

今回が初めての出場だったのですが、 UEC杯は和やかな雰囲気の熱い大会でした。また、対戦するときはお互いを尊重しあっており、強くとも驕らず、弱くとも卑屈にならずに大会が進んでいたのも印象的でした。時期は決まっていませんが、次回が開催されることは決まっているとのことですので、今から楽しみにしているところです。