著者

木村 健 小谷 善行

雑誌

第53回プログラミング・シンポジウム予稿集

巻号頁・発行日

vol.2012, pp.91-96, 2012-01-06 (Released:2012-06-20)

---

本稿ではGPGPU(グラフィックスプロセッサの汎的計算への応用)を用いた将棋ゲーム木探索手法を提案する。チェスや将棋などのゼロ和完全情報ゲームにおける並列ゲーム木探索の研究は決して新しい研究ではない。しかしながらさまざまな技術が年を経るごとに開発されているにつけ、並列探索の技術も変化を必要としている。GPU上における並列計算環境であるCUDAと、CUDAライブラリの一部であるCUDA版C++STLとも言えるThrustを用いた、並列ゲーム木探索手法を提案する。提案手法は1993年にTransputer上に実装されたYBWCをベースにしており、高いスピードアップが期待できる。ただし、CUDA固有の高スループット実現の難しさもあり、提案手法の実際の実装についての知見が必要である。 In this paper, we introduce a Shogi (Japanese Chess)’s game tree search method that uses GPGPU (General Purpose GPU). This is not new research field that parallel game tree search for zero-sum perfect information games (such as Chess and Shogi). The technology of parallel game tree search need change to fit new technology such as GPGPU. Inthispaper, we introduce the way of searching game tree in parallel which uses CUDA (Parallel environment for GPGPU) and Thrust (C++STL like CUDA based library). The proposal method is based on YBWC which implemented 1024 nodes Transputers in 1993, so high speed-up is guaranteed. But there are difficulties of implementing high throughput program in CUDA, so individual implementation and their performance findings are needed.