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

TadaoYamaokaの日記

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

囲碁プログラムの高速化 その2(root並列化)

前回高速化した囲碁プログラムを並列化してさらに高速化した。

並列化の手法は、rootノードとその直下の枝のみ各スレッドで共有して、それから下の枝はそれぞれスレッドごとに別に実行する方法とした。

rootノードの直下の枝のプレイアウト回数、勝利数の更新はVisualC++組み込み関数のアトミック命令(_InterlockedExchangeAddと_InterlockedIncrement)を使って、スレッドセーフにした。
UCBの計算は読み込みのみなのでロックしていない。

論理コア数分の8スレッドを作成して処理したところ、19路盤での10000プレイアウトで並列化前と比べて約5.3倍速くなった。

並列化前 7343 ms
並列化後 1391 ms

十分に速くなったので、プレイアウト数を30万まで増やして、9路盤でGnuGo(デフォルトレベル10)と対戦したところ、今まで全く勝てなかったが初勝利をあげることができた。
実行時間も3.8秒くらいでまともな速度で動作している。


勝率は高くないがランダムプレイアウトのみでもGunGoに勝てることがわかり、モンテカルロ木探索の有用性が確認できた。

前回バグとりに苦労した連の集合によるボードの構成もちゃんと動いているようである。


次はプレイアウトの改良に取り組む予定。


初勝利記念の棋譜

(;FF[4]CA[UTF-8]AP[gogui-twogtp:1.4.9]SZ[9]
KM[6.5]PB[GoSample]PW[GNU Go]DT[2016-04-24]
C[Black command: H:\\src\\GoSample2\\x64\\Release\\GoSample2.exe -gtp 300000
White command: C:\\bin\\gnugo-3.8\\gnugo.exe --mode gtp
Black version: 1.0
White version: 3.8
Result[Black\]: ?
Result[White\]: B+16.5
Host: eins
Date: April 24, 2016 3:30:44 PM JST]
;B[ee];W[cf];B[fe];W[cc];B[de];W[ce];B[cd];W[bd];B[dd];W[gc]
;B[ge];W[eb];B[dc];W[cb];B[db];W[ec];B[da];W[hd];B[he];W[hb]
;B[dg];W[cg];B[df];W[ch];B[dh];W[di];B[be];W[bc];B[id];W[ic]
;B[gd];W[ie];B[bf];W[ei];B[bg];W[bh];B[ah];W[fg];B[ci];W[bi]
;B[eh];W[if];B[fi];W[ae];B[ci];W[di];B[gb];W[hf];B[fc];W[fb]
;B[hc];W[ca];B[gc];W[af];B[hh];W[ci];B[fh];W[ag];B[gh];W[ei]
;B[ed];W[];B[ga];W[];B[])


github.com