TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

強化学習の勉強

コンピュータ将棋の記事をちょっと書いたこともあり、強化学習について勉強を始めました。

教科書として用いるのは、

この本です。

この本で使用されているサンプルプログラムは、Octaveとg++が使用されいます。
Windowsで最新のOctaveとMSYS2で実行するのに少し苦労したので、実行方法を記しておきます。

環境

三目並べのコードの実行方法

Octaveのインストール

https://ftp.gnu.org/gnu/octave/windows/
から、「octave-4.2.1-w64-installer.exe」をダウンロードしてインストールする。

MSYS2のインストール

MSYS2 download | SourceForge.net
から、「msys2-x86_64-20161025.exe」をダウンロードしてインストールする。

MSYS2
の説明に従ってパッケージを最新にする。

g++インストール

スタートメニューから「MSYS2 MinGW 64bit」を起動する。

$ pacman -S mingw-w64-x86_64-toolchain
:: 17 のパッケージがグループ mingw-w64-x86_64-toolchain にあります:
:: リポジトリ mingw64
   1) mingw-w64-x86_64-binutils  2) mingw-w64-x86_64-crt-git  3) mingw-w64-x86_64-gcc  4) mingw-w64-x86_64-gcc-ada
   5) mingw-w64-x86_64-gcc-fortran  6) mingw-w64-x86_64-gcc-libgfortran  7) mingw-w64-x86_64-gcc-libs
   8) mingw-w64-x86_64-gcc-objc  9) mingw-w64-x86_64-gdb  10) mingw-w64-x86_64-headers-git
   11) mingw-w64-x86_64-libmangle-git  12) mingw-w64-x86_64-libwinpthread-git  13) mingw-w64-x86_64-make
   14) mingw-w64-x86_64-pkg-config  15) mingw-w64-x86_64-tools-git  16) mingw-w64-x86_64-winpthreads-git
   17) mingw-w64-x86_64-winstorecompat-git

選択して下さい (デフォルト=all): 1 2 3 7 9 10 11 12 13 14 15 16

makeコマンドのファイル名がmingw32-make.exeとなっているので、コマンドプロンプトでmake.exeへハードリンクを作成する。

cd /d C:\msys64\mingw64\bin
mklink /H make.exe mingw32-make.exe
FLTKのインストール

FLTKはパッケージマネージャからインストールできないので、
GitHub - msys2/MINGW-packages: Package scripts for MinGW-w64 targets to build under MSYS2.
のビルドスクリプトを使用して、自分でビルドしてインストールする。

「MSYS2 MinGW 64bit」を起動して、適当な作業ディレクトリに移動して、

$ git clone https://github.com/Alexpux/MINGW-packages.git
$ cd MINGW-packages
$ cd mingw-w64-fltk
$ MINGW_INSTALLS=mingw64 makepkg-mingw -sLf
$ pacman -U mingw-w64-x86_64-fltk*.pkg.tar.xz

三目並べサンプルプログラムのビルド

書籍に記載されているサポートページからサンプルプログラムをダウンロードして解凍する。
「MSYS2 MinGW 64bit」を起動して、解凍したディレクトリに移動して、

$ cd sanmoku
$ g++ -fpermissive sanmoku.cpp -o sanmoku.exe -lfltk

サンプルプログラムのコードは古いバージョンのg++でビルドされているためデフォルトオプションではエラーになるので「-fpermissive」オプションを付けている。

sanmoku.exeを実行すると、
f:id:TadaoYamaoka:20170415171548p:plain
このような画面が表示される。

学習の実行

学習のプログラムの実行方法は、書籍の4.9章に記載されている。

スタートメニューからOctave(GUI)を起動して、ファイルブラウザでサンプルプログラムを解凍したディレクトリの「sanmoku」ディレクトリを開く。
コマンドウィンドウで、書籍の通り入力していく。

options.pmode=2
options.epsilon=0.1
options.gamma=0.9
Q=MonteCarloPolicyIteration(10,1000,options)

このまま実行すると、大量に警告が出力されるので、以下の通り編集する。

action_train.mの49行目

if(val==2 & num==1)

if(val==2 && num==1)

に修正する。

MonteCarloPolicyIteration.mの97行目と99行目の日本語部分を

g=xlabel('games');

g=xlabel('rate');

に修正する。

Q=MonteCarloPolicyIteration(10,1000,options)

を実行すると、以下のように結果が表示され、

>> Q=MonteCarloPolicyIteration(10,1000,options)
1) Win=411/1000, Draw=83/1000, Lose=506/1000
2) Win=719/1000, Draw=63/1000, Lose=218/1000
3) Win=786/1000, Draw=45/1000, Lose=169/1000
4) Win=783/1000, Draw=61/1000, Lose=156/1000
5) Win=751/1000, Draw=50/1000, Lose=199/1000
6) Win=850/1000, Draw=38/1000, Lose=112/1000
7) Win=788/1000, Draw=36/1000, Lose=176/1000
8) Win=797/1000, Draw=29/1000, Lose=174/1000
9) Win=821/1000, Draw=52/1000, Lose=127/1000
10) Win=809/1000, Draw=26/1000, Lose=165/1000
Q =

Compressed Column Sparse (rows = 19683, cols = 9, nnz = 388 [0.22%])

  (1, 1) ->  4.9260
  (6, 2) -> -0.57000
  (12, 2) ->  3.1858
  (46, 2) ->  5.4000
  (84, 2) -> -2.6775
  (105, 2) -> -7.5000
  (129, 2) ->  5
  (748, 2) -> -6
  (781, 2) -> -5
  (831, 2) ->  6.3141
  (883, 2) -> -4.5000
  (937, 2) -> -5
  (968, 2) ->  10
  (993, 2) ->  4.0500
  (1158, 2) ->  9
  (1182, 2) ->  10
  (1245, 2) ->  4.5000
  (1344, 2) ->  20
  (1590, 2) -> -20
  (1713, 2) -> -7.5000
  (1717, 2) -> -5
  (1772, 2) -> -5
  (1806, 2) -> -10
  (1808, 2) -> -5
  (1856, 2) -> -5
  (1878, 2) ->  40
  (1896, 2) ->  12
  (1902, 2) -> -11.667
  (1906, 2) ->  10
  (1949, 2) -> -5
  (1988, 2) ->  9

グラフウィンドウが起動する。一度ウィンドウを切り替えないと描画されないので、他のウィンドウをアクティブにしてからグラフのウィンドウをアクティブにする。
f:id:TadaoYamaoka:20170415172533p:plain

対戦の実行

学習した関数を使用して対戦を実行できるが、Octaveで改行コードがCrLfだと、state.txtが正しく読めない。
observe_test.mの19行目を以下の通り編集する。

    [tok,rem]=strtok(rem,":\r\n");
    if (length(tok) == 0)
      break;
    endif

これで、書籍に記載している通りの実行方法で対戦ができる。

test(Q,options)

f:id:TadaoYamaoka:20170415182527p:plain

将棋でディープラーニングする その3(棋譜から学習)

プロの棋譜を使って前回の日記で作成したニューラルネットワークの学習を行った。

棋譜サイトにあった竜王戦棋譜を使用した。

訓練データとテストデータの数は以下の通り。

訓練データ テストデータ
局数 3744 417
局面数 422852 47242

学習には非常に時間がかかるため、学習が進んでいることが確認できたら途中で打ち切ることにした。

はじめ最適化手法をAdamで行ったが学習が進まないので、AdaGradにしたところ学習が進むことを確認できた。
ミニバッチサイズを8として、1ミニバッチサイズの学習を1イテレーションとして、32500イテレーション学習した結果は以下の通り。
f:id:TadaoYamaoka:20170410204331p:plain
accuracyは100イテレーションごとに、テストデータからランダムに抽出した64サンプルで評価している。

