TadaoYamaokaの日記

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

将棋でディープラーニングする その36(PUCTアルゴリズムの実装)

Ray+Rnのソースを元に、policy networkとvalue networkを使った、モンテカルロ木探索を実装しました。

実装方法

以前の日記で書いたPUCTアルゴリズム*1を実装した。

以前に考察したように、将棋ではプレイアウトで終局までプレイしても精度が低いため、終局までのシミュレーションは行わず、末端ノードでバリューネットワークの値を報酬として使用した。

バリューネットワークの計算結果を待つ必要があるため、スレッドをCPUのコア数以上に実行して、並列に実行を行い、複数スレッドのpolicy networkとvalue networkの計算を同時に行うようにした。
また、policy networkとvalue networkの計算結果は、ハッシュテーブルに登録し、同じ局面で再利用するようにした。

実行結果

将棋所を使い、Lesserkaiと対局をさせた。
f:id:TadaoYamaoka:20170619000941p:plain

以前のpolicyのみのバージョンでは、中盤で評価値が反転する悪手を指すことがあったが、モンテカルロ木探索を行うことで、悪手を指すことがなくなった。
Lesserkai相手には、実行した限り、100%勝つようになった。

16スレッド、2000プレイアウトで、1手1秒程度かかる。
ハッシュにヒットしない局面では、NPSは1000程度しかでていない。

評価値は、選択した手のバリューネットワークによる報酬の平均rを、以下の式で対数スケールに変換して表示している。
\displaystyle
 -log(\frac{1}{r} - 1) \times 754.3
定数754.3は、elmoの教師データの勝率から算出した。(以前の日記参照)

GPSfishとの対局

ShogiGUIに付属するGPSfishとも対局させた。
f:id:TadaoYamaoka:20170619001753p:plain

終盤で崩れることが多く、何回か行ったが1度も勝つことができない。

評価値の傾向は、だいたい同じになっているので、バリューネットワークの精度はそれなりになっているようだ。

考察

GPSfish相手に、勝てない理由として以下のように考えている。

  • ログを見ると同じ手ばかり調べている
  • プレイアウト数が足りない
  • モデルの精度不足

強くするには、それぞれについて対策を行っていく必要がある。

同じ手を調べることが多い点については、終局までのシミュレーションを行っていないため、ランダム要素がなく探索するルートが固定されてしまっている。
各ノードで、候補手のUCBが最大の値を選択しているが、UCBの値を使って確率的に手を選択した方が、調べる局面の幅を広げることができる。

プレイアウト数が少ない点については、さらに高速化が必要になってくるが、コア数以上のスレッドで実行しているので、これ以上スレッドを増やしても逆効果になる。
コア数の多いCPUに交換すれば増やせるが、アルゴリズムでの工夫がないかもう少し検討したい。

モデルの精度不足については、現在のモデルはこれ以上学習しても精度が上がらなくなっているので、効果的な入力特徴を追加したり、層数を増やしたり、試行錯誤する必要がありそうだ。
結構根気がいる作業なので、ぼちぼち試していきたい。


まだ、強さはいまいちだが、従来の探索を使わずに、ディープラーニングのみを使って将棋を指すプログラムのベースができた。
時間制御とか細かいところの実装ができていないので、もう少しブラッシュアップしたい。
作り始めたときは少し検証してみるくらいのつもりだったが、ここまでできたので、できれば改良して大会にも出ようかと考えている。

PUCTアルゴリズムの実装を公開しまた。Ray+Rnのソースを流用しています。
github.com