LiveCode LessonsHow To - Step-By-Step Guides To Tasks In LiveCode Creating an 8-puzzle gameHow do I Tell the Computer to Solve the 8-Puzzle Game Using A*?

How do I Tell the Computer to Solve the 8-Puzzle Game Using A*?

This lesson introduces the Heuristic Search Algorithm A* (A Star) and uses it to solve the 8-Puzzle. A high level discussion of key algorithm components is given, and code samples are provided. Further research into the A* algorithm is strongly advised.

 

Introduction

Prior knowledge of lesson How do I Create an 8-Puzzle Game?  is essential and an understanding of lesson How to I Tell the Computer to Solve the 8-Puzzle Game? would be an advantage. The brute force algorithm discussed in How to I Tell the Computer to Solve the 8-Puzzle Game? is not relevant to this lesson but should provide you with an alternative view on how to solve puzzles like the 8-Puzzle.

A* (A Star) is a state space search algorithm that makes informed judgements about the cost involved in solving the puzzle. Two fundamental values feed into assessing the cost of a particular move on the board:

g: is the number of tiles that have moved to reach a board state that is being assessed

h: is the estimated cost to solve the board state that is currently being assessed

g can be calculated accurately by counting the number of moves we have already taken.

h is calculated using a heuristic that provides an underestimating cost to solve the game. The heuristic we use here is called the manhattan distance and calculates by how many squares a tile is displaced from the location that the tile would have to be in to form part of the winning board state.

This gives us the following cost assessment for any state in the search space: f = g + h

Using a heuristic to solve the 8-Puzzle, rather than brute force, as described in How to I Tell the Computer to Solve the 8-Puzzle Game? allows us to find a solution to the puzzle in less time. You can test the algorithms side by side to see the performance difference.

Integrating the Functionality

Please update the openStack code from lesson How do I Create an 8-Puzzle Game? with the following openStack code. This adds a Solve button to the board and populates that button with the LiveCode script to run the A* algorithm.

Note: Only one comment and one line of code have been added to the original openStack.

on openStack

# set up the constants for the game type

setGameConstants 3, 3

# remove any previous buttons that may already be on the card

# this prevents us from duplicating existing buttons

repeat while the number of buttons of this card > 0

delete button 1 of this card

end repeat

# create the board buttons

createBoard 50

# write the values onto the buttons

writeButtonLabels sWinningState

# create the space on the board

hide button ("b" & sSpaceButton)

# create the shuffle button

createShuffleButton

# create the solve button

createSolveButton  

# make sure the board cannot be resized

set resizable of me to false

end openStack

The Solve Button

Command createSolveButton creates the Solve button and populates the script that is called when pressing the button. This command also resizes the card on which the game buttons and tiles are placed.

command createSolveButton

# create the shuffle button

new button

set label of button "New Button" to "Solve"

set width of button "New Button" to 60 * sTilesX + sOffset * (sTilesX - 1)

set location of button "New Button" to (60 * sTilesX + sOffset * (sTilesX - 1)) / 2 + 20, \

(60 * sTilesY + sOffset * (sTilesY - 1)) + 96

# populate the button script for the shuffle button

set the script of button "New Button" to \

"on mouseUp" & cr & \

"solvePuzzle 50" & cr & \

"end mouseUp"

set the name of button "New Button" to "Solve"

# resize the board for the buttons

set the width of me to 60 * sTilesX + sOffset * (sTilesX - 1) + 40

set the height of me to 60 * sTilesY + sOffset * (sTilesY - 1) + 126

end createSolveButton

Managing the Solution Process

Command solvePuzzle performs all the steps need to solve the 8-Puzzle. This includes testing whether or not the first board state is already the winning board state, calling the cost function costGH and exploreStates to explore the next potential paths that may lead to a solution. pPadding specifies the amount of space that exists between the top and the left edge of the stack cards and the grid tiles.

command solvePuzzle pPadding

local tStatesToExplore, tExploredStates, tMove

# create the first state to explore and calculate its estimated cost

put "," & boardToBoardState (pPadding) into tStatesToExplore

if manhattanDistance (item 2 of tStatesToExplore) is 0 then

answer "Puzzle is Already Solved!" with "OK"

else

put costGH (tStatesToExplore) & "," & tStatesToExplore into tStatesToExplore

repeat until tStatesToExplore is empty

if manhattanDistance (item 3 of line 1 of tStatesToExplore) is 0 then

repeat for each word tMove in item 2 of line 1 tStatesToExplore

swapButtons sSpaceButton, tMove

end repeat

answer "I Made It!" with "OK"

exit repeat

else

exploreStates tStatesToExplore, tExploredStates

end if

end repeat

end if

end solvePuzzle