グラフを見ると、lossは順調に下がっている。
accuracyは、0.15程度まで上昇しており、15%の精度でプロの指し手を予測している。

lossはまだ下がりそうなのでこのまま学習を進めれば予測精度は上がっていくと思われる。

lossが下がらなくなるまで学習を進めないとはっきりしたことは言えないが、将棋でもディープラーニングを使用して指し手の予測ができそうである。

学習に使用したソースをGitHubに公開した。
github.com

次は、特徴に手番や王手、2歩などを追加した場合に精度が上がるか比較してみたい。

追記

3エポック(158500イテレーション)学習した結果、accuracyは0.21程度まで上昇した。
f:id:TadaoYamaoka:20170410221308p:plain

実行時間は、GeForce1080で35分かかった。

追記2

後手番のときに盤を回転しないで学習していたので、180度回転して学習するようにしたところ、accuracyが0.25くらいまで上がった。
f:id:TadaoYamaoka:20170410234225p:plain

将棋でディープラーニングする その2(ニューラルネットワークの構成)

先日の日記に続き、将棋でのディープラーニングの実装を試す。

今回は、ニューラルネットワークの構成を検討する。

ネットワーク構成

ネットワーク構成は、AlphaGoのネットワーク構成を参考にし、13層の畳み込みニューラルネットワーク(DCNN)とする。
位置について精度が要求されるため、プーリング層は使用しない。

入力特徴

9×9の2値画像を特徴数の枚数分入力する。
特徴は以下の通りとする。

特徴 枚数
自プレイヤーの駒の配置 14
自プレイヤーの持ち駒 38
相手プレイヤーの駒の配置 14
相手プレイヤーの持ち駒 38
空の配置 1

持ち駒は、駒ごとに1枚を割り当て、持ち駒の最大枚数分を割り当てる。
持ち駒がある場合は、すべて1の画像とし、持ち駒がない場合はすべて0の画像とする。

入力特徴数の合計は、105枚となる。

他にも、手番や王手かどうか、2歩の位置なども入力特徴とした方が精度があがると思われるが、一旦最低限の特徴のみで検証を行いたい。

出力

指し手の確率を出力する。
指し手は合法手を絞らず、駒ごとの座標に一つのラベルを割り当て、多クラス分類問題として扱う。
どの駒を移動したかは考慮しない。
ラベル数は、駒の種類が14なので、14×9×9=1134となる。

Chainerでの実装

以上のように設計したネットワーク構成、入力特徴、出力をChainerで実装すると以下のようになる。

import chainer
from chainer import Chain
import chainer.functions as F
import chainer.links as L

import shogi

k = 256
class MyChain(Chain):
    def __init__(self):
        super(MyChain, self).__init__(
            l1=L.Convolution2D(in_channels = None, out_channels = k, ksize = 3, pad = 1),
            l2=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l3=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l4=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l5=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l6=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l7=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l8=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l9=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l10=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l11=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l12=L.Convolution2D(in_channels = k, out_channels = k, ksize = 3, pad = 1),
            l13=L.Convolution2D(in_channels = k, out_channels = len(shogi.PIECE_TYPES), ksize = 1, nobias = True),
            l13_2=L.Bias(shape=(9*9*len(shogi.PIECE_TYPES)))
        )

    def __call__(self, x):
        h1 = F.relu(self.l1(x))
        h2 = F.relu(self.l2(h1))
        h3 = F.relu(self.l3(h2))
        h4 = F.relu(self.l4(h3))
        h5 = F.relu(self.l5(h4))
        h6 = F.relu(self.l6(h5))
        h7 = F.relu(self.l7(h6))
        h8 = F.relu(self.l8(h7))
        h9 = F.relu(self.l9(h8))
        h10 = F.relu(self.l10(h9))
        h11 = F.relu(self.l11(h10))
        h12 = F.relu(self.l12(h11))
        h13 = self.l13(h12)
        return self.l13_2(F.reshape(h13, (len(h13.data), 9*9*len(shogi.PIECE_TYPES))))

