読者です 読者をやめる 読者になる 読者になる

TadaoYamaokaの日記

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

【囲碁プログラム】 プレイアウトにパターン適用

昨日は第26回世界コンピュータ将棋選手権を中継で観ていました。
コンピュータ将棋はまだまだ進化しているようで熱くなりますね。
チェスのStockfishの技術が将棋にも応用されているみたいです。

さて、AlphaGoとイセドルの対局を観てから作り始めた囲碁プログラムですが、どこを着地点にするか決めずにとりあえず続けています。
DCNNを実際に使って理解を深めたいというのが作り始めた理由でしたが、高速化とか強さにもこだわり始めています。
それなりに強くなったらどっかの大会にも出てみたいです。


前回プロの棋譜から学習したrollout policyをプレイアウト時に適用してみました。
プレイアウトの各手番で、すべての合法手に対して単純にパターンにマッチするかチェックしたところ、アタリを調べるだけのプレイアウトと比較して、処理速度が33倍も低下してしまった。

アタリを調べるだけ 1156 ms
パターン適用 38484 ms

19路、10000プレイアウトの1手目の処理時間

候補手を生成する際に、合法かチェックを行わないようにしたところ、15688 msまで改善した。(元から13倍)

確率に応じて手を選ぶ際に、ランダム値がそれまで調べた確率の合計以下かをループで調べているが、調べる順番をあらかじめ確率が高い順にソートしてみたが、これはかえって遅くなってしまった。ソートは要素数が多くないので、挿入ソートで行ったが、それでもオーバーヘッドが大きかったようである。

次に、直前の手から変更がなかった箇所は、再度パターンマッチを行う必要がないので、更新しないようにした。
ボードを更新する際に、変更した連を記録しておき、変更した連の周囲2目分のみを更新対象とすることで実現した。
これにより、5375 msまで改善した。(元から4.6倍)


パターン適用が有効に働いているか、GnuGoと9路で対戦させて確認してみた。

アタリを助けるだけのプレイアウトでは、GnuGoに勝つために30万プレイアウトくらい必要だったが、パターンを適用すると7万プレイアウトでGnuGoに勝つことができた。(ただし、勝率は低い。)
パターンを適用しない場合、7万プレイアウトでは全く勝てなかったので効果はでているようだ。
しかし、その分処理時間が増えているので現時点では有効とは言えない。
さらに高速化の工夫が必要そうである。


AlphaGoでは、MCTSのツリーの初期値にもrollout policy+αを使っているので、次はそちらを実装してみるつもり。

また学習時に、正則化を行っていないので、過学習している可能性がある。
正則化した場合に学習結果がどう変わるかも検証してみるつもり。

github.com