Sliding Puzzle – Solving Search Problem with Iterative Deepening A*Demystifying Graph TraversalGreg SurmaBlockedUnblockFollowFollowingJan 27In today’s article, we are going to solve Sliding Puzzle game with Iterative Deepening A* algorithm.
In order to do so, we are going to disentangle this popular logic game and represent it as a Search Problem.
By the end of this article, you will be able to implement search algorithms that can solve some of real-life problems represented as graphs.
Iterative Deepening A* SolverSliding Puzzle GameBefore we proceed to the core of this project, let’s begin with providing some info about a game which we will strive to solve.
A sliding puzzle, sliding block puzzle, or sliding tile puzzle is a combination puzzle that challenges a player to slide (frequently flat) pieces along certain routes (usually on a board) to establish a certain end-configuration.
The pieces to be moved may consist of simple shapes, or they may be imprinted with colors, patterns, sections of a larger picture (like a jigsaw puzzle), numbers, or letters.
Rules of this game are very simple – we are sliding (←, →, ↑ , ↓) tiles to reach the final state in which all numbers are in order with ‘1’ in the top left corner of the board.
I recommend you to play this game yourself.
As usual, you can find it on GitHubgsurma/sliding_puzzleSwift implementation of the Sliding Puzzle game with Iterative Deepening A* AI Solver.
– gsurma/sliding_puzzlegithub.
comand on the AppStore.
Sliding Puzzle – Board GameRead reviews, compare customer ratings, see screenshots, and learn more about Sliding Puzzle – Board Game.
Download…itunes.
apple.
comNow as we are more familiar with the game, let’s solve it!Search AlgorithmsLet’s begin our Graph Traversal journey with visualizing and setting our problem.
“A goal properly set is halfway reached.
” Zig ZiglarProblemGiven a board state, find a combination of moves that leads to the final state.
Graph RepresentationNow that we have our problem defined, let’s represent it as a graph.
More specifically, weighted (each connection has a weight of 1) cyclic (it is possible to ‘go in circles’) undirected (connections are bidirectional) graph.
Initial board state is a starting node of the graph, its root.
Somewhere in the graph of possible board states, there is a final state node and our goal is to find it as fast as possible.
Since we are dealing with the graph traversal problem, let’s take a look at our node representation which is a building block of a graph.
Every node represents a specific board state, where a board state is represented by an array of tiles with the following propertiesKeep in mind that even though we are sliding tiles, we are not going to modify its positions.
We are going to keep positions constant and modify its values instead.
With this approach, it will be way easier for us to keep references to the neighbor tiles because once set in the beginning, they will remain unchanged.
Besides position and neighbor tiles we are also going to store value and goalValue variables, where the former keeps the temporary value visible on the board and the latter keeps the final desired value.
Let’s take a look at the following exampleand its representation.
x: 0, y: 0, value: 4, goalValue: 1x: 1, y: 0, value: 1, goalValue: 2x: 2, y: 0, value: 6, goalValue: 3x: 0, y: 1, value: 0, goalValue: 4x: 1, y: 1, value: 3, goalValue: 5x: 2, y: 1, value: 5, goalValue: 6x: 0, y: 2, value: 2, goalValue: 7x: 1, y: 2, value: 7, goalValue: 8x: 2, y: 2, value: 8, goalValue: 0Moreover, keep in mind that we don’t have to store the full history of moves for every node in the graph.
In order to create a path that led to the given node, we only need to store the reference to the previous node because we can recursively go back to the starting node and capture all the moves that were taken.
With the above representation, we are ready to proceed with the search algorithms.
Meanwhile, I recommend you to check one of my previous articles where I used search algorithms to solve the game of Snake.
Slitherin – Solving the Classic Game of Snake????.with AI????.(Part 1: Domain Specific …In today’s article, I am going to show you various approaches to solving the classic game of Snake with Artificial…towardsdatascience.
comFYI: All below algorithms (along with the full codebase) are available here.
BFS – Breadth First SearchLet’s start with the classic BFS algorithm.
(source: https://www.
raywenderlich.
com/661-swift-algorithm-club-swift-depth-first-search)BFS algorithm does find a correct solution but it’s quite slow, it averages 43.
1 s for a 3×3 board.
DFS – Depth First Search(source: https://www.
raywenderlich.
com/661-swift-algorithm-club-swift-depth-first-search)DFS algorithm doesn’t find a solution, due to the graph’s cyclicity.
If a graph is a cyclic one, DFS tends to go in circles instead of moving towards a solution thus never finishes its execution.
While the BFS algorithm proved to be successful, it was very slow.
Let’s ask ourselves a question – can we do better?Let’s try to improve our search by providing some insights to the algorithm.
Such insights are called heuristics.
You can find more info about them in one of my previous articles.
Hex — Creating Intelligent Adversaries (Part 2: Heuristics & Dijkstra’s Algorithm)Demystifying AI Game Opponentstowardsdatascience.
comWe are going to implement an Iterative Deepening A* (IDA) algorithm which requires a heuristic function that meets specific requirements.
Iterative Deepening A*In order for IDA to work, the heuristic function must be admissible.
It means that it must never overestimate the cost of reaching a goal.
One of the possible heuristic functions that meet this requirement is a Manhattan Distance function.
Manhattan DistanceIn the opposition to the Euclidean distance where we can use Pythagorean Theorem to calculate a distance between the two points on a 2D plane, Manhattan Distance function is calculated by the sum of their absolute coordinates.
Taxicab geometry versus Euclidean distance: In taxicab geometry, the red, yellow, and blue paths all have the same shortest path length of 12.
In Euclidean geometry, the green line has length 6√2 ≈ 8.
49 and is the unique shortest path.
(source: https://en.
wikipedia.
org/wiki/Taxicab_geometry#/media/File:Manhattan_distance.
svg)Since we are sliding only in the [←, →, ↑ , ↓] directions, Manhattan Distance seems like a perfect approximation of ‘how far’ are we from reaching the final state.
For every board state, we are going to calculate its heuristic score, which will imply how good is a given state.
Since for every tile we are calculating the distance from the current state to the final one (number of required moves), the lower the Manhattan Distance value the better.
Now that we have a way to evaluate every board state, let’s feed our search algorithm with this information.
IDA* Graph TraversalThe crucial part in the above algorithm lays in the 3rd line where we are truncating nodes that are eitherwinning – great, we have found a solution!orworse than the current cost estimation (threshold) – no need in exploring branches that can only be worse than our current estimation.
After above evaluation, IDA* behaves similarly to the DFS algorithm.
IDA* does find a solution in ~0.
51 s on average, on a 3×3 board.
It’s about 86 times faster thane BFS!What’s next?We have proved that in certain circumstances we can improve classic search algorithms with heuristic functions and come up with significantly faster and more efficient solutions.
I encourage you to experiment with these algorithms and try to implement them on a larger 4×4 board.
Feel free to share your solutions!Don’t forget to check the project’s github pagegsurma/sliding_puzzleSwift implementation of the Sliding Puzzle game with Iterative Deepening A* AI Solver.
– gsurma/sliding_puzzlegithub.
comand iOS game.
Sliding Puzzle – Board GameRead reviews, compare customer ratings, see screenshots, and learn more about Sliding Puzzle – Board Game.
Download…itunes.
apple.
comQuestions?.Comments?.Feel free to leave your feedback in the comments section or contact me directly at https://gsurma.
github.
io.
.