Autonomous checkers robot using enhanced massive parallel game tree search
Ahmed A. Elnaggar, Mahmoud Gadallah, Mostafa Abdel Aziem, Hisham Aldeeb · 2014
The dream of building intelligent robotic systems to interact and communicate with people and help them in their lives is a very old and ongoing study. In this research, the massive parallel autonomous checkers agent "MPACA" can autonomously play checkers with a human upto Grandmaster level without requiring a special checkers board for detecting human movements. The main aim and contribution of this research is proposing enhanced algorithms for a game tree search using two different approaches. The first was a task-based approach on CPU with a parallel database, while the second was a threads-based approach on the GPU with no divergence and dynamic parallelism. The two approaches were compared with previous studies using various approaches, including threads on CPU for up to 6× speedup for an 8-core processor and threads on GPU using iterative dependence and fixed grid and block size of up to 40× speedup at 14 depth. Furthermore, the approaches were tested with different depths on the CPU and the GPU. The result shows speed up for parallel CPU tasks up to 7× for an 8-core processor and parallel GPU of up to 80× at 14 depth.