Research Project: Modeling and Solving Puzzle Games Using CSPs/ILPs/SAT (AI)

People

Supervisor

Description

Many real-world problems -- such as puzzle games -- are combinatorial problems, where the maximum number of required "actions" is known, it's just not clear which ones need to be taken. (In some cases also the exact number of 'actions' is not known, but we might still have some information available, e.g., which steps must be taken or how many at the most.) Such problems are often NP-complete and can be solved efficiently using AI techniques such as Constraint Satisfaction Problem (CSP) solvers, Integer Linear Programming (ILP) solvers, or Satisfiability (SAT) solvers. They are designed to solve problems that require to find a certain "configuration", or an "assignment" of values to a pre-defined number of variables.

All these technologies are thus well-suited to solve a range of puzzle 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 (CSP, ILP, or SAT) of the respective technology.
  • Translate this formal model into a text-file representation using standard languages used by the respective solvers.
  • Conduct an empirical evaluation thus comparing different solvers and also different versions of the model.
  • Present the result in your project report.

Goals

  • Model puzzle games or optimization problems using CSPs or ILPs. The problems should be modeled in a more general way using a problem generator so that bigger instances can be generated automatically.
  • Conduct an empirical evaluation.

Requirements

  • 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 constraint reasoning and current existing constraint reasoning systems (like CSP solvers or ILP solvers) to model and solve constraint reasoning problems.

Keywords

  • Artificial Intelligence
  • Constraint Reasoning
  • Puzzle Games

Updated:  10 August 2021/Responsible Officer:  Head of School/Page Contact:  CECS Webmaster