Publicação: ADABA: uma nova abordagem de distribuição do Alfa-Beta - aplicação ao domínio do jogo de Damas
Carregando...
Arquivos
Tipo do documento
Data
Direito de acesso
Coleções
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO::SISTEMAS DE INFORMACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
No cenário de agentes jogadores, é imprescindível que se conte com um apropriado algoritmo de busca apto a tomar decisões acertadas, em tempo satisfatório, em ambientes competitivos nos quais adversários tentam minimizar o êxito dos mesmos. As árvores Alfa-Beta estão na essência da maioria dos atuais algoritmos existentes para tomada de decisão em tais cenários, sendo que a qualidade da solução tende a melhorar na medida em que se eleva o nível de profundidade dessas árvores. Tal fato vem servindo de motivação para um esforço em pesquisa visando a propor versões distribuídas do Alfa-Beta que melhorem o desempenho do algoritmo serial, de forma a permitir a exploração de níveis mais profundos da árvore de busca. Dentre estas versões, destaca-se o APHID ("Asynchronous Parallel Hierarchical Iterative Deepening"), que é um modelo mestre-escravo cujas vantagens principais são a adaptabilidade para operar em arquiteturas de memória distribuída e compartilhada, bem como o fato de prover uma redução das sobrecargas de comunicação e de sincronização em comparação com outras versões distribuídas do Alfa-Beta. Apesar destas contribuições, o APHID apresenta notórias fragilidades no que diz respeito às políticas de: atualização da janela Alfa-Beta dos processadores escravos; prioridade da execução das tarefas a serem executadas por esses mesmos processadores; e "thread" única alocada ao processador mestre para tratar os resultados retornados pelos escravos. Neste contexto, o presente trabalho como metas principais: inspirado no APHID, propor uma nova versão distribuída assíncrona do Alfa-Beta - denominada ADABA ("Asynchronous Distributed Alpha-Beta Algorithm") - que combata as fragilidades do algoritmo distribuído original; e, objetivando dispor de uma ferramenta para avaliar o desempenho do algoritmo proposto, implementar um sistema multiagente jogador de Damas, denominado D-MA-Draughts, cujo processo de busca seja conduzido por ele. Os resultados dos experimentos, avaliados em arquitetura de memória distribuída, corroboram a melhoria de desempenho provida pelo ADABA, inclusive em termos de taxas de vitória.
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.
Palavras-chave
Algoritmos de busca, Search algorithms, Busca distribuída, Distributed Search, Alfa-Beta, Alpha-Beta, APHID, Computação, YBWC, Jogo de damas por computador, ADABA, Algoritmos de computador, Jogos Soma Zero, Zero-sum games, Jogadores Automáticos de Damas, Automatic Checkers players, Sistemas Multiagentes, Multiagent Systems
Citação
TOMAZ, Lídia Bononi Paiva. ADABA: uma nova abordagem de distribuição do Alfa-Beta - aplicação ao domínio do jogo de Damas. 2018. 196 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Uberlândia (Uberlândia), 2019. DOI http://dx.doi.org/10.14393/ufu.te.2019.316