GPU Acceleration for Board Games

This technology preview is a snapshot of some internal research we have been working on and talking about at various conferences for the past couple years. The level of interest in GPU-acceleration for board games has continued to grow, so we are making this (unsupported) snapshot available for developers who would like to experiment with the technology.

The software provided in this technology preview supports GPU accelerated game tree search of both the pruning and backtracking styles. While this technology primarily focuses on zero-sum games, the zero-sum concept is fairly broad and applicable to other domains that include economic theory, environmental study, psychological behavior, and artificial intelligence in general. The scenario, of which many thousands of users play from their mobile computer a diverse set of game boards against a remote cloud server, is an example of applications that benefits from GPU-acceleration.

Please share your experience and feedback on this GPU technology in our developer forums.

You may also be interested in GPU Accelerated Machine-Learning and Imaging and Computer Vision.

Features supported in this release:

  • Game Tree Split: parallel alpha-beta pruning search exploiting shared node bounds in global memory
  • Not-Tail, Single and Multiple Recursion: a unique runtime/user managed stack to gracefully support >1000 deep recursion
  • Zero-Sum Games: 3D Tic-Tac-Toe, Connect-4 and Reversi sample board games
  • Back Tracking Search: an exhaustive search for generating and solving Sudoku puzzles
  • Statistical Simulation: Monte Carlo Go sample, concurrently running many  thousands of random games per move

Benefits of GPU Acceleration for Board Games:

  • Faster than CPU: exploits GPU parallelism for game tree search and running many simultaneous matches, using 10s of thousands of GPU threads
  • Offload the CPU: free up CPU resources for other work
  • Flexible model: an efficient producer-consumer framework for optimally find, dispatch and resolve cut nodes
  • Widely supported: works on 100s of millions of GPUs, anything with compute capability 2.0 or later

Downloads:

GPU AI Board Games libraries and sample apps Download (Windows)
3D Tic-Tac-Toe
 Release Notes, License
Connect-4
 Release Notes, License
Reversi
 Release Notes, License
Sudoku
 Release Notes, License
Go
 Release Notes, License

Each of the four installers in the .zip file are composed of:

  • A foundation library, including header(s), lib/dll and API reference documentation
  • A sample application, executable and source code demonstrating how to use the foundation library
  • Release notes and end user license agreement

The sample applications and foundation libraries are 32-bit native, and will run on both 32-bit and 64-bit Windows systems.  The foundation libraries were built with the CUDA Toolkit 4.0 (requires R270 drivers or later) and include support for GPUs with compute capability 2.0 (sm_20) and later.

 

Recommended reading for a deeper understanding of GPU acceleration for Board Games:

  • Producer-Consumer Model for Massively Parallel Zero-Sum Games on the GPU, presentation from Intelligent Systems and Control 2011

Presentation (free PDF), Paper($27 from conference proceedings)

Presentation (free PDF), Video