フィルター枚数は、AlphaGoでは192だが、将棋は駒の種類が多いため一旦256とした。
フィルター枚数などのハイパーパラメータは実験により調整が必要である。

次回、作成したニューラルネットワークを使用して、棋譜から学習を行う予定。

将棋でディープラーニングする

先日の日記で1行もコードを書かずに、将棋におけるディープラーニングについて考察した。

コードを書いて実験しないとただの机上の空論になるのでコードを書いて検証してみたいと思う。
といっても、将棋のプログラムの実装は行ったことがない。
一からコードを書くのはしんどいので、とりあえず使えるライブラリを探して使用していきたいと思う。

python-shogiのインストール

Pythonディープラーニングフレームワークを使用したいので、Pythonで扱えるライブラリがよい。
Python向けの将棋のライブラリとして、python-shogiが見つかった。
pypi.python.org

pipからインストールが可能になっている。

pip install python-shogi

でインストールできる。

しかし、Windowsでインストールしようとすると、

UnicodeDecodeError: 'cp932' codec can't decode byte 0x81 in position 2239: illegal multibyte sequence

というエラーが表示されて、インストールできなかった。

GitHubからリポジトリをクローンしてきて、setup.pyの25行目を以下の通り編集(「, encoding='utf-8'」を追加)し、

  description = open(os.path.join(os.path.dirname(__file__), 'README.rst'), encoding='utf-8').read()
pip install --no-cache-dir -e .

でインストールした。
GitHubにプルリクエストを送ったので、そのうち修正してもらえるかもしれない。(※2017/4/9 マージしていただきました。)

棋譜スクレイピング

棋譜サイトから棋譜のデータをスクレイピングして集める。
使用した棋譜サイトは、直リンクでは棋譜がダウンロードできず、ボタンクリックをしてCSA形式で棋譜データが表示できるようになっていたので、SeleniumとPhantomJSを使用して棋譜データを抽出した。

from selenium import webdriver
driver = webdriver.PhantomJS(executable_path='C:/bin/phantomjs-2.1.1-windows/bin/phantomjs.exe')

driver.get('https://xxxxxxx')
driver.implicitly_wait(10)
csa_export = driver.find_element_by_id('xxxxx')
csa_export.click()
csa_txt = driver.find_element_by_css_selector('xxxx').text

このような感じに記述することで取得できる。

棋譜の再生

取得したCSA形式の文字列を、python-shogiで再生する。

import shogi
import shogi.CSA

kifu = shogi.CSA.Parser.parse_str(csa_txt)[0]
moves = kifu['moves']

board = shogi.Board()
board.push_usi(moves[0])
board.push_usi(moves[1])
board.push_usi(moves[2])
...

盤の駒は以下のようにして取得する。

board.piece_at(shogi.I4)

持ち駒は以下のようにして取得する。

hand = board.pieces_in_hand
hand_b = hand[shogi.BLACK] # 先手
for p in hand_b.keys():
    print("piece: {0}, num: {1}".format(shogi.Piece(p, shogi.BLACK).symbol(), hand_b[p]))

以上のようにして、教師データの準備ができる。

本日はここまで。
次回、方策のニューラルネットワークを記述する予定。

コンピュータ将棋におけるディープラーニングの考察

先日の日記で、コンピュータ将棋とAlphaGoについて言及したが、次のPonanzaがディープラーニングに成功したということで、どのように適用しているのかが気になっている。

そこで適当に考察してみる。

電王戦のインタビューでもプロの棋譜との一致率について言及していたことから、学習しているのは評価関数ではなく方策(policy)であると思われる。

入力に盤面の情報を与えて、出力に指し手の確率を出力する関数である。

入力

ポイントとなるのが、入力の盤面の情報の与え方であると思う。

AlphaGoでは19×19の各座標の白石、黒石、空きで3チャンネル(2値)の情報と、アタリやシチョウなどの若干の囲碁の知識を特徴量として各チャンネルに割り当て、合計で48チャンネルのデータを入力としていた。

将棋では、駒の種類が多いため、成りを含めた14種類のコマ数分のチャンネルが必要になる。
また、持ち駒もあるため、9×9の座標の他に、持ち駒の表現が必要になる。

畳み込みでは、位置の情報が重要であるため、なんらかの方法で位置に対してノイズとならないように入力してあげる必要がある。

また、AlphaGoでは盤面の情報の他にアタリやシチョウの場所なども与えているので、将棋の知識から2歩の場所などは与えた方がよさそうである。

出力

出力は、AlphaGoでは石を置く場所を表す19×19の1チャンネルで良かったが、将棋では座標の他に、どの駒が移動するか、成るのか、持ち駒から指すのかという情報が必要になる。

インタビューで、ルールを教えなくても正しい結果がでるようになったと言っていたので、移動については考慮せず、座標と駒のみを出力して、どこから移動したかは後からロジックで見つけているのかもしれない。
その場合、移動元が一意に決まらないケースがたまにあるという問題がある。

移動元と移動先の座標をそれぞれのチャンネルとして出力しているのかもしれない。

ネットワーク構成

ニューラルネットワークの構成は、AlphaGoではプーリングなしの13層の畳み込みニューラルネットワークだったが、似たような構成でよいかもしれない。

学習

以上の入力と出力、ネットワーク構成の設計ができたら、AlphaGoと同様にプロの棋譜から指し手を教師データとして誤差逆伝播で行うことができる。
AlphaGoのSL policy networkでは50GPUで3週間かかっているので、おそらく収束にはかなりの計算リソースが必要になると思われる。

方策改善

AlphaGoのRL policy networkと同様の方法で、自己対戦により強化学習の手法で、方策改善を行うことができる。

AlphGoの論文では以下の論文が引用されている。
Williams, R. J. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8, 229–256 (1992).

この論文で提案されているのは、REINFORCEアルゴリズムという、関数近似手法を使い強化学習を一般化したものである。

価値関数の学習

AlphaGoのValue networkと同様の方法で、方策から価値関数を学習することができる。

大量の異なる局面からRL policy networkの方策に従い最後までプレイしたときの報酬から、価値関数を回帰により学習する。

対戦時の方法

AlphaGoでは、モンテカルロ木探索の着手予測にSL policy networkを使い、プレイアウトの結果とValue networkの結果の平均をとることで、うまく従来の手法と組み合わせている。
ディープラーニングでは読みの部分で弱点があるので、プレイアウトで補っているものと思われる。

将棋は、囲碁以上に読みが重要なゲームであるため、ディープラーニングのみで指しても強くないと思われる。
探索とうまく組み合わせる必要がある。

先日の日記で書いたように、従来の探索を使用し、学習した方策を枝刈りに使用し、学習した価値関数を探索の末端の評価関数に使用することでディープラーニングを従来の探索と組み合わせて使えると思う。

以上、1行もコードを書かずに勝手に考察してみました。

PonanzaもAlphaGoのように論文を書いてくれることを期待してます。

そうしたら来年のコンピュータ将棋はディープラーニング一色に染まりそうですね。

追記

上で書いた内容は、専門家でない私の勝手な考察なので、おそらく全くの的外れです。
あまり参考にしないでください。

チェスでの先行研究の情報を追記しておきます。

チェスでのディープラーニングの実装があるようです。
Deep learning for... chess · Erik Bernhardsson
これは、方策ではなく評価関数を学習しています。

この論文では、評価関数と実現確率を学習しているようです。363個の特徴を入力しており、入力特徴の設計の参考になるかもしれません。
[1509.01549] Giraffe: Using Deep Reinforcement Learning to Play Chess

このサイトで研究がまとめられています。
https://chessprogramming.wikispaces.com/Deep+Learning

追記その2

