TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

【将棋AI】N駒関係をMulti-Head Self-Attentionで学習する

こないだ参加したハースストーンのAIコンペの関連論文を読んでいて、個人的に興味深い論文があった。

Helping AI to Play Hearthstone using Neural Networks

この論文では、ハースストーンのゲーム状態からニューラルネットワークを使って勝率を予測する方法について提案している。
ゲーム状態は、単純化して、2人のプレイヤーがそれぞれフィールドに出した最大7体のミニオンで表現している。
ミニオンはヘルス、攻撃などの7つの属性に対応する特徴量で表現される。
これらのミニオンの特徴量をニューラルネットワークに入力して勝率を予測している。

この論文で面白いのは、ニューラルネットワークに畳み込み層を使用して、ミニオン同士の関係を学習できるようにしている点である。
具体的には、自分と相手のミニオンの位置(1~7)が同じミニオン同士をペアにして1次元のテンソルとし、各位置の1次元テンソルを行方向にならべることで2次元のテンソルとし、畳み込みで処理できるようにする。
次に、自分のミニオンの位置をサイクルさせて(1を2、2を3、・・・、7を1にする)、同様に2次元のテンソルを作り、このサイクルを6回繰り返してできた6個(最初のを合わせると7個)の2次元テンソルをチャネル方向に並べることで、3次元テンソルとして畳み込み層への入力としている。
サイクルさせる処理のことをPCS(partial cyclic shift)演算と呼んでいる。
f:id:TadaoYamaoka:20200712135847p:plain

畳み込み層のカーネルには、[1, 14(ミニオンのペアの特徴量), d(任意フィルタ数)]が使われる。
行方向のカーネルサイズは1なので、列方向(ミニオンのペア)にのみフィルタが適用される。
(隣のミニオンの同士の関係を学習するために[2,14,d]というフィルタもある)

論文には直接書かれていないが、これはつまり、自分のミニオンと相手のミニオンの2駒関係を畳み込み層で学習していると解釈できる。

将棋AIで試せないか

AlphaZeroのCNNでは、入力層は、盤面の座標に対応しており、カーネルサイズは3×3なので、畳み込み層では主に近くにある駒の関係が学習される。
深い層では離れた駒の関係を学習しているかもしれないが、CNNによる画像認識では局所的な特徴量が学習されるという指摘がある。
Deep convolutional networks do not classify based on global object shape

そのため、離れた駒の関係を直接学習できるようなニューラルネットワークの方が好ましいかもしれない。

そこで、将棋AIでも2駒関係を畳み込み層で学習することができないか考察してみた。

上記の論文と同じように2駒関係を畳み込み層で学習しようとすると、駒を14次元ワンホットベクトルで表して、自分と相手の駒のペアを28次元のベクトルで表し、座標に対応する駒のペアを行方向に並べればよい。
ただし、サイクルさせると自分の駒の位置の情報が消えてしまうため、位置を表す情報も自分の駒の表現に加える必要がある。
また、自分の駒同士、相手の駒同士の関係は学習できないため、駒のペアに自分の駒同士、相手の駒同士のペアも考慮した方がよさそうだ。

この方法では、持ち駒の位置も考慮すると行の数が多くなり、PCS演算でサイクルさせる回数も多くチャネル数も多くなり効率が悪そうである。
また、将棋ではある位置に駒がない場合の方が多いので、畳み込み層で処理するには無駄が多い。
(NNUEのように疎ベクトルを差分計算した方がよっぽど良い。)

CNNの代わりにSelf-Attentionを使う

そんなことを考えていてひらめいたのが、PCS演算ではなく、Multi-Head Self-Attentionを使えばどうだろうというアイディアだ。

Multi-Head Self-Attentionは、位置が離れた要素の関係も学習するCNNのようなものと解釈できる。

Multi-Head Attentionの説明に、Transformerの論文の図を引用する。
(Multi-Head Attentionの詳細は説明がめんどうなので省略)
f:id:TadaoYamaoka:20200712143048p:plain
Self-Attentionでは、この図のQKVが同じ入力になる。

右の図のQKVの後につながるLinearが学習する関数となり、畳み込み層のフィルタのパラメータに該当する。

入力には、すべての駒を駒の種類を表すワンホットベクトルと、座標と保持しているプレイヤーをPositional Encorderでエンコードしたものの和や連結で表現して入力することができる。
もしくは、Positional Encorderを使わずに、駒ごとの位置に対応する要素を駒がある場合に1にしたベクトルとしてもよいかもしれない。

これをMulti-Head Self-Attentionで処理することで、離れた駒であっても依存関係を学習できる。
また、2駒の依存関係に限らないため、N駒の関係を学習できる(と思う)。

まとめ

以上、つらつらとアイディアだけを書いてみた。
効果があるかは試してみないと分からないので、(やる気がでれば)後日試してみる予定である。