FPGA基板を用いたモンテカルロ碁の高速化

摘要

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[1], 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 9 × 9 and 19 × 19 boards. With the optimizations, We achieved 13104playouts/sec in 9 × 9 and 2055playouts/sec in 19 × 19 board in simulation. By making games with GNU Go on a host Computer, We evaluation the playouts of TLPG.%モンテカルロ碁において，プレイアウトの実行には時間がかかる．これまでFPGA上にプレイアウト回路を実装することによって高速化するという試みはなされてきた[1]が，FPGA内の資源の使用率が非常に高く，高速なプレイアウトを実現することは難しかった．本論文では囲碁のルールに特化したプレイアウト処理の並列化アルゴリズムTLPG（Triple Line-based Playout for Go）を提案し，9路盤用および19路盤用のプレイアウト回路をFPGA内に実装した．プレイアウトの高速化を行い，シミュレータ上で9路盤において毎秒13104プレイアウト，19路盤において毎秒2055プレイアウトの実行速度であった．また実際に計算機上で実行させたGNU Goと対戦させ，FPGA上のTLPGによるプレイアウトを評価した．