Research Project: Modeling and Solving (Puzzle) Games Using AI

Description

Classical AI Planning serves the goal of finding a sequence of actions that transforms a given state into a desired goal state. Given an adequate model of the world this technology can be used in a wide range of possible application scenarios. It has been deployed successfully in many real-world applications such as automated factories and robotics. It is thus a general problem solving technique that's applied when ever we need to find a sequence of actions (of unknown lenght) to transform an initial world state into a state that fulfills some desired properties.

Other AI techniques, mostly Constraint Satisfaction Problem (CSP) solvers, Integer Linear Programming (ILP) solvers, or Satisfiability (SAT) solvers, are used to solve problems that require to find a certain "configuration", or an "assignment" of values to a pre-defined number of variables.

Both technologies are thus well-suited to solve a range of puzzle games or board games.

In this project, we will first decide on approximately two interesting puzzles or games (feel free to propose something!). Then you will have to:

  • model these games/puzzles in an appropriate description language (classical planning, CSP, ILP, etc.) of the respective technology
  • translate this formal model into a text-file representation using standard languages like PDDL for classical planning.
  • conduct an empirical evaluation thus comparing different solvers and also different versions of the model
  • present the result in your project report

Please note that I will accept almost no if any students for S1 2020 due to an extreme work-load teaching-wise. You might apply, but chances for acceptance are slim (unless you have expectional good grades in the clear HD spectrum).

Goals

  • Planning and Optimization

Requirements

  • Knowledge in classical planning is helpful, but not required
  • Knowledge in constraint reasoning (CSP, SAT, etc.) are helpful, but not required

Please send me:

  • The course code.
  • The URL of your course.
  • The number of points your course has (i.e., 6, 12, 24, or 24 honours final project).
  • When you would like to do your project.

Background Literature

 

Further material:

Gain

  • You will be able to use AI planning and current existing planning systems to model and solve planning problems -- OR, depending on the technology you end up using -- you will be able to use constraint reasoning and current existing constraint reasoning systems to model and solve constraint reasoning problems.

Keywords

  • Artificial Intelligence
  • Automated Planning
  • Constraint Reasoning
  • Puzzle Games

Updated:  1 June 2019/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing