Artificial IntelligencePuzzle

Pau Sanchez Valdivieso - www.pausanchezv.com

Click the button to start enjoying!

Puzzle rules

The objective involves getting the goal state color starting from the start state by using the allowed movements.

When a square is moved all its content is also moved, so that the start square will be changed with the destination square.

The movement is governed by the square which starts the movement, so that the destination square will have to change its position even if its figure cannot make that move.

Both squares, start and destination will be able to do the movements of their figures in their new positions on the matrix.

Keep in mind that in the goal state, it doesn't matter the position of the figures. It's only important to get the matrix goal color.

There are two types of puzzle, those having goal state long for reaching the final state using the minimum number of movements. On the other hand, those puzzles which don't have goal state have the goal of ending up having all the colors connected by clusters.

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 have to get an approximate solution because if we want a fast algorithm, then cannot spend much time expanding more nodes than the necessary ones, knowing that these kind of search algorithms have linear complexity in terms of time, but they become exponential in space.

First of all I tried to get the best solution always, and I got it by using Backtracking techniques in the heuristic. But 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 which the distance among all of them was lower (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 expanded following always the best path since the exhaustive search explores absolutely all the possibilities to select the best one. And it finds it! There was a problem, though. In spite of 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 it was gonna happen, but anyway, it had to be tested to let myself rest in peace.

Finally an approximate heuristic is used and it is really fast, so we can throw four distinct heuristics, then run four A* Search and finally choose the best solution. It is necessary to keep in mind that there are cases, for instance, in which an heuristic based on the euclidean distance works better than the other one using the manhattan distance, and so on... If in most cases the solutions found varies around [0, +2] among themselves, it means that it is highly likely the best is one of them, and if it's not, then there is nothing to worry about because we are extremely close to the best solution.

But even if we are using an approximate solution, there are some cases in which a good one is extremely difficult to spot, especially when the difficulty level is 'expert' and we are dealing with puzzles 6x6, 6x7, 7x6 or 7x7 size. It's difficult to stop the algorithm if some solution is hard to be found. Setting a timer is never a good solution, so there is a limit depth on A* Search, then if more than 5000 states have been expanded and we still have no solution, a new puzzle is recomputed and the whole process starts yet again (It is true that the worst case involves that the A-Star overcomes 5000 states, then it is called once more time, and so on..., but it is not going to happen due to pure statistic). So the average time that an user has to wait for a level is around 0-5 seconds. It seems quite reasonable if we keep in mind the brutal problem we are dealing with.

The conclusion is that, given that the heuristic is just a numerical value, we can have some different heuristics which return different values from different scales, so we cannot call different heuristics from the same A*, but we can call 4 distinct A*, compare 4 results and finally choose the best one.

Level Generator

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

The first thing we have to do to generate a matching color level is to obtain a valid distribution. A distribution is an object that contains the amount percentage of characters for the level. For example, it doesn't make sense generating a level that contains only bishops because it has no solution.

Now we have to get a valid puzzle size, both number of rows and columns. It will be given depending on the difficulty which is passed through the instance of the object.

After that it's necessary to obtain the colors of the puzzle. The number of the colors depends on the puzzle size obtained in the previous step.

The next stage involves generating the level. First of all we generate the level as an array which will be used to build a graph in order to help us to check whether or not the level is connected. We can check the graph connection by using the Depth First Search Algorithm using it as a traversal algorithm instead of search algorithm. Then if the generated level has any isolated node, a recursive call is produced and this stage starts yet again until we get a valid level.

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

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

The second kind of level is generated in a similar way, but the goal consists of ending up with a puzzle where all its colors are together, in other words, clustered. It means that every square should be side by side by at least one edge with another square having the same color.

The game

This algorithm was useful for the implementation of my last Android Game Galactic Monsters which can be found by following the link: https://www.galacticmonsters.com

Who I am

I am a Computer Engineer who loves programming and enjoys developing games, applications, and algorithms. My education encompasses a large variety of qualifications:

2 x Associate's degree in Business Management (Industrial University of Barcelona)
1 x Bachelor's degree in Computer Engineering (University of Barcelona - Mathematics Faculty)

I really like programming Artificial Intelligence algorithms to find the best solution for a given problem, I love developing applications and thinking that someone is going to use them. It makes me feel that I am useful and I can contribute a little to improve anything.

I have been the founder of some well-known platforms like makethejobs.com, capable of joining more than 3.000 people after releasing the website in 2014, in only two weeks. I am really keen on developing games involving graphs, matrices, and A.I. such as galacticmonsters.com or savealltherobots.com, both founded and developed by myself.

I think developers have a special power since we are able to imagine something and make it real, and that is one of the most beautiful sensations I have ever felt. Rarely will you come across people capable of doing that! Everyone has their strengths and abilities, but a programmer is a programmer :)

I am currently working at Opportunity Network as a Software Engineer surrounded by amazing people helping me learn something new every day and helping the platform improve in ways I could never have imagined. I am enjoying this fascinating experience as much as I can without losing sight of my own projects.

All this makes me get better and better every day in every way as days go by, until the day I die.

Pau.