FenixEdu™

Dissertação

SoC-FPGA Monte Carlo Tree Search Processor EVALUATED

Detalhes: O Monte Carlo Tree Search (MCTS) é um método de procura em árvore, em que simulações aleatórias são aplicadas com o intuito de encontrar decisões ótimas num sistema. O objetivo deste trabalho consiste na pesquisa e desenvolvimento de uma arquitetura hardware-software do MCTS numa Soc-FPGA, demonstrada em um subconjunto do jogo de xadrez, onde uma arquitetura de hardware dedicada é desenvolvida de forma a acelerar o algoritmo. O uso de funções heurísticas no MCTS é também explorado e avaliado neste trabalho. O processador dedicado hardware realiza jogadas de xadrez, por dois jogadores, a partir de uma determinada posição inicial. Este processador gera todas a jogadas, avalia-as e seleciona uma, repetindo sucessivamente as ações referidas, para os dois jogadores até que uma condição de paragem se verifique. A aplicação de heurísticas e de tabelas de finais de jogo durante as etapas de seleção, expansão e simulação do MCTS incrementou a precisão do algoritmo e reduziu o tempo de computação do MCTS. A arquitetura de hardware-software, desenvolvida e implementada numa Zynq-7010, acelerou o algoritmo até 98 vezes. Permitiu realizar todos os jogos exigidos pela etapa de simulação do MCTS e, se escalada para 10 elementos de processamento, com recurso a um método de paralelização em folha, pode atingir uma aceleração até 668 vezes.
Keywords: Xadrez, MCTS, FPGA, Simulações do MCTS em Hardware

Discussão: junho 26, 2019, 14:30