将棋AI

「将棋AIで学ぶディープラーニング」

1章 コンピュータ将棋について

評価関数とミニマックス探索という現在の将棋AIの原型となる考え方が「Programming a Computer for playing Chess」という論文で発表されている

その後、α β探索のアイディアが発明されている

Bonanzaは評価関数を大量のプロの寄付から学習して自動で作成するということが行われていた

AlphaGo Zeroは人間の棋譜なしで異常な強さになった

・世界コンピュータ選手権

・将棋電王トーナメント

・floodgate

どれかに参加してみると良さそう

2章 コンピュータ将棋のアルゴリズム

ゲーム木

全探索は無理なので、探索途中の曲面がどのくらい勝ちやすいかを何らかの基準を元にして数値にして評価する

ミニマックス法

評価値を使ったゲーム木探索の基本的な手法がミニマックス法である

局面が自分の手番であれば子ノードのうち評価値が最大のものを、相手の手番であれば最小のものを選ぶことを繰り返す

ルートノードで選択したものを手とする

評価関数

現在では評価関数で使われるパラメータを機械学習で調整することが行われている

αβ法

ミニマックス法の探索の効率を上げたものがαβ法である

調べている曲面が同じ兄弟の局面の評価値を参照することで探索を省略できる場合がある

αβ法を使って探索することで探索する局面を減らし、ミニマックス法と同じ指手を選択できる

評価関数の機械学習

機械学習の用語で、三駒の配置のように点数をつける項目を特徴という

どのような特徴が有効であるかは人間が決める必要がある

将棋のける機械学習の成功の要因は3コマ関係が評価関数の特徴として有効であったから

強化学習

最近の将棋AIはAI同士の棋譜を使って学習している

これは強化学習の１つ

elmoは深い探索の評価値を浅い探索の評価値に近づける学習をしている

まとめ

コンピュータ将棋ではゲーム木を探索して、評価関数で局面を評価する

探索方法はミニマックス法を改良したαβ探索である

現在では自己対局による強化学習

現在は、コンピュータ将棋の強化学習のわかりやすい資料がなく、Aperyややねうら王のソースコードで学んでいる

3章 コンピュータ囲碁のアルゴリズム

本章では、コンピュータ囲碁で用いられているモンテカルロ木探索の概要について述べる

AlphaGOもモンテカルロ木が基本となっている

コンピュータ囲碁の課題

将棋と比べて探索空間が広い

評価関数を作るのが難しい

という課題がある

また石自体にも特徴がないため石の配置だけから有効な評価関数を作るのもキツかった

モンテカルロ法

モンテカルロ法ではランダムに着手を行い、終局までプレイして、その勝敗の平均値から局面の勝率を推測する

囲碁はランダムにプレイアウトした場合でも終局できるのでモンテカルロ法と相性がいい

囲碁の知識を活用し、直前の着手が当たりであれば逃げる手を選ばれやすくするなどしてプレイあうとの質を高める工夫が行われている

モンテカルロ木探索

一手あたりにプレイアウトできる回数は限られている

そこで、ゲーム木と組み合わせたモンテカルロ木という手法が考え出された

これは有望な手に限ってプレイアウトをする

1 選択

ミニマックス戦略でゲーム木を辿る

2 展開

訪れたノードの訪問回数が閾値未満の場合、展開は行わず、プレイアウトのステップに進む

訪問回数が閾値より大きい場合、候補手でゲームを展開する

3 プレイバック

ゲーム木の末端まで辿ってそのノードの訪問回数が閾値以下の場合、そのノードからプレイアウトを行う

4 バックアップ

プレイアウトを行った結果の勝敗を報酬として辿ってきたノードに報酬を加算する

この手順を思考の時間内に何回も行い、最終的にルートノードでの訪問回数が最も多い手を打ち手として選択する

勝率の高い手を選択することと、まだ探索していない手を探索することはトレードオフの関係にある

囲碁AIではノードの選択のアルゴリズムにUCB1というアルゴリズムが使用されている

ICBを用いたモンテカルロ木のことをUCTアルゴリズムという

AlphaGoで用いられている探索方法もUCTが元になっている

マルチアームバンディット問題

nこのスロットマシンがあるとする

マシンごとに得られる賞金の期待値が異なる

得られる賞金を最大にするにはどのような戦略でコインを投入して引くレバーを選択すれば良いか

コインを投入してレバーを引くことを行動、得られる賞金を報酬、賞金の期待値を価値という

それぞれのレバーの期待値は事前には分かっていないので実際にコインを投入してレバーを引くことで期待値を予測できる

実は、理論的に最も期待値が高くなる戦略が存在する

UCB1アルゴリズムではコインを投入するたびにある式の値が最大となるレバーを選択する

UCB1の式は、期待値項 + ボーナス項という感じになっている

期待値項はそれまでに得られた報酬の期待値が大きいレバーを選択することを示し、ボーナス項はコインを投入した枚数が少ないレバーほど選択されやすくなることを示している

UCTアルゴリズム

UCB1アルゴリズムをモンテカルロ木探索のノード選択に用いた探索アルゴリズムをUCTアルゴリズムという

バンディット問題の賞金の期待値は、UCTアルゴリズムにおいてはモンテカルロ法を使ってプレイした結果の勝敗を報酬とした場合、その期待値に該当する

1 選択

ルートノードからゲーム木を未展開のノードに達するまで辿る

各ノードではUCB1アルゴリズムに従ってノードを選択する

2 展開

未展開のノードに達したら、訪問回数が閾値より大きい場合、その局面の合法手を打った後の局面を表す子ノードを追加する

3 プレイアウト

ゲーム木を辿って達した末端ノードの訪問回数が閾値以下の場合、その局面からプレイアウトを行う

4 バックアップ

プレイアウトした結果の勝敗を報酬として辿ってきたノードに報酬を加算する

このとき、各ノードの訪問回数に1を加算する

囲碁の開始局面では候補手が361手もあり、全ての手を対象とすると弱いプログラムになってしまうので、FPU、Progressiive Wideningといった手法が用いられる

モンテカルロ木探索は並列化が行いやすい

ルート並列化：並列化した各スレッドでルートノードのみノードの情報を共有する、ルートノード以外独立に探索できるためオーバーヘッドが発生しない

ツリー並列化：各スレッドのこノードの情報も共有する

排他制御を行う必要がある

ロックを防ぐためにVirtual Lossという手法がある

まとめ

モンテカルロ木探索は、確率的に勝率を求めるモンテカルロ法とゲーム木探索を巧妙に組み合わせた手法である

4章 AlphaGoの手法

モンテカルロ木探索を強くするためには主に２つの改善が必要だった

・優先順位制御の改善

・プレイアウトの質の改善

優先順位制御とは、UCTアルゴリズムのノード選択において有望な手を選択し、無駄な手を選べないように制御を行うこと

実際の対局で打たれた手に近い手の優先順位を上げるということが行われている

AlphaGo以前の強豪ソフトでは9*9の蜂の巣型のパターンが用いられている

プレイアウトの質については、プレイアウトの着手の精度を高めるためにパターンを寄付から学習するということが行われていた3*3などの小さいパターンが使用されていた

AlphaGoでは方策ネットワークと価値ネットワークというニューラルネットワークを使用することで優先順位制御とプレイアウトの質の２つの大幅に向上させた

方策ネットワーク

方策ネットワークは局面を画像として入力して、着手の確率を出力するニューラルネットワーク

画像というのは、局面を数値化した物

局面全体を入力することで対局的な判断が可能となる

AlphaGoでは方策ネットワークをモンテカルロ木探索の各ノードのノード選択の優先順位付けに使用している

方策ネットワークによる着手予測に基づいて探索を行う

ある状態でどの行動を取るかの振る舞いかたを方策という

方策は確率的に定義される

価値ネットワーク

価値ネットワークは局面を入力して、勝率を出力するネットワークである

AlphaGo以前は局面の勝率をプレイアウトの結果の平均から勝率を推測していたが、勝率はプレイアウトの質によるものであった

価値ネットワークではプレイアウトを行わず、直接勝率を予測する

価値ネットワークは、方策ネットワークを使い自己対局を行い、その勝敗結果を学習データとして学習を行う

方策ネットワークで何回もプレイアウトを行った場合と同等の確率を学習できる

実際の対局で方策ネットワークを用いてプレイアウトを行うには実行時間が問題となる

しかし価値ネットワークとして事前に学習することで対局時にすぐに方策ネットワークでプレイアウトを行った時と同等の結果を得られる

AlphaGoでは価値ネットワークの計算と並列にロールアウトポリシーと呼ぶ3*3パターンなどを使った軽量の方策を使ってプレイアウトを行った結果との平均を価値としている

AlphaGo Zeroでは価値ネットワークのみで局面を評価している

価値という用語も強化学習で使われる用語である

価値には行動価値と状態価値がある

行動価値は、ある状態で行動を選んだ場合、その行動を選んだ後に得られる報酬の期待値を表す

状態価値はある状態から将来得られる報酬の期待値

AlphaGoの探索アルゴリズム

AlphaGoではモンテカルロ木探索をもとにして方策ネットワークと価値ネットワークを活用して探索をokなう

AlphaGoの探索アルゴリズムはAPV-MCTSアルゴリズムと呼ばれている

1 選択

ルートノードから未展開のノードまで辿る

そのときに評価関数を工夫する

2 評価

末端ノードに達した場合、そのノードが未評価の場合、価値ネットワークを使用して局面を評価を行う

価値ネットワークの計算中に並列でロールアウトポリシーを使用して複数回プレイアウトを行う

3 バックアップ

評価の結果を各ノードに反映する

4 展開

末端ノードの訪問回数が閾値より大きい場合、そのノードに全ての合法手をうった後の局面を表す子ノードを追加する

AlphaGo Zeroの手法

AlphaGo Masterはプロの対局データを使用しているが、AlphaGo Zeroは自己対局のみで学習を行なっている

以下の特徴がある

・自己対極の結果を訓練データとする

・囲碁のルール以外のドメイン知識を必要としない

・プレイアウトを行わず、価値ネットワークのみで評価する

・方策ネットワークと価値ネットワークを同じネットワークで出力する

・ニューラルネットワークの構成がResNet構成

・学習の最適化手法がモーメントありSGD

AlphaGoでは入力特徴に、囲碁の知識を活用して呼吸てんやシチョウなどの特徴を入力していた

AlphaGo Zeroの入力特徴は盤面の石の配置と局面の履歴のみとなっている

AlphaGo Zeroは自らそれを発見した

ALphaZeroの登場

チェスと将棋においてもAphaGo Zeroの手法が適用できることが示された

これをAlphaZeroアルゴリズムと呼んでいる

まとめ

AlphaGoの手法を、ディープラーニングを使用することでモンテカルロ木探索の課題を克服したという視点から解説を行った

価値ネットワークによる従来のプレイアウトよりも高い精度で局面の勝率が予測できるようになった

詳しくは論文を参照

5章 ディープラーニングについて

ニューラルネットワーク

ニューラルネットワークの学習

分類問題と回帰問題

CNN

ディープラーニングの将棋AIへの応用

方策ネットワーク

寄付を訓練データとして、打ち手を予測するニューラルネットワークを学習している

画像の分類問題と同様のこと

価値ネットワーク

価値ネットワークでは局面の勝率を予測する

これは回帰問題として扱える

これを将棋に応用することを考えてみる

局面を複数のチャンネルで構成された画像として扱い、指手に一意の出力ラベルを割り当てることができれば、AlphaGoと同様にCNNで指手の予測ができそう

コマの種類それぞれにチャンネルを割り当てれば良さそう

まとめ

多層パーセプトロンとCNNの解説を行った

6章 ディープラーニングフレームワーク

ここからは３つの将棋AIを作成する

1 方策ネットワークで指手の予測のみでプレイするAI

2 価値ネットワークで一手探索を行うAI

3 方策ネットワークと価値ネットワークを使ってモンテカルロ木探索を行うAI

ディープラーニングフレームワーク

ディープラーニングを扱うプログラムでは、フレームワークを使用するのが一般的である

実装が面倒だし、GPUを利用するには計算リソースを効率的に使うための実装ノウハウが必要だから

フレームワークの選択

Chainer

TensorFlow

