FPGA基板を用いたモンテカルロ碁の高速化(アクセラレーションと回路設計,2009年並列/分散/協調処理に関する『仙台』サマー・ワークショップ(SWoPP仙台2009))  [in Japanese] Acceleration of Monte-Carlo Go by FPGA-based Hardware  [in Japanese]

モンテカルロ碁において,プレイアウトの実行には時間がかかる.これまでFPGA上にプレイアウト回路を実装することによって高速化するという試みはなされてきたが,FPGA内の資源の使用率が非常に高く,高速なプレイアウトを実現することは難しかった.本論文では囲碁のルールに特化したプレイアウト処理の並列化アルゴリズムTLPG(Triple Line-based Playout for Go)を提案し,9路盤用および19路盤用のプレイアウト回路をFPGA内に実装した.プレイアウトの高速化を行い,シミュレータ上で9路盤において毎秒13104プレイアウト,19路盤において毎秒2055プレイアウトの実行速度であった.また実際に計算機上で実行させたGNU Goと対戦させ,FPGA上のTLPGによるプレイアウトを評価した.

In the monte-carlo simulation of Go, it takes time to run playouts. There were attempts of accelerating by implementing circuits for playout on FPGA, but it is difficult to realize high-speed playouts because of high utilization of resources in a FPGA. In this paper, we propose an algorithm, Triple Line-based Playout for Go (TLPG) to accelerate playouts for the monte-carlo tree search for computer-go game. We implemented the playout logics on FPGA for 9x9 and 19x19 boards. With the optimizations, We achieved 13104playouts/sec in 9x9 and 2055playouts/sec in 19x19 board in simulation. By making games with GNU Go on a host Computer, We evaluation the playouts of TLPG.