PhD Thesis

Prediction-Based Search for Autonomous Game-Playing

Abstract

Simulation-based search algorithms have been widely applied in the context of autonomous game-playing. Their flexibility allows for the rapid development of agents that are able to achieve satisfying performance in many problem domains. However, these algorithms share two requirements: access to a forward model and full knowledge of the environment's state. In this thesis, simulation-based search algorithms are adapted to tasks in which either the forward model or the state of the environment is unknown.

To play a game without a forward model, methods for learning the environment's model from recent interactions between the agent and the environment are proposed. These forward model learning techniques allow the agent to predict the outcome of its actions, and therefore, enable a prediction-based search process. An analysis of environment models shows how they can be represented and learned in the form of an end-to-end forward model. Based on this general approach, three methods are proposed which reduce the number of possible models and, thus, the training time required.

In case the environment's state cannot be fully observed by the agent and the number of possible states is low, state determinisation methods which uniformly sample possible states have shown to perform well. However, if the number of states is high, the uniform state sampling approach performs worse than non-determinising search methods. In this thesis, two methods for predictive state determinisation are proposed, evaluated in the context of the collectible card game Hearthstone.

Code Repositories

• Forward Model Learning
• Predictive-State Determinization

BibTeX

@phdthesis{Dockhorn2020Dissertation,
  author = {Dockhorn, Alexander},
  title  = {Prediction-Based Search for
            Autonomous Game-Playing},
  school = {Otto von Guericke University Magdeburg},
  year   = {2020},
  pages  = {1--231}
}