Keras

PyTorch

Caffe

TNCK

などがある

GPUでディープラーニングするためにCUDAやcuDNNというライブラリが提供されている

Chainerの基本

ライブラリインポート

ニューラルネットワーク定義

引数の定義

モデルインスタンス作成

最適化手法の設定

保存したモデル読み込み

データセット読み込み

学習ループ

ミニバッチ単位のループ

ミニバッチデータの準備

順伝播

勾配を初期化

損失計算

誤差逆伝播

評価

モデル保存

CPUでの実行も可能！

7章 方策ネットワーク

方策ネットワークは局面を入力として、指手を予測するニューラルネットワーク

モジュールインストール

setuptopplsを使って、スクリプトを別のスクリプトからimportできるようにPythonに登録する

そしてpip install —no-chache-dir -e .

とすることでpython-dlshogiディレクトリ内のソースをPythonモジュールとしてimportできるようになる

方策ネットワークの構成

盤上のコマは駒の種類ごとにチャンネルを分けて各チャンネルは駒の座標を表す9*9の2値画像とする

先手と後手も別のチャンネルとする

持ち駒は、種類ごとに最大枚数分のチャンネルを割り当てる

ある場合は全て1の画像とする

移動さきと移動もとの座標の組み合わせをラベル化するのはきついので、移動方向と駒の種類に分けて考える

出力ラベル数は、移動方向と移動さきの座標の組み合わせを考えて、2187

将棋の指手の予測では位置が正確である必要があるのでプーリング層は用いない

実装

コンストラクタでメンバ変数に定義するもの

1 学習するパラメータを持つ層

2 パラメータを持つ関数

コンストラクでは定義しないもの(callに定義)

1 活性化関数

2 プーリング層

3 その他

訓練データの準備

棋譜を準備する

ここではfloodgateから棋譜を使用する

python-shogi

棋譜の読み込みや局面の管理を行うためにpython用の将棋ライブラリであるpython-shogiをインストールする

共通処理の実装

方策ネットワークの学習処理の実装を行う前に学習処理から呼び出す共通処理の実装について説明する

ディープラーニングの学習に使用するデータは全てメモリに読み込むのは困難な場合、データベースなどに格納してミニバッチ単位で読み込んで使用することがある

将棋の局面はビットボードで管理すると必要なメモリ量はそれほど多くないため全てメモリに読み込んでも問題ない

python-shogiでは局面はBoardクラスで管理される

局面から入力特徴を作成する

ミニバッチにする際は(ミニバッチ、チャンネル、y座標、x座標)が次元となる

この次元で格納する形式はNCHW形式と呼ばれる

Chainerではこの形式で入力する必要がある

学習処理の実装

学習実行

8章 将棋AIの実装

本章では前章で学習した方策ネットワークを使って指してを決める将棋AIを作成する

将棋AIは、USIプロトコルに対応したUSIエンジンとして作成するのが一般的である

USIエンジンの実装

コマンドラインからテスト

GUIソフトに登録できるようにする

対局

ソフトマックス戦略

9章 学習テクニック

本章ではニューラルネットワークを学習する際に使用される学習テクニックについて述べる

ハイパーパラメータの調整

ハイパーパラメータを決めるには類似の分野のベストプラクティスを参考にするのが効率的である

最適化手法

Batch Normalization

10章 価値ネットワーク

価値ネットワークとは、局面を入力として、勝率を予測するニューラルネットワークである

本章では価値ネットワークを作成し、学習する方法について述べる

また価値ネットワークを使用して１手探索を行う将棋AIの実装について述べる

価値ネットワークの構成

価値ネットワークの実装

学習処理の実装

学習実行

１手探索のAI作成

USIエンジンに登録

対局

11章 学習テクニックその2

転移学習

マルチタスク学習

Residual Network

12章 モンテカルロ木探索

前章までに作成した将棋AIはゲーム木の探索を行っていなかった

探索をすることで誤差の影響を少なくする

ハッシュ

モンテカルロ木探索の実装

テスト

対局

並列化

13章 さらに発展させるために

C++による高速化

Aperyややねうらおうが公開されているので、利用可能である

大規模学習

終盤の課題