|
|
Monte Carlo Techniques in Planning
Trunda, Otakar ; Barták, Roman (advisor) ; Toropila, Daniel (referee)
The Monte Carlo Tree Search (MCTS) algorithm has recently proved to be able to solve difficult problems in the field of optimization as well as game-playing. It has been able to address several problems that no conventional techniques have been able to solve efficiently. In this thesis we investigate possible ways to use MCTS in the field of planning and scheduling. We analyze the problem theoretically trying to identify possible difficulties when using MCTS in this field. We propose the solutions to these problems based on a modification of the algorithm and preprocessing the planning domain. We present the techniques we have developed for these tasks and we combine them into an applicable algorithm. We specialize the method for a specific kind of planning problems - the transportation problems. We compare our planner with other planning system.
|
|
|
Arimaa challenge - comparission study of MCTS versus alpha-beta methods
Jakl, Tomáš ; Majerech, Vladan (advisor) ; Hric, Jan (referee)
In the world of chess programming the most successful algorithm for game tree search is considered AlphaBeta search, however in game of Go it is Monte Carlo Tree Search. The game of Arimaa has similarities with both Go and Chess, but there has been no successful program using Monte Carlo Tree Search so far. The main goal of this thesis is to compare capabilities given by Monte Carlo Tree Search algorithm and AlphaBeta search, both having the same evaluation function, in the game of Arimaa.
|
|
|
Application of MCTS to the game Quoridor
Tomek, Jakub ; Hric, Jan (advisor) ; Majerech, Vladan (referee)
Monte Carlo Tree Search is quite a new technique for searching a tree developed for a computer player in games, that have too large state space to be effectively searched by an deterministic algorithm. MCTS in its basic version offers a simple way to evaluate positions without any domain specific knowledge. MCTS was already applied in many variants for computer Go, however its usage for other games has not been nearly as deep studied. This work deals with the option of using MCTS on a particular game called Quoridor.
|
|
|
MCTS with Information Sharing
Baudiš, Petr ; Hric, Jan (advisor) ; Majerech, Vladan (referee)
We introduce our competitive implementation of a Monte Carlo Tree Search (MCTS) algorithm for the board game of Go: Pachi. The software is based both on previously published methods and our original improvements. We then focus on improving the tree search performance by collecting information regarding tactical situations and game status from the Monte Carlo simulations and sharing it with and within the game tree. We propose specific methods of such sharing --- dynamic komi, criticality-based biasing, and liberty maps --- and demonstrate their positive effect. based on collected play-testing measurements. We also outline some promising future research directions related to our work.
|
|
|
Agent Based Gameplaying System
Trutman, Michal ; Zbořil, František (referee) ; Král, Jiří (advisor)
This thesis deals with general game playing agent systems. On the contrary with common agents, which are designed only for a specified task or a game, general game playing agents have to be able to play basically any arbitrary game described in a formal declarative language. The biggest challenge is that the game rules are not known beforehand, which makes it impossible to use some optimizations or to make a good heuristic function. The thesis consists of a theoretical and a practical part. The first part introduces the field of general game playing agents, defines the Game Description Language and covers construction of heuristic evaluation functions and their integration within the Monte Carlo tree search algorithm. In the practical part, a general method of creating a new heuristic function is presented, which is later integrated into a proper agent, which is compared then with other systems.
|
guest ::
