Original title:
Řešení hry Sokoban pomocí genetických algoritmů
Translated title:
Investigation of Sokoban Game Using Genetic Algorithms
Authors:
Nezvalová, Leona ; Vašíček, Zdeněk (referee) ; Minařík, Miloš (advisor) Document type: Bachelor's theses
Year:
2012
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Tato práce se zabývá tvorbou automatického řešení hry Sokoban s využitím gentických algoritmů. Důraz je kladen především na reprezentaci chromozomu, která pomáhá řešit hlavní problémy hry - velikost stavového prostoru a prezence uváznutí. Na tyto problémy je také zaměřena speciální operace křížení a fitness ohodnocující funkce. Vedlejším cílem je optimalizace nalezeného řešení pomocí optimalizační funkce i samotné evoluce.
This work proposes an automatic Sokoban solver based on genetic algorithms. Emphasis is placed on the chromosome representation, that helps to deal with main problems related to automatic solving - size of a state space and presence of deadlocks. These problems are also addressed by specialized crossover operation and fitness function. The secondary objective is to optimize the solution using the optimization function and evolution itself.
Keywords:
automatic solver; evolution; Genetic algorithms; IDA*; Sokoban; automatické řešení; evoluce; Genetické algoritmy; IDA*; Sokoban
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/52917