|
|
Genetic Algorithms driven by MCTS
Havránek, Štěpán ; Hric, Jan (advisor) ; Moudřík, Josef (referee)
Evolutionary and genetic algorithms are problem-solving methods designed according to a nature inspiration. They are used for solving hard problems that we cannot solve by any efficient specialized algorithm. The Monte Carlo method and its derivation the Monte Carlo Tree Search (MCTS) are based on sampling and are also commonly used for too complex problems, where we are dealing with enormous memory consumption and it is impossible to perform a complete searching. The goal of this thesis is to design a general problem solving method that is built from these two completely different approaches. We explain and implement the new method on one example problem: the Traveling salesman problem (TSP). Second part of this thesis contains various tests and experiments. We compare different settings and parametrizations of our method. The best performing variant is then compared with the classical evolutionary TSP solution or, for example, with greedy algorithms. Our method shows competitive results. The best results were achieved with the cooperation of our method and the classical evolutionary TSP solution. This union shows better results than any of its parts separately, which we find as a great success.
|
|
|
Solving of Problems using MCTS
Malý, Dominik ; Hric, Jan (advisor) ; Majerech, Vladan (referee)
Title: Solving problems using MCTS Author: Dominik Malý Department: Department of theoretical informatics and mathematical logic Supervisor: RNDr. Jan Hric Supervisor's e-mail address: Jan.Hric@mff.cuni.cz Abstract: MCTS (Monte Carlo Tree Search) methods are a state-of-the-art approach to the computer solution of strategic board game Go. Because of their versatility and successfulness, these techniques show great potential for all kinds of problems. This paper aims to explore the suitability of MCTS for solving different kind of problems, specifically games of one player, like Sudoku or SameGame. I've created a computer player based on MCTS, who can solve not only Sudoku and SameGame, but also other tasks of similar kind. I've experimentally examined many MCTS extensions and their eligibility for solving these games and through extensive testing I've also compared the suitability of various kinds of UCT selection fun- ctions and used heuristics. In case of SameGame I've compared my algorithm to another exi- sting one undertaking the same problem. In the end I've described what kind of problems has a MCTS-based computer player to overcome, if it is to successfully solve games of this type, and what characteristics should these problems posses to be suitable for MCTS solution. Keywords: MCTS, Go, Sudoku,...
|
|
|
A Controlled Searching of Game Trees
Vrba, Jan ; Hric, Jan (advisor) ; Majerech, Vladan (referee)
Title: A Controlled Searching of Game Trees Author: Jan Vrba Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: RNDr. Jan Hric Abstract: Monte-Carlo Tree Search is a search algorithm based on random Monte- Carlo playouts. Since it was first introduced in 2006, it has been successfully used in several areas. Most notably for the game Go. MCTS is intended mainly for problems with too large a state space to be fully explored in reasonable time. Working with a large state space and the fact that when evaluating a node, it first explores all possible moves leads to large memory complexity. This work explores options a user can use to regulate memory complexity based on the results of previous Monte-Carlo playouts. Keywords: MCTS, UCT, BMCTS, RAVE
|
|
|
Genetic Algorithms driven by MCTS
Havránek, Štěpán ; Hric, Jan (advisor) ; Moudřík, Josef (referee)
Evolutionary and genetic algorithms are problem-solving methods designed according to a nature inspiration. They are used for solving hard problems that we cannot solve by any efficient specialized algorithm. The Monte Carlo method and its derivation the Monte Carlo Tree Search (MCTS) are based on sampling and are also commonly used for too complex problems, where we are dealing with enormous memory consumption and it is impossible to perform a complete searching. The goal of this thesis is to design a general problem solving method that is built from these two completely different approaches. We explain and implement the new method on one example problem: the Traveling salesman problem (TSP). Second part of this thesis contains various tests and experiments. We compare different settings and parametrizations of our method. The best performing variant is then compared with the classical evolutionary TSP solution or, for example, with greedy algorithms. Our method shows competitive results. The best results were achieved with the cooperation of our method and the classical evolutionary TSP solution. This union shows better results than any of its parts separately, which we find as a great success.
|
|
|
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.
|
|
|
Solving of Problems using MCTS
Malý, Dominik ; Hric, Jan (advisor) ; Majerech, Vladan (referee)
Title: Solving problems using MCTS Author: Dominik Malý Department: Department of theoretical informatics and mathematical logic Supervisor: RNDr. Jan Hric Supervisor's e-mail address: Jan.Hric@mff.cuni.cz Abstract: MCTS (Monte Carlo Tree Search) methods are a state-of-the-art approach to the computer solution of strategic board game Go. Because of their versatility and successfulness, these techniques show great potential for all kinds of problems. This paper aims to explore the suitability of MCTS for solving different kind of problems, specifically games of one player, like Sudoku or SameGame. I've created a computer player based on MCTS, who can solve not only Sudoku and SameGame, but also other tasks of similar kind. I've experimentally examined many MCTS extensions and their eligibility for solving these games and through extensive testing I've also compared the suitability of various kinds of UCT selection fun- ctions and used heuristics. In case of SameGame I've compared my algorithm to another exi- sting one undertaking the same problem. In the end I've described what kind of problems has a MCTS-based computer player to overcome, if it is to successfully solve games of this type, and what characteristics should these problems posses to be suitable for MCTS solution. Keywords: MCTS, Go, Sudoku,...
|
|
|
Srovnávací studie www stránek světových univerzit
Andits, Tomáš ; Kubešová, Vlasta (advisor) ; Třeštíková, Ludmila (referee)
Bakalárska práca ma za cieľ porovnať a analyzovať www stránky University at Buffalo, University of Cape Town, The Chinese University of Hong Kong, Univerzity of Melbourne a Vysokej školy ekonomickej v Praze z hľadiska grafického spracovania, informačnej hodnoty, jednoduchosti použitia a bezbariérovej prístupnosti. Hlavným bodom je vytvorenie metodológie vhodnej k analýze a porovnaniu stránok vybraných univerzít. Tie prejdú detailným rozborom, na jeho základe budú bodovo ohodnotené.
|
|
|
Srovnávací studie www stránek světových univerzit
Andits, Tomáš ; Střížová, Vlasta (advisor) ; Třeštíková, Ludmila (referee)
Bakalárska práca ma za cieľ porovnať a analyzovať www stránky University at Buffalo, University of Cape Town, The Chinese University of Hong Kong, Univerzity of Melbourne a Vysokej školy ekonomickej v Praze z hľadiska grafického spracovania, informačnej hodnoty, jednoduchosti použitia a bezbariérovej prístupnosti. Hlavným bodom je vytvorenie metodológie vhodnej k analýze a porovnaniu stránok vybraných univerzít. Tie prejdú detailným rozborom, na jeho základe budú bodovo ohodnotené.
|
guest ::
