The project is not yet taken by another student.
It might however be that I don't have capacities left in general. Please check out the main page on research projects to see whether I'm maxed out. (I don't post this here so that I don't have to update all my project descriptions in case I don't accept more students.)
In this project we will first decide on a puzzle problem (a list of possible games is given below) as well as on a technology, i.e., SAT (i.e., propositional Logic) or planning. The chosen problem will then be modeled in said technology and solved with state-of-the-art solvers.
The slightly longer version:
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 and which order. (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 thereby 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. Other problems are more suitable to be solved by AI planning technology. Those are problems where one doesn't need to find the correct "configuration", but to find the right sequence of actions (e.g., in the Rubic's cube).
In this project, we will first decide on one or two interesting puzzles or games (feel free to propose something!). Depending on the puzzle(s) and/or game(s) we will decide on an adequate technology (i.e., CSP/ILP/SAT, or planning) and then first model the problem with said technology and then solve it with a state-of-the-art solver from the respective field.
Your task is:
This project is either on classical planning or SAT solving (or CSPs or ILPs, but they are closely related).
There is a number of puzzle games we could use, and I have already purchased a collection of such games that I can borrow for the time this project is done. The following is a list of problems I already have available:
Note that you can also propose your own game/puzzle!