Avi Bleiweiss
Game theory, Zero-Sum, Heuristic search, Statistical simulations, GPU computing
Over more than two decades, several parallel approaches to game tree searches have emerged to specifically address single problem instances of exponential running time. Yet their execution is limited on a relatively small set of processing elements. Still, the challenge of effective massive parallelism in heuristic based search remains largely uncontested. While the dynamics of the search are quite complex, our study remarkably devises a scalable, parallel model that balances the rapid node expansion of the tree with the number of active threads, allowed to run on the GPU. In this paper, we discuss our challenges and an implementation that optimizes communication amongst many thousands of threads. We present an evaluation of our approach on a range of Zero-Sum games that employ both the Alpha-Beta algorithm and a Monte Carlo technique. Our research investigates both the efficiency of a single game tree split and the behavior of running a large set of simultaneous matches. The results indicate that our GPU based search scales well with the complexity of the game, consistently of an average move time of under 0.5 seconds.
Important Links:
Go Back