後日、実際に実装して試してみました。
将棋でディープラーニングする - TadaoYamaokaの開発日記
将棋でディープラーニングする その2(ニューラルネットワークの構成) - TadaoYamaokaの開発日記
将棋でディープラーニングする その3(棋譜から学習) - TadaoYamaokaの開発日記
将棋でディープラーニングする その4(ネットワーク構成の変更) - TadaoYamaokaの開発日記
将棋でディープラーニングする その5(入力特徴に手番を追加) - TadaoYamaokaの開発日記
将棋でディープラーニングする その6(BatchNormalizationを追加) - TadaoYamaokaの開発日記
将棋でディープラーニングする その7(最適化手法の変更) - TadaoYamaokaの開発日記
将棋でディープラーニングする その8(出力に移動元を追加) - TadaoYamaokaの開発日記
将棋でディープラーニングする その9(王手を入力特徴に追加) - TadaoYamaokaの開発日記
将棋でディープラーニングする その10(入力特徴から盤面の空の位置を削除) - TadaoYamaokaの開発日記
将棋でディープラーニングする その11(Kerasの実装) - TadaoYamaokaの開発日記
将棋でディープラーニングする その12(Wide ResNetを試す) - TadaoYamaokaの開発日記
将棋でディープラーニングする その13(ハイパーパラメータの調整) - TadaoYamaokaの開発日記
将棋でディープラーニングする その14(floodgateの棋譜で学習) - TadaoYamaokaの開発日記
将棋でディープラーニングする その15(強化学習) - TadaoYamaokaの開発日記
将棋でディープラーニングする その16(対局できるようにする) - TadaoYamaokaの開発日記
将棋でディープラーニングする その17(強化学習の実装) - TadaoYamaokaの開発日記
将棋でディープラーニングする その18(報酬に応じた勾配) - TadaoYamaokaの開発日記
将棋でディープラーニングする その19(報酬に応じた勾配 その2) - TadaoYamaokaの開発日記
将棋でディープラーニングする その20(バリューネットワーク) - TadaoYamaokaの開発日記
将棋でディープラーニングする その21(elmoの学習データ) - TadaoYamaokaの開発日記
将棋でディープラーニングする その22(評価値と勝率の関係) - TadaoYamaokaの開発日記
将棋でディープラーニングする その23(バリューネットワークの実装) - TadaoYamaokaの開発日記
将棋でディープラーニングする その24(歩の持ち駒の上限) - TadaoYamaokaの開発日記
将棋でディープラーニングする その25(C++でミニバッチ作成) - TadaoYamaokaの開発日記
将棋でディープラーニングする その26(学習の高速化) - TadaoYamaokaの開発日記
将棋でディープラーニングする その27(対局できるようにする) - TadaoYamaokaの開発日記
将棋でディープラーニングする その28(学習の高速化その2) - TadaoYamaokaの開発日記
将棋でディープラーニングする その29(強化学習【修正版】) - TadaoYamaokaの開発日記
将棋でディープラーニングする その30(探索アルゴリズム) - TadaoYamaokaの開発日記
将棋でディープラーニングする その31(DNNのスループット) - TadaoYamaokaの開発日記
将棋でディープラーニングする その32(転移学習) - TadaoYamaokaの開発日記
将棋でディープラーニングする その33(マルチタスク学習) - TadaoYamaokaの開発日記
将棋でディープラーニングする その34(強化学習【成功】) - TadaoYamaokaの開発日記
将棋でディープラーニングする その35(マルチタスク学習(補足)) - TadaoYamaokaの開発日記
将棋でディープラーニングする その36(PUCTアルゴリズムの実装) - TadaoYamaokaの開発日記
将棋でディープラーニングする その37(利き数を入力特徴に追加) - TadaoYamaokaの開発日記
将棋でディープラーニングする その38(学習継続中) - TadaoYamaokaの開発日記
将棋でディープラーニングする その39(ブートストラップ) - TadaoYamaokaの開発日記
将棋でディープラーニングする その40(入力特徴に履歴追加) - TadaoYamaokaの開発日記
将棋でディープラーニングする その41(モーメントありSGD) - TadaoYamaokaの開発日記
将棋でディープラーニングする その42(ValueNetの出力をtanhにする) - TadaoYamaokaの開発日記
将棋でディープラーニングする その43(ValueNetの出力をtanhにする2) - TadaoYamaokaの開発日記
将棋でディープラーニングする その44(L2正則化) - TadaoYamaokaの開発日記
将棋でディープラーニングする その45(高速化) - TadaoYamaokaの開発日記
将棋でディープラーニングする その46(出力ラベルの表現方法) - TadaoYamaokaの開発日記
将棋でディープラーニングする その47(全結合) - TadaoYamaokaの開発日記
将棋でディープラーニングする その48(ResNet) - TadaoYamaokaの開発日記
将棋でディープラーニングする その49(再学習) - TadaoYamaokaの開発日記
将棋でディープラーニングする その50(ブートストラップ【訂正】) - TadaoYamaokaの開発日記
将棋でディープラーニングする その51(ディリクレノイズ) - TadaoYamaokaの開発日記
将棋でディープラーニングする その52(自己対局で教師局面生成) - TadaoYamaokaの開発日記

Bonanzaメソッドの解説

昨日、電王戦 Ponanza×佐藤天彦名人の第1局をニコニコ生放送で見ていました。

コンピュータ将棋には以前より興味があり、初めの頃から電王戦はウォッチしていました。

名人に勝ったPonanzaは、次はディープラーニングを使うということですが、昨日の対戦で使われたバージョンは、探索はミニマックス法の改良で、評価関数を機械学習で最適化するという方法で作られています。

ミニマックス法の並列化や高速化は、チェスのプログラムで昔から改良され続けてきました。
将棋プログラムでも基本は同じでありコンピュータ将棋での技術的な進歩はそれほどなかったと思います。

評価関数については、2006年のBonanzaの登場以前は、プログラマーがロジックを組んで調整していたものが、Bonanzaが3駒関係の特徴量の線形和をプロの棋譜から機械学習したことでブレイクスルーが起きました。

Bonanza登場以降は、ほぼすべての将棋プログラムがBonanzaの改良となっています。

Ponanzaは、他の将棋プログラムの一歩先を行っており、評価関数の学習に、プロの棋譜を使用しないで、自己対戦の結果を使って強化学習を行っているようです。

Bonanzaが取り入れた、評価関数の機械学習が今の将棋プログラムの重要な要素となっています。

ここでは、Bonanzaで行っている機械学習の方法(通称Bonanzaメソッド)について解説します。

Bonanzaメソッド

学習する局面の集合を{\bf P}、特徴ベクトルを{\bf v}、局面pの合法手数をM_p棋譜で選択された子局面をp_1、m番目の合法手による子局面をp_mとすると、

目的関数J({\bf P}, {\bf v})を、以下のように設計する。

\displaystyle
J({\bf P}, {\bf v}) = \sum_{p \in {\bf P}} \sum_{m=2}^{M_p} T_p[\xi(p_m, {\bf v}) - \xi(p_1, {\bf v})]

ここで、\xi(p_m, {\bf v})は、Minimax探索の値である。
T_p(x)は損失関数で、局面pの手番がMaxプレイヤーの場合、T_p(x)=T(+x)、Minプレイヤーの場合、T_p(x)=T(-x)となる。
T(x)は、一価の単調増加関数であればよく、Bonanzaではシグモイド関数

\displaystyle
1/(1+e^{-0.0273x})

が使われている。

勾配法を使用して、目的関数を最小化するように特徴ベクトル{\bf v}を学習する。

解説

プロの棋譜で選ばれた手の正しい評価値が分かるわけではないので、直接評価関数を学習することができない。
そこで、現在の評価関数を使用して、プロの棋譜で選ばれた局面の評価値と、それ以外の局面の評価値の差の合計を損失関数T(x)としている。

プロの棋譜と違う手を選択した場合、その評価値を低く見積もった場合ほど、損失関数の値は大きくなる。

全局面分について損失関数を計算した合計が目的関数となっている。

損失関数を微分可能な関数にすることで、勾配法を用いて、特徴ベクトル{\bf v}を最適化できる。

勾配法は、目的関数をv_iについて偏微分を行う。

\displaystyle
\frac{\partial J({\bf P}, {\bf v})}{\partial v_i} = \sum_{p \in {\bf P}} \sum_{m=2}^{M_p} \frac{d T_p(x)}{dx}[\frac{\partial \xi(p_m, {\bf v})}{\partial v_i} - \frac{\partial \xi(p_1, {\bf v})}{\partial v_i}]

各パラメータv_iについて、偏微分の値に、学習率を掛けてパラメータを更新する。

上記式で、T_p(x)v_iについての偏微分は、合成関数の微分の法則

\displaystyle
y=f(x), x=g({\bf v})
のとき、\displaystyle
\frac{\partial y}{\partial v_i}=\frac{d f}{d x} \frac{\partial g}{\partial v_i}

を使用している。

\xi(p_m, {\bf v})微分は、探索結果の末端局面の評価関数の微分で代替する。
末端局面の評価関数は3駒関係の線形和であるため、微分可能である。

Bonanzaでは収束性をよくするために、束縛条件(持ち駒の評価値の合計を一定)と、L1正則化項を目的関数に加えている。

目的関数が全局面の損失関数の合計となっていることからわかるように、バッチ学習を行っている。

当時のコンピュータで、45833局の学習で、約1ヶ月かかっているようである。
2009-11-30

この部分は、ミニバッチにすることで、より収束が速くなると思われる。

おまけ

私は、以前にコンピュータ囲碁のAlphaGoのクローンを途中まで作成したことがある。
その際に、rollout policyをプロの棋譜から機械学習を行った。
rollout policyで学習するのはどの手を選択するかの方策であるため、出力をsoftmax関数とすることで、プロの棋譜で選択された手から直接学習を行うことができた。

また、AlphaGoのRL policy networkでも行われているように、強化学習の手法で方策を改善でき、Value Networkで方策から価値関数(評価関数)を学習できる。

学習した方策を枝刈りに使用し、学習した評価関数を探索の末端の評価関数に使用することで、もしかしたらAlphaGoの手法はコンピュータ将棋にも応用できるかもしれない。
その場合、方策で使用する関数が3駒関係でも有効なのかは試してないのでわからない。

3Dモデルから学習データを生成する その3(顔の向きを変える)

前回に続きBlenderで読み込んだ初音ミクMMDモデルを使って、マンガキャラクターの顔パーツ検出用学習データの生成を試みる。

前回は、トゥーンレンダリングを使用して3Dモデルからマンガ風の画像を生成した。
今回は、学習データのバリエーションを増やすため、3Dモデルの顔の向きを変えることを試みる。

Blenderで顔の向きを変えるには、ボーンを操作してポーズを付ける。

ボーンの操作

顔の向きを変えるため、首のボーンを回転させる。

デフォルトレイアウトの画面右上のOutliner領域から
Scene→初音ミク初音ミク_arm→Pose→センター→上半身→首
をクリックする。

f:id:TadaoYamaoka:20170402220122p:plain

TransformのRotation Modeを「XYZ Euler」に変更し、RotationのYの値を「30°」に設定する。

f:id:TadaoYamaoka:20170402220309p:plain

Pythonのコードでは以下のように記述する。

bpy.data.objects['初音ミク_arm'].pose.bones['首'].rotation_mode = 'XYZ'
bpy.data.objects['初音ミク_arm'].pose.bones['首'].rotation_euler.y = radians(30)

レンダリングを行うと以下のようになる。
f:id:TadaoYamaoka:20170402220611p:plain

顔の向きを変えることができた。

同様の方法で、上下を含めて顔の向きをランダムに変更することで、学習データを生成できる。

次回は、3Dモデル上の顔のランドマーク位置からスクリーン上での座標を計算で求める予定。