Exploring Game States

Command exploreStates takes pointers to two lists of states that are to be explored and that have already been explored. This information is important as it allows the search algorithm to make an informed decision as to whether a new state is better or worse than states that have been visited in the past or states that are to be visited in the future.

command exploreStates @pStatesToExplore, @pExploredStates

local tNewStates, tResult

# get the next possible moves for pStateToExplore

put getNewStatePaths (line 1 of pStatesToExplore) into tNewStates

# move the state path that is being explored to pExploredStates

if pExploredStates is not empty then

put cr after pExploredStates

end if

put line 1 of pStatesToExplore after pExploredStates

# remove the state path that is being explored from pStatesToExplore

put line 2 to -1 of pStatesToExplore into pStatesToExplore

# prune the existing explored and unexplored search space

pruneStateSpace tNewStates, pStatesToExplore, pExploredStates

# sort pStatesToExplore so the cheapest path is located at the beginning

sort lines of pStatesToExplore numeric by item 1 of each  

end exploreStates

Getting New States

Function getNewStatePaths produces a list of possible states that can be reached by moving one tile from the most recent state of pPath. pPath is the only parameter passed to this function. All possible next steps are returned by tResult.

function getNewStatePaths pPath

local tPossibleMove, tNewPath, tResult

# we are testing for all possible tile moves

# from the most recent state of the current path

repeat with tPossibleMove = 0 to sSpaceButton - 1

put deriveNextState (pPath, tPossibleMove, sSpaceButton) into tNewPath

if tNewPath is not empty then

if tResult is not empty then

put cr after tResult

end if

put tNewPath after tResult

end if

end repeat

return tResult

end getNewStatePaths

Generating a New State for an Existing Path

Function deriveNextState takes three arguments and tries to add a new state to the path that is passed in by the argument pCurrentPath. pSwap1 and pSwap2 are the tiles that are to be swapped in order to create the new state. If tiles pSwap1 and pSwap2 cannot be swapped, then deriveNextState returns empty.

pCurrentPath and the non empty tResult are comma delimited strings with item 1 containing the current cost f of the path, item 2 containing the individual moves that can later be replayed when solving the 8-Puzzle and items 3 to n containing the individual board states that make up the path that is being explored.

function deriveNextState pCurrentPath, pSwap1, pSwap2

local tHorizontal, tVertical, tButton1H, tButton2H, \

tButton1V, tButton2V, tPossibleNewState, tResult

# get the x and y positions of the two buttons to be swapped

# with respect to the horizontal and vertical game grid of the first

# state of the current path

# we are using item 3 here as item 1 is the cost of the path and

# item 2 contains the moves needed to solve the puzzle

put (wordOffset (pSwap1, item 3 of pCurrentPath) - 1) mod sTilesX into tButton1H

put (wordOffset (pSwap1, item 3 of pCurrentPath) - 1) div sTilesY into tButton1V

put (wordOffset (pSwap2, item 3 of pCurrentPath) - 1) mod sTilesX into tButton2H

put (wordOffset (pSwap2, item 3 of pCurrentPath) - 1) div sTilesY into tButton2V

# determine if the two buttons can be swapped,

# if so create a new state that represents the swap

if ((tButton1H - tButton2H is 0) and (abs (tButton1V - tButton2V) is 1)) or \

((tButton1V - tButton2V is 0) and (abs (tButton1H - tButton2H) is 1)) then

put item 3 pCurrentPath into tPossibleNewState

replace pSwap1 with "X" in tPossibleNewState

replace pSwap2 with pSwap1 in tPossibleNewState

replace "X" with pSwap2 in tPossibleNewState

# check here if we have a loop in the path and reject it if so

if itemOffset (tPossibleNewState, item 3 to -1 of pCurrentPath) is 0 then

# add the new state to the front of other states

put tPossibleNewState & "," & item 3 to -1 of pCurrentPath into tResult

# add the move that got us to this new state to the list of moves we made so far

if item 2 of pCurrentPath is empty then

put pSwap1 & "," & tResult into tResult

else

put item 2 of pCurrentPath && pSwap1 & "," & tResult into tResult

end if

put costGH (tResult) & "," & tResult into tResult

end if

end if

return tResult

end deriveNextState

Calculating f = g + h

Function costGH calculates the cost f for a given path pPath.

function costGH pPath

local tMove, tResult

# calculate g for pPath

repeat for each word tMove in item 1 of pPath

add 1 to tResult

end repeat

# calculate h for pPath and add it to g

add manhattanDistance (item 2 of pPath) to tResult

return tResult

end costGH

 

Pruning the Search Space

Command pruneStateSpace take a set of paths that are to be explored and tries to add them to pStatesToExplore. A successful add depends on whether or not a potentially better path already exists in pStatesToExplore or pExploredStates.

