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 | Size | Format | |
---|---|---|---|---|
AdabaNovaAbordagem.pdf | Tese | 11.32 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.