APHID-Draughts: Comparing the Synchronous and Asynchronous Parallelism Approaches for the Alpha-Beta Algorithm Applied to Checkers

This paper has two main goals. Its first purpose is to create, in a distributed memory architecture, the Checkers agent APHID-Draughts, which is a player system designed to operate in a high performance environment. This system counts on an unsupervised learning process, where the decisions are made by means of distributed asynchronous version of the alpha-beta algorithm, known as APHID (Asynchronous Parallel Hierarchical Iterative Deepening). The second goal of this paper is to compare the performance in distributed memory architectures between unsupervised player agents operating according to one of the following alpha-beta parallelism approaches: asynchronous or synchronous. This second goal is performed through tournaments in which the agent APHID-Draughts proposed herein faces off with D-VisionDraughts, a Checkers player agent operating with the synchronous distributed version of alpha-beta known as YBWC (Young Brothers Wait Concept). Noteworthy here is that APHID-Draughts and D-VisionDraughts both consist of Multilayer Perceptron Neural Networks that learn through Temporal Difference Methods TD(λ). Thus, the only difference between these agents refers to the decision-making strategy, since the former uses the asynchronous algorithm APHID and the latter uses the synchronous version YBWC. The results obtained confirm the theoretically expected assumption that asynchronous approaches are more suitable for operating in distributed memory architectures than those of a synchronous nature.