Original title:
Strategická desková hra s neurčitostí
Translated title:
Strategic Game with Uncertainity
Authors:
Sova, Michal ; Zbořil, František (referee) ; Zbořil, František (advisor) Document type: Bachelor's theses
Year:
2021
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Tato páce řeší autonomní hraní hry Scotland Yard za využití metody strojového učení. Daný problém je vyřešen pomocí algoritmu Monte Carlo tree search. Algoritmus Monte Carlo tree search byl testován proti algoritmu Alfa-beta. Výsledky testování ukázaly, že navržený algoritmus je funkční, ale procento výher u algoritmu Monte Carlo tree search je nižší než u algoritmu Alfa-beta. Výsledkem práce je funkční verze systému, který hraje zjednodušenou verzi hry Scotland Yard autonomně. Dále práce obsahuje rozšíření hry Scotland Yard přidáním agentů a změnou parametrů. Rozšíření této verze pro algoritmus Alfa-beta nebylo úspěšné kvůli nedostatečné kapacity vlastních zdrojů. Naopak algoritmus Monte Carlo tree search se jeví v tomto ohledu úspěšnější.
The thesis focuses on creating an autonomous system for the game Scotland Yard by using machine learning method. The problem is solved by algorithm Monte Carlo tree search. Algorithm Monte Carlo tree search was tested against algorithm Alpha-beta. These results showed that Monte Carlo tree search algorithm is operational but win rate of this algorithm is lower than win rate of algorithm Alpha-beta. The resulting system is functional, autonomous and capable of playing the game Scotland Yard on simplified game area. There was an attempt to expand simplified version of the game Scotland Yard. In expanded version algorithm Alpha-beta was not successful because of insufficient computational resources. Algorithm Monte Carlo tree search, on the other hand, was more successful in expanded version.
Keywords:
alpha-beta; AlphaGo; board games; game theory methods; games with uncertainity; Go; machine learning; Monte Carlo Tree Search (MCTS); neural network; Scotland Yard; strategic games; alfa-beta; AlphaGo; Go; hry s neurčitostí; metody hraní her; Monte Carlo Tree Search (MCTS); neuronové sítě; Scotland Yard; stolní hry; strategické hry; strojové učení
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/199364