logical thinking to choose a best move

Aims: To understand simple AI techniques and algorithms and how they can be applied to solve puzzles and play games.

Background:

Many puzzles and games require logical thinking to choose a best move, or to find a hidden pattern. We have moved on a long way from games of patience. What unites them is that they are not time based and are all just for one player. They can all be solved by AI.

We most often use a backtrack based search to find the best move, or the solution. We can employ algorithms to improve backtracking like consistency pruning (e.g.) arc-consistency, look ahead (e.g.) forward checking, efficient backtracking (like backjumping) and variable and value heuristics (like Dynamic Variable Ordering).

If there is a pay off and we are trying to optimise then we can use branch and bound, or alpha/beta pruning, or even expectimax optimization.

In the end we can solve these puzzles quickly, and much better than people.

Some of these games have web based implementations, in which case you can extend the project to play the game automatically, as though you were typing, by using the debugging mode available on all modern browsers.

Most of these games can be read from picture files, using another form of AI, image processing.

A common and hard task for such games is to evaluate their difficulty. This is very hard to do as games that computers are slow at may not be those that people see as hardest. Some games like Sudoku have extensive online, pre-coded games libraries that you can use to try to learn what makes a game difficult.

Sometimes there are online cheat pages that give hints and human algorithms for solving games. Perhaps these should be incorporated into your solver.

The following would all make good examples for this project.

Constraint Satisfaction is one of the leading technologies in Artificial Intelligence for solving search problems. A constraint satisfaction problem instance can be seen as a set of related questions that need to be answered. We cannot answer any particular question without knowing the answers to those questions which affect it. You should research and report on how this technique could be used for your puzzle/game. One goal of the project might be to allow people to play your chosen game off-line. If you are puzzle solving the perhaps you could generate new puzzles, or evaluate and solve existing ones. Here you would stress a beautiful experience rather than extensive background theory.

This approach is applicable to more general AI problems found in machine vision, fleet scheduling, staff rostering, machine shop design, game playing, frequency assignment, vehicle routing etc., Perhaps your solver could be generalised to solve a whole class of such problems.

It is ideal for solving Sudoku. Constraint solvers are relatively easy to implement in Java and can solve even hard Sudoku instances in very little time. In this project you will see that the time taken by a constraint solver (although very fast indeed) really represents the difficulty rating that papers gives the puzzles. It seems that we are similar in behaviour to constraint solvers.

As you can see in the extensions it is sensible to extend your project by choosing to write it for a mobile device. This new set of acquired skills would need groundwork done in the fist term.

Other things that would be big changes and would require significant extra work, but would allow very high scores would be to use machine vision to enter puzzle or to automatically playing the game/solve the puzzles on a public website”

Early Deliverables

Proof of concept programs: Simple colourful GUI with an active button
Proof of concept programs: Relevant Data structures including a priority queue.
Proof of concept programs: Solving the eight queens problem using backtracking
Proof of concept program which solves a simple example of your puzzle.
Reports: Design Patterns for AI and Search.
Report on Backtracking and Recursion.
Reports: Constraint Satisfaction, particularly consistency techniques.
Reports: Techniques and Algorithms used by human solvers.
Reports: User Interface design for a solver
Reports: Complexity, NP hardness and the big O notation. Estimating problem size and hardness of your puzzle.

Final Deliverables

The program must have a full object-oriented design, with a full implementation life cycle using modern software engineering principles
The program will have a splash screen and at least two other user interaction screens.
The program will have a Graphical User Interface that can be used to generate, load, save, solve and help with puzzle solving/game playing.
The program must be able to produce puzzles that have only one correct solution, or games that have a single best strategy.
The report will describe the software engineering process involved in generating your software.
The report will describe interesting algorithms and programming techniques used (or able to be used) on the project.
The report will discuss the choice of data structures and their performance impact on the solving and generation algorithms.
The report will describe at least a backtracking and recursion solving algorithm and will compare them (including benchmark).
The report will describe the CSP and algorithms useful for solving the CSP including generalised arc consistency, Forward Checking, DVO and Backjumping.

Suggested Extensions

Porting the program to a mobile device
Solving and benchmarking public domain sets of puzzles
Using XML based files to store and load puzzles
Solving more than one kind of puzzle
Using machine vision to enter puzzle
Automatically playing the game/solving the puzzle on a public website
The program gives hints for users when they are stuck, and allows users to step back.
The program supports printing, different screen size, timers etc.,.

Reading

http://ktiml.mff.cuni.cz/~bartak/constraints/