Naslov
Minimax and Monte Carlo Tree Search Implementations for TwoPlayer Game
(Minimax and Monte Carlo Tree Search Implementations for Two Player Game)

Autori
Toma Rončević ; Marina Rodić ; Ljiljana Despalatović

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, ostalo, stručni

Skup
5. međunarodna znanstvena i stručna konferencija “IZAZOVI DANAŠNJICE” 5th International Scientific and Professional Conference “THE CHALLENGES OF TODAY”

Mjesto i datum
Šibenik, Hrvatska, 07.10.2021. - 08.10.2021

Vrsta sudjelovanja
Ostalo

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
minimax ; mcts ; uttt ; implementation

Sažetak
In this paper, we examine practical implementations of two algorithms: minimax and Monte Carlo Tree Search (MCTS). Both algorithms have been applied in the domain of two-player games with different extensions, modifications, and success. In this work, the two algorithms are implemented for a game that is an upgradeof the children's Tic-Tac-Toe game, now played on nine 3x3 boards with additional rules, called Ultimate Tic-Tac-Toe (UTTT). While the original game is trivial, this version is much harder to solve and represents a good use case for more advanced algorithms' implementation. The game was also used in an open competition among several hundred enthusiasts where our minimax approach arrived sixth in the finals. We give an overview of both algorithms, discuss their advantages and drawbacks, and describe their common modifications. We also discuss differences between algorithms, their results, and implementation details, both related and unrelated to our use case.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA