ADABA: uma nova abordagem de distribuição do Alfa-Beta - aplicação ao domínio do jogo de Damas

Abstract

Within the player agent scenario, it is of vital importance that one can count on an appropriate search algorithm, capable of making adequate decisions, in a satisfactory interval, within a competitive setting, in which adversaries try to minimize their outcome. Alpha-Beta trees essentially make up the majority of the current algorithms used today for decision-making in such scenarios, where the quality of the solution tends to improve as the depth elevation of these trees increases. Such a fact has served as the motivation behind research efforts that aim at proposing distributed versions of Alpha-Beta, which improve the performance of the serial algorithm, in such a way as to allow for the exploration of deeper levels of the search tree. Among such versions, the APHID (Asynchronous Parallel Hierarchical Iterative Deepening) is highlighted, which itself is a master-slave model that holds as its main advantages the adaptability to operate in distributed and shared memory architectures, as well as providing a reduction in communication and synchronization overheads, when compared to other distributed versions of Alpha-Beta. In spite of these contributions, APHID presents notorious weaknesses regarding the policies of: updating the Alpha-Beta window of the slave processors; execution priorities of tasks to be executed by these selfsame processors; and \textit{thread} is the only one allocated to the master processor for dealing with results returned by the slaves. In this context, the present study has as its main goals: inspired on APHID, the proposal of a new distributed asynchronous version of the Alpha-Beta – denominated as ADABA (Asynchronous Distributed Alpha-Beta Algorithm) - that combats the weaknesses of the original distributed algorithm; while, making available a tool for the evaluation of the proposed algorithm as its main objective; and implement a multiagent Checkers player system, denominated D-MA-Draughts, whose search process it conducts. The results from the experiments, evaluated in a distributed memory architecture, corroborate the improved performance provided by ADABA, even in terms of victory rates.