|
|
Bidirectional heuristic search
Hřebejk, Tomáš ; Vyskočil, Tomáš (advisor) ; Zajíček, Ondřej (referee)
The purpose of this bachelor thesis is to summarize the most important results on bidirectional heuristic search and to bring some new thoughts. Two algorithms are described which attempt to improve the best algorithms in this field. The algorithms were experimentally compared with a unidirectional algorithm. According to the result of the comparison, we can state that bidirectional heuristic algorithms can be much faster than unidirectional heuristic algorithms. The text also describes how to solve some problems by shortest-path algorithms and how to make a good heuristic. A program which can solve a generalized puzzle was created as a demonstration.
|
|
|
Arimaa challenge - static evaluation function
Hřebejk, Tomáš ; Majerech, Vladan (advisor) ; Baudiš, Petr (referee)
Arimaa is a strategic board game for two players. It was designed with the aim that it will be hard to create a computer program that could defeat the best human players. In this thesis, we focus on the design of the static evaluation function for Arimaa. The purpose of a static evaluation function is to determine which player is leading in a given position and how significant the lead is. We have divided the problem into a few parts, which were solved separately. We paid most attention to the efficient recognition of important patterns on the board, such as goal threats. The basic element of the proposed evaluation function is mobility. For each piece, the number of steps that the piece would need to get to other places on the board is estimated. We also examined machine learning. We developed a new algorithm for learning a static evaluation function from expert games. An implementation of an Arimaa playing program, which demonstrates the proposed methods, is part of the thesis. Powered by TCPDF (www.tcpdf.org)
|
|
|
Bidirectional heuristic search
Hřebejk, Tomáš ; Vyskočil, Tomáš (advisor) ; Zajíček, Ondřej (referee)
The purpose of this bachelor thesis is to summarize the most important results on bidirectional heuristic search and to bring some new thoughts. Two algorithms are described which attempt to improve the best algorithms in this field. The algorithms were experimentally compared with a unidirectional algorithm. According to the result of the comparison, we can state that bidirectional heuristic algorithms can be much faster than unidirectional heuristic algorithms. The text also describes how to solve some problems by shortest-path algorithms and how to make a good heuristic. A program which can solve a generalized puzzle was created as a demonstration.
|
guest ::
