Sliding Puzzle Bot Strategy

Here are some suggestions of strategies to improve your bot's performance.

Estimate how far you are away from a solution

If you estimate how far you are away from a solution this will help you decide which of the possible moves you might take. There are various ways of doing this but one method is to take how many tiles you have in the incorrect place, for example the board shown below would score 5 as tiles 7,6,2,8,4 are in the incorrect place:

spg_example_strategy.png

When scoring you also include the blank tile who's correct position is in the bottom right hand corner.

Use an A* Search Algorithm

Construct a tree of paths starting from the initial board and explore each node based upon the moves performed so far and the estimate to the correct solution.

We define a state of the game to be the board position, the number of moves made to reach the board position, and the estimate to the correct solution. First, insert the starting state into a priority queue. Then, delete from the priority queue the state with the minimum number of moves plus the estimate to the correct solution, and insert onto the priority queue all neighboring states (those that can be reached in one move). Repeat this procedure until the state dequeued is the goal state.

Starting priority queue

State ID Board Number of Moves Estimate to Correct Solution
1 [[1,2,3],[4,0,5],[7,8,6]] 0 3

Remove the state with the minimum number of moves plus the estimate to the correct solution and insert onto the queue all moves that can be reached in one move:

State ID Board Number of Moves Estimate to Correct Solution
1 [[1,0,3],[4,2,5],[7,8,6]] 1 4
2 [[1,2,3],[4,5,0],[7,8,6]] 1 2
3 [[1,2,3],[4,8,5],[7,0,6]] 1 4
4 [[1,2,3],[0,4,5],[7,8,6]] 1 4

Again remove the state with the minimum number of moves plus the estimate to the correct solution, in this case line ID 2. Insert onto the queue all the moves from state ID 2 that can be reached in one move:

State ID Board Number of Moves Estimate to Correct Solution
1 [[1,0,3],[4,2,5],[7,8,6]] 1 4
3 [[1,2,3],[4,8,5],[7,0,6]] 1 4
4 [[1,2,3],[0,4,5],[7,8,6]] 1 4
5 [[1,2,3],[4,5,6],[7,8,0]] 2 0
6 [[1,2,0],[4,5,3],[7,8,6]] 2 3

The state removed now is the correct solution as it has an estimate of 0 so stop processing and submit steps.

A more in-depth explanation of this algorithm can be found here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License