|
|
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.
|
|
|
Algorithms for Tafl Games
Halmo, Kryštof ; Kočí, Radek (referee) ; Zbořil, František (advisor)
The goal for this work is to create a program witch allows the possibility to play some types of Tafle games against a some algorithms or against a other player. Algorithms used in the solution wear MCTS, Alfabeta and Minmax whit heurystyks which help to find a move faster and evaluate the game board whit specified parameters. Created solution allows the user to select the parameters for running this program. Results of this work provides a comparison between different types of Tafle games and the comparison of different types of algorithms agents one another.
|
|
|
Monte Carlo Techniques in Planning
Trunda, Otakar ; Barták, Roman (advisor)
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.
|
|
|
Playing Gomoku with Neural Networks
Slávka, Michal ; Kolář, Martin (referee) ; Hradiš, Michal (advisor)
Táto práca sa zaoberá použitím algoritmu AlphaZero pre hru Gomoku. AlphaZero je založený na spätnoväzbnom učení a k trénovaniu nemusia byť využité žiadne existujúce datasety. Trénovanie prebieha iba na hrách algoritmu samého so sebou. AlphaZero používa algoritmus na prehľadávanie stromu, pre zlepšenie stratégie. Na vylepšnej stratégii sa následne trénuje neurónová sieť. Tento prístup bol úspešný v hrách proti existujúcim algoritmom. Generovanie trénovacích dát vysokej kvality si vyžaduje veľa výpočetne náročných iterácií trénovania a generovania dát. Experimenty ukázali, že každou iteráciou sa algoritmus zlepšuje, čo naznačuje, že je ešte miesto na zlepšenie, ale množstvo iterácií nedostačovalo na to, aby bol poriadne natrénovaný.
|
|
|
Monte Carlo Techniques in Planning
Trunda, Otakar ; Barták, Roman (advisor)
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.
|
|
|
Artificial Intelligence for Go on Non-standard Topologies
Červeň, Martin ; Gemrot, Jakub (advisor) ; Brunetto, Robert (referee)
Go is a popular strategic game for two players. It is usually played on a squared board of 19x19. The aim of this thesis is to create an application allowing a user to play Go on any board defined by a graph, such as sphere and torus. We created a web based client-server application, written in JavaScript and Node.js, that is using protocol Websockets for fast communication. Application allows user to play against other players on the Internet. Server can support multiple concurrent games at the same time. Boards can be created by modelling tool Blender and then imported into the application. Our application supports 3D rendering of these boards in web client using WebGL. It has responsive control, allowing changes of view by rotating, moving and zooming. Users can also play against artificial intelligence. 1
|
|
|
Kooperativní hledání cest s protivníkem
Ivanová, Marika ; Surynek, Pavel (advisor) ; Mrázová, Iveta (referee)
Presented master thesis defines and investigates Adversarial Cooperative Path-finding problem (ACPF), a generalization of standard Cooperative Path-finding. In addition to the Cooperative path- finding where non-colliding paths for multiple agents connecting their initial positions and destinations are searched, consideration of agents controlled by the adversary is included in ACPF. This work is focused on both theoretical properties and practical solving techniques of the considered problem. ACPF is introduced formally using terms from graph theory. We study computational complexity of the problem where we show that the problem is PSPACE-hard and belongs to EXPTIME complexity class. We introduce and discuss possible methods suitable for practical solving of the problem. Considered solving approaches include greedy algorithms, minimax methods, Monte Carlo Tree Search and adaptation of algorithm for the cooperative version of the problem. Surprisingly frequent success rate of greedy methods and rather weaker results of Monte Carlo Tree Search are indicated by the conducted experimental evaluation. Powered by TCPDF (www.tcpdf.org)
|
|
|
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.
|
guest ::
