A review of AI puzzles

Puzzle problems are the framework in which the search for Artificial Intelligence takes place. The evolution from easier to more advanced understanding of AI is strongly connected to the evolution of AI puzzle problems. There are certain categories available:

1. easy: traveling salesman problem, chess problems, tictactoe game, Knight's tour, path planning
2. medium: 15 puzzle problem, piano movers problem, Tetris playing AI agent, pacman AI agent
3. advanced: dataset driven machine learning
4. hard: Visual question answering, instruction following, multimodal machine learning

Let us describe first the easy category. This sort of problems has the longest tradition in the AI literature and the problems including possible algorithms are described in high amount of papers. Nearly every introduction course in computer science, mention or explains the traveling salesman problem. It has become a standard challenge for investigating the performance of algorithms.

Most of the problem from the easy category can be solved with a backtracking algorithms. In case of chess problems, the algorithms needs improvement from an evaluation function but the main principle is to traverse the state space.

The problems from the medium section are less often explained and they are requiring sophisticated heuristics. The first puzzle in the section, the “15 puzzle problem” is used exclusively to explain the advantages of an evaluation function, namely the manhattan distance, while the other problems like “pacman AI agent” will need a finite state machine or an advanced behavior tree. Its not possible to solve the problem in the medium category with easy to implement backtracking algorithms because of the larger size of the state space.

The two remaining categories, advanced and hard, are only seldom described in the literature. The first papers about the subjects were published since the year 2000. For VQA related problems, the first written description is even available since 2010.

What all these problem categories have in common is, that they do not require software or hardware in terms of computer science. But the problems can be discussed independently of computer science. A typical problem description fits on a single piece of paper which reads like the description for a board game. So we can say, that the problems belong to the umbrella term of game theory. The complex reality gets simplified into game rules and the player can take decision inside the rule system.