FenixEdu™

Dissertação

{en_GB=SoC-FPGA Monte Carlo Tree Search Processor} {} EVALUATED

Detalhes: {pt=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. , en=Monte Carlo Tree Search (MCTS) is a search method that combines a tree search with random simulations in order to find optimal decisions in a system. The objective of this work was to research and develop a hardware-software architecture in a Soc-FPGA for MCTS, applied to a subset of chess, where a dedicated hardware architecture was designed to accelerate the algorithm simulations. The use of specific heuristic functions on MCTS was also explored and evaluated. The dedicated hardware processor plays a Chess end game from a given starting position. This processor generates all moves, evaluates them, selects one for the side-to-move and successively repeats these actions until a stop condition is verified. Chess specific heuristics and 4-piece endgame tables in the selection, expansion and simulation stage of MCTS were used to improve the algorithm accuracy and reduce the computation time of MCTS. The developed hardware-software architecture, implemented in a Zynq-7010, accelerated the MCTS execution up to 98 times. The architecture is fully scalable and if scaled to 10 processing elements, using a leaf parallelization method, can achieve an acceleration up to 668 times. }
Keywords: {pt=Xadrez, MCTS, FPGA, Simulações do MCTS em Hardware, en=Chess, MCTS, FPGA, Hardware MCTS simulations}

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