engleski

Minimax and Monte Carlo Tree Search Implementations for Two Player Game

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.

minimax ; mcts ; uttt ; implementation

nije evidentirano