Note: pStatesToExplore and pExploredStates are passed in by reference. This means that any changes made to their content will be permanent and affects their use outside the scope of this command.

command pruneStateSpace pNewPaths, @pStatesToExplore, @pExploredStates

local tPath, tStatesToExploreDuplicate, tExploredStatesDuplicate, tAddFlag

repeat for each line tPath in pNewPaths

put false into tAddFlag

# find out if the new state to explore exists

# as a head in one of the already explored states

put stateMatch (tPath, pExploredStates) into tExploredStatesDuplicate

# find out if the new state to explore exists

# as a head in one of the states that are still to be explored

put stateMatch (tPath, pStatesToExplore) into tStatesToExploreDuplicate

if tExploredStatesDuplicate is false and tStatesToExploreDuplicate is false then

# if we found no match, then set a flag to add the new path

# to the paths that are to be explored

put true into tAddFlag

else if tExploredStatesDuplicate is not false and item 1 of tPath < \

item 1 of line tExploredStatesDuplicate of pExploredStates then

# if we found a match with the states we already explored and the new path

# is cheaper then remove the matched state from the explored states

# and set the flag to add the new path to the paths that are to be explored

delete line tExploredStatesDuplicate of pExploredStates

put true into tAddFlag

else if tStatesToExploreDuplicate is not false and item 1 of tPath < \

item 1 of line tStatesToExploreDuplicate of pStatesToExplore then

# if we found a match with the states we have not yet explored and the new

# path is cheaper then remove the matched state from the unexplored states

# and set the flag to add the new path to the paths that are to be explored

delete line tStatesToExploreDuplicate of pStatesToExplore

put true into tAddFlag

end if

# if tAddFlag is set then add the new path to the paths that are to be explored

# any new paths that exist for which tAddFlag is not set to true are skipped

if tAddFlag is true then

if pStatesToExplore is not empty then

put cr after pStatesToExplore

end if

put tPath after pStatesToExplore

end if

end repeat

end pruneStateSpace

Function stateMatch tests whether or not the most recent state in a new path matches one of the most recent states in a list of paths. This function returns false if no match was found or the location where the path match was found.

function stateMatch pPath, pPathList

local tPath, tLineCount

repeat for each line tPath in pPathList

add 1 to tLineCount

if item 3 of tPath is item 3 of pPath then

return tLineCount

end if

end repeat

return false

end stateMatch

The 8-Puzzle Board (Ready to Play)

The 8-Puzzle Board (Ready to Play)

The puzzle interface from this lesson works in the same way as the puzzle interface from lesson How do I Tell the Computer to Solve the 8-Puzzle?. The only difference is that the label on the Solve button does not change. This is because the search algorithm is iterative, rather than recursive and we are not exploring the search space in a depth first fashion.

2 Comments

Britt Griscom

I'm trying to adapt this algorithm for a 15-puzzle. If the algorithm has to explore a lot of states, it gets extremely slow. I don't need it to find the shortest path to the solution. I just need it to find any solution, quickly.

I think the trouble might be in how it deals with ties. I notice that it spends a lot of time exploring all the different paths that have the same cost. Is there a way for it it to deal with ties differently? That is, maybe when there is a tie, could it just pick one and try to follow it to the solution, even if that solution is sub-optimal? If it could do that, it would probably be a lot faster.

Any help would be much appreciated.

Hanson Schmidt-Cornelius

Hi Britt,

thank you for posting your comments about the A* algorithm for the 8-Puzzle.

This lesson is all about introducing the concept of heuristic search to the LiveCode community. As such I tried to balance the need for sophisticated heuristics with the possible computing resources that are available to individual users.

This algorithm uses the manhattan distance to evaluate how far a specific board state is from the goal state. The manhattan distance is a reasonable approach that is easy to understand and that solves the problem without overestimate the number of moves required. The problem is that the manhattan distance is not very accurate for a whole range of board states, in particular when you have tile reversal situations. For two tiles that have to be swapped to solve the game, the manhattan distance would typically provide a cost of "2" moves. In reality, swapping two tiles around requires many more moves.

You could optimise the performance of this game and the 15 puzzle by finding a heuristic that evaluates the cost of solving a particular games state more accurately. There are a number of research examples on the internet that should be able to help you.

I would look for key words like: "heuristic search 15 puzzle" or "solve 15 puzzle".

If you find an algorithm that does not overestimate the cost of solving the puzzle, but at the same time provides a pretty good estimate, then the A* algorithm should still provide you with the shortest possible path to solving the problem.

Hope this helps.

Kind Regards,

Hanson

Add your comment

E-Mail me when someone replies to this comment