TadaoYamaokaの日記

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

将棋AIの実験ノート:chain ruleで方策を定義する

現在dlshogiでは、方策ネットワークの出力は、移動先座標と移動方向(8方向+桂馬2方向+駒打ち7方向)の組み合わせで表現している。
これには、移動元を座標で表すと、分類するクラス数が多くなり精度に悪影響があるため、移動方向として表現することでクラス数を抑えるという意図がある。
移動方向だけではどの座標の駒を動かすかは直接はわからないが、将棋では移動方向さえわかれば、盤面から移動元の駒が一意に特定できるため問題ない。

クラス数が増える問題

将棋のルールを活かした出力の表現になっているが、すべてのゲームで同じように表現できるわけではない。
たとえば、駒をジャンプすることができるというルールのゲームであれば、移動方向だけでは移動元の駒を一意に特定できない。
その場合は、移動元の座標や距離も含めた組み合わせの考慮が必要になり、クラス数が増えることになる。
ゲームが複雑になればクラス数が爆発的に増えてしまう。

chain rule

先日、StarCraft IIの論文を読んでいて、方策の出力の表現方法について面白い方法がとられていたので、将棋AIでも試してみた。
StarCraft IIというRTSゲームでは、ユニットを座標で範囲を指定して選択してから、建設の場所を指示するといった組み合わせで行動を行う。
マップを低解像度で表現した場合でも100万オーダーの組み合わせ数になる。
この問題に対処するため、確率のchain ruleを使用して、自己回帰的に方策を定義している。

\displaystyle
\pi_\theta(a|s) = \prod_{l=0}^L  \pi_\theta(a^l|a^{\verb|<|l},s)
行動の操作がLステップで構成されている場合に、lより前のステップの操作と状態を事前条件としたステップlの確率の、ステップ0~Lまでの総積を計算している。

ただ、このままだとニューラルネットワークで表現が難しいため、簡略化して、
\displaystyle
\pi_\theta(a|s) = \prod_{l=0}^L  \pi_\theta(a^l|s)
として表現している。
状態のみを事前条件として、それぞれのステップの操作の確率を独立に求めて、それらの総積を計算している。

将棋AIへの応用

この考え方を将棋AIでも試してみた。
とくに精度が上がることは期待していないが、この表現方法でも十分な精度で学習できるかに興味がある。

将棋の指し手も、駒を移動するか駒を打つか選んで、移動元の駒または打つ駒を選んで、移動先の座標を選択するという操作の組み合わせになっている。
これらを以下の3つの確率として表現する。

  1. 移動先座標
  2. 移動元座標または駒打ち
  3. 打つ駒の種類または移動

移動か駒打ちかの選択は、2と3に含めている。
これは、ニューラルネットワークで学習する際の都合による。
3つの確率から損失を計算する際に、例えば駒打ちの場合に、2の損失が計算できなくなるため、対象外というラベルも必要になる。
移動元がないということは、駒打ちということになるので、2で表現できている。
同様に3には打つ駒に加えて移動を表すラベルも加えている。

これらの3つの確率を方策ネットワークで出力し、それらの総積をとり、最大の確率となる手を指し手とする。

学習の際は、総積の計算は行わず、それぞれの出力に対応する正解ラベルを与えて学習する。

実装

上記の考え方に従って方策ネットワークの実装を行った。
GitHub - TadaoYamaoka/ShogiChainRulePolicy

盤面から入力特徴量を作成する箇所は、cshogiを使用している。

学習結果

elmoで生成した10万局面、テスト局面4万局面を使用して学習させてみた(MomentumSGD、学習率0.01、バッチサイズ512)。
f:id:TadaoYamaoka:20190928235509p:plain
f:id:TadaoYamaoka:20190929000927p:plain

損失は単調に減少しており学習できていることが確認できた。
正解率は、3つ目確率(acc3)(打つ駒の種類または移動)が高くなっているが、正解に移動の方が多いため移動と分類する数が多くなるため、正解率が上がっているためである。
同様に3つ目確率(acc2)(移動元座標または駒打ち)も駒打ちの場合、正解しやすく正解率が上がっている。
最終的な確率(acc)では、12%の精度で指し手を予測できている。

現在のdlshogiの指し手の表現で同じ局面を学習させて場合とも精度の比較を行う予定。
(続く)