Artificial Intelligence Puzzle

Figures

Towers can be moved perpendicular

Bishops can be moved diagonally

Queens can be moved in all directions

The number on the squares represents the movement scope allowed

A-Star & Heuristic

Since the problem we are trying to solve is absolutely NP-HARD, we need an approximate solution. If we want a fast algorithm, we cannot spend much time expanding more nodes than necessary, knowing that these kinds of search algorithms have linear complexity in terms of time but become exponential in space.

Initially, I tried to always find the best solution using Backtracking techniques in the heuristic. However, there was a problem: the heuristic is called for each node expansion, in our case, about 200 times for each expansion (it is brutally hard to solve). The backtracking was used to find the best square pairs with the lowest distance among all of them (it is another hard problem because you know what you want, but you have to explore all the combinations to find it).

The truth is that it worked perfectly because the states were always expanded following the best path since the exhaustive search explores all possibilities to select the best one. And it finds it! There was a problem, though. Despite including branch and bound techniques, the A* was not capable of sustaining itself if the puzzle size was greater than 9-12 squares. I had imagined that this might happen, but it had to be tested for peace of mind.

Finally, an approximate heuristic is used and it is really fast, so we can apply four distinct heuristics, then run four A* Searches and finally choose the best solution. It is necessary to keep in mind that there are cases where a heuristic based on Euclidean distance works better than one using Manhattan distance, and so on. If in most cases the solutions found vary around [0, +2] among themselves, it is highly likely that the best solution is among them, and if not, then there is nothing to worry about because we are extremely close to the best solution.

However, even with an approximate solution, there are some cases where a good solution is extremely difficult to find, especially when the difficulty level is 'expert' and we are dealing with puzzles of sizes 6x6, 6x7, 7x6, or 7x7. It is difficult to stop the algorithm if a solution is hard to find. Setting a timer is never a good solution, so there is a depth limit on A* Search. If more than 5000 states have been expanded and we still have no solution, a new puzzle is recomputed and the whole process starts again (It is true that the worst case involves the A* exceeding 5000 states and being called again, but this is unlikely due to pure statistics). Therefore, the average time a user has to wait for a level is around 0-5 seconds. This seems quite reasonable considering the complex problem we are dealing with.

The conclusion is that, given the heuristic is just a numerical value, we can use different heuristics that return different values from different scales. We cannot call different heuristics from the same A*, but we can run four distinct A* searches, compare the four results, and finally choose the best one.

Level Generator

There are basically two models of generated levels: Matching Colors and Clustering.

The first step in generating a matching color level is to obtain a valid distribution. A distribution is an object that contains the percentage of each type of character for the level. For example, it doesn't make sense to generate a level that contains only bishops because it would have no solution.

Next, we need to determine a valid puzzle size, including the number of rows and columns. This will be decided based on the difficulty level provided to the instance of the object.

After that, it is necessary to obtain the colors of the puzzle. The number of colors depends on the puzzle size determined in the previous step.

The next stage involves generating the level. First, we generate the level as an array, which will be used to build a graph to check whether the level is connected. We can check the graph's connectivity by using the Depth First Search Algorithm as a traversal algorithm instead of a search algorithm. If the generated level has any isolated nodes, a recursive call is made, and this stage starts again until we get a valid level.

As a result, we now have a puzzle array based on 3-positional items. The first refers to the kind of item (tower, bishop, or queen), the second shows the scope of its move, and finally, the third indicates the square's color. Now, we can get the goal array, which is based on the color. All we have to do is extract it from the puzzle array, taking just the third position for each item.

Finally, both the start and goal puzzles are created using the arrays and based on the puzzle size. The puzzles are saved in the levelGenerator object to extract the best solution using the A* Search Algorithm. But that's another story, which is explained in its section.

The second type of level is generated in a similar way, but the goal is to end up with a puzzle where all the colors are clustered together. This means that every square should be adjacent to at least one edge of another square with the same color.