Solving general game playing puzzles using heuristics search

One of the challenges of General Game Playing (GGP) is to effectively solve puzzles. Solving puzzles is more similar to planning algorithms than the search methods used for two- or multi-player games. General problem solving has been a topic addressed by the planning community for years. In this thesis we adapt heuristic search methods for automated planning to use in solving single-agent GGP puzzles. One of the main differences between planning and GGP is the real-time nature of GGP competitions. The backbone of our puzzle solver is a realtime variant of the classical A* search algorithm we call Time-Bounded and Injection-based A* (TBIA*). The TBIA* is a complete algorithm which always maintains a best known path to follow and updates this path with new and better paths as they are discovered. The heuristic TBIA* uses is constructed automatically for each puzzle being solved, and is based on techniques used in the Heuristic Search Planner system. It is composed of two parts: the first is a distance estimate derived from solving a relaxed problem and the second is a penalty for every unachieved sub-goal. The heuristic is inadmissible when the penalty is added but typically more informative. We also present a caching mechanism to enhance the heuristic performance and a self regulating method we call adaptive k that balances cache useage. We show that our method both adds to the flora of GGP puzzles solvable under real-time settings and outperforms existing simulation-based solution methods on a number of puzzles.

Author dc:creator

• Gylfi Þór Guðmundsson 1977-

Contributors dc:contributor

• Háskólinn í Reykjavík

• Tölvuleikir
• Þrautir
• Tölvunarfræði
• Meistaraprófsritgerðir
• Games
• Computer games
• Computer science

Language dc:language.iso

en

Handle dc:identifier.uri

http://hdl.handle.net/1946/7422

OAI identifier oai:identifier

oai:skemman.is:1946/7422