NDLI: A Node-based Parallel Game Tree Algorithm Using GPUs

Content Provider	IEEE Xplore Digital Library
Author	Liang Li Hong Liu Peiyu Liu Taoying Liu Wei Li Hao Wang
Copyright Year	2012
Abstract	Game tree search is a classical problem in the field of game theory and artificial intelligence. Fast game tree algorithm is critical for computer games asking for real-time responses. In this paper, we focus on how to leverage massive parallelism capabilities of GPUs to accelerate the speed of game tree algorithms and propose a concise and general parallel game tree algorithm on GPUs. The performance model of the algorithm is presented and analyzed theoretically. We also implement the algorithm for a real computer game called Connect6 and use it to verify the effectiveness and efficiency of our algorithm. Experiments support our theoretical results and show good performance of our approach. Compared to classical CPU-based game tree algorithms, our algorithm can achieve speedup of 70.8 in case of no pruning. When pruning is considered (which means the practical performance of our algorithm), the speedup can reach about 7.0. The insight of our work is that using GPUs is a feasible way to improve the performance of game tree algorithms.
Starting Page	18
Ending Page	26
File Size	294628
Page Count	9
File Format	PDF
ISBN	9781467324229
e-ISBN	9780769548074
DOI	10.1109/CLUSTER.2012.45
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-09-24
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Games Graphics processing unit Algorithm design and analysis Parallel processing Computers Computer architecture Search problems CUDA parallel search GPGPU game tree alpha-beta pruning Conect6
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Parallel Algorithm for Game Tree Search Using GPGPU

Enhanced parallel NegaMax tree search algorithm on GPU

Acceleration of game tree search using GPGPU

GpuWars: Design and Implementation of a GPGPU Game

GPGPU-based data parallel region growing algorithm for cell nuclei detection

A New Parallel Schema for Branch-and-Bound Algorithms Using GPGPU

High performance computing and simulations on the GPU using CUDA

Parallel alpha-beta algorithm on the GPU

Implementation of Parallel Game Tree Search on a SIMD System

A Node-based Parallel Game Tree Algorithm Using GPUs

Similar Documents

A Parallel Algorithm for Game Tree Search Using GPGPU

Enhanced parallel NegaMax tree search algorithm on GPU

Acceleration of game tree search using GPGPU

GpuWars: Design and Implementation of a GPGPU Game

GPGPU-based data parallel region growing algorithm for cell nuclei detection

A New Parallel Schema for Branch-and-Bound Algorithms Using GPGPU

High performance computing and simulations on the GPU using CUDA

Parallel alpha-beta algorithm on the GPU

Implementation of Parallel Game Tree Search on a SIMD System

A Node-based Parallel Game Tree Algorithm Using GPUs