Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/24628
Document type: Tese
Access type: Acesso Aberto
Title: ADABA: uma nova abordagem de distribuição do Alfa-Beta - aplicação ao domínio do jogo de Damas
Alternate title (s): ADABA: a new Alpha-Beta distribution approach - application to the Checkers game domain
Author: Tomaz, Lídia Bononi Paiva
First Advisor: Julia, Rita Maria da Silva
First member of the Committee: Cozman, Fábio Gagliardi
Second member of the Committee: Hubner, Jomi Fred
Third member of the Committee: Faria, Elaine Ribeiro
Fourth member of the Committee: Gabriel, Paulo Henrique Ribeiro
Summary: 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.
Keywords: 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
Area (s) of CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO::SISTEMAS DE INFORMACAO
Language: por
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Program: Programa de Pós-graduação em Ciência da Computação
Quote: 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
Document identifier: http://dx.doi.org/10.14393/ufu.te.2019.316
URI: https://repositorio.ufu.br/handle/123456789/24628
Date of defense: 17-Dec-2018
Appears in Collections:TESE - Ciência da Computação

Files in This Item:
File Description SizeFormat 
AdabaNovaAbordagem.pdfTese11.32 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.