this question is surely worth the 200 points. To answer your question right away: A* *CAN* be used to solve the 15 puzzle. However it might not be the best approach; I'll get to that in a minute.
As this is going to become a bit lengthy let me offer you a table of contents so you don't get lost:
1. Breaking down the problem
2. Dijkstra's algorithm
3. Dijkstra + knowledge -> A*
4. Can you picture this?
All code priveded is optimized for readablity only.
1. Breaking down the problem:
As with all problems you'd like to present to a computer you will have to transform it, so that a machine can 'understand' it. Thus transformation usually means abstraction of the nature of the problem.
Let's go back to the 15 puzzle. There are 4 pieces of information to describe the entire problem. A set of states (S), a set of transitions (T) to move from one state to another, a start state (start), and a goal state (goal).
Set of states (S): this is a machine-readable description of all possible constellations of the puzzle. I'd suggest using a 4x4 array
char tile[16];
to describe the layout, where tile[0] is the top left corner, tile[3] the top right corner, tile[15] the bottom right corner. Fill this array with the respective number of the tile and mark the empty spot with a '0'. This way you have just created the start state (start). Your goal state (goal) is {1, 2, 3, ..., 14, 15, 0}.
Set of transitions (T): this refers to sliding pieces on the board to get from one layout to another. For any state of the puzzle this can be 2, 3, or 4 legal moves (2 at corners, 3 on edges, and 4 on the interior). We'll use
char dir;
for transitions and declare the directions as follows:
right: 00000001b (1)
top: 00000010b (2)
left: 00000100b (4)
bottom: 00001000b (8)
Information on which tile is to be moved can be gathered from the direction code (d) and the current state (cs). Let's say d == 4 (left) and cs = { 0, .... } then the 2nd tile (tile[1]) is to be moved.
Let's take a step back and see what we have so far: We know WHAT the puzzle looks like (start), we know WHERE we are headed (goal), and we know HOW to walk (set of transitions T). Still with me? Good!
2. Dijkstra's algorithm
With all the WHAT, WHERE, and HOW we still don't know WHICH step at any give puzzle state will get us closer to our goal. There aren't many means to choose from when there is nothing to decide upon, so let's face it: a situation like this calls for brute force. Beginnig with the start state we do the following:
a.) set cs = start
b.) if( cs == goal ) return GOAL_REACHED;
c.) for each legal direction set cs = transform( cs, dir ) and goto b.)
[transform( const char[16]& state, const char dir ) returns new puzzle state after sliding the appropriate tile into the specified direction]
Simplified - and not quite accurate, I admit - this is Dijkstra's algorithm: Check for ALL possibilities until we reach the goal. Cool! We've reached the goal then? Technically speaking, yes, cs == goal. From a human perspective, though, the interest is more towards 'can you tell me how?'. Damn, we forgot the housekeeping. We need some structure to hold information on where we came from.
struct node {
char tile_state[16];
char dir_parent;
};
And we need some means to 'remember' where a possible parent of a parent came from. What about some sort of long term memory that stores all puzzle states we've examined so far? Let's just call it closed (as in 'closed for examination'):
#include <list>
std::list<node> closed;
Let's refine the algorithm above:
a.) node n = {start, 0};
b.) if( n.tile_state == goal ) return solution;
c.) for each legal dir { open.push_back( n ); n.tile_state = transform( n.tile_state, dir ); n.dir_parent = rev_dir( dir ); goto b.); }
Now we have all the information to construct a solution. Starting at goal, we check for equality with start. If not, we retrieve node n from closed, where n.tile_state == cs, and append n.dir_parent to our solution list, ... The list is still doubly inverted. All we have to do is to change the order from back to front and reverse each direction. Voila - here it is.
Well, possibly, but not necessarily. We did not take any precautions to avoid ending up in an endless loop (i.e. moving a tile to the left and moving it to the right again, then left, right, left, right, ...) And possibly we could use the little information we have gathered on our way to speed up calculation. Let's redesign our node structure:
class node {
char tile_state[16];
char dir_parent;
int move_count;
};
move_count is set to 0 for the start node and increased by 1 for each expansion. We'll also be using a short term memory list that holds all nodes open for examination and call it open. Before expanding a node the open list is sorted in ascending order, so we'll expand all nodes whose tile_state can be reached with one move, then those, that can be reached in two moves, and so on.
To finish this section, here is the more complete algorithm in pseudo-code:
a.) node n = { s, 0, 0 }; open.push_back( n );
b.) if( 0 == open.size() ) return FAILED; // no solution!
c.) open.sort( ASCENDING ); n = open.front(); open.pop_front();
d.) if( n.tile_state == goal ) return solution;
e.) closed.push_back( n );
f.) for( char d = 1; d <=8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node n_new = transform( n.tile_state, d );
if( !closed.find( n_new ) && !open.find( n_new ) ) {
open.push_back( n_new );
}
}
}
g.) goto b.)
Enough for today, my girlfriend needs attention...
The rest will follow tomorrow.
Anyway, let's go over what we have so far. With Dijkstra's algorithm we have a - computationally expensive - method to solve problems given a search space (S, T), a start state (start), and the goal state (goal). Btw. this algorithm can be applied to any problem that can be abstracted to search space, start, and goal. Now why is this approach so computationally expensive? Because the algorithm applied is basically dumb, i.e. it doesn't use any means to decide, which transition seems to be the most promising one to take at any given puzzle state.
3. Dijkstra + knowledge -> A*:
To reduce the effort necessary to find a solution we will have to find some means to favor one transition over another at a given state. For the 15 puzzle there is no actual information to gain from looking at the layout, as far as I can see. So we will have to guess which one of any two given states is closer to our goal. Let's call additional information on a problem 'heuristic' (h). One thing we can be sure about the 15 puzzle is, that if
h = number of tiles at wrong locations
we will need at least h moves (at least 1 move for each incorrect tile) to reach the goal. How can we use this information to reduce the amount of searching necessary to find a solution? Let's go back to Dijkstra's algorithm. Instead of sorting our open list with respect to the number of moves taken so far, let's take our estimate on the 'distance' from the goal into account. While Dijkstra's sorting predicate is
f = g (g = costs so far)
we'll use costs + estimate
f = g + h
and call this 'new' algorithm A*. So the difference between Dijkstra's algorithm and A* is, that Dijkstra is searching indifferent in all possible directions whereas A* is searching in favor of those directions, that are presumably closer to the goal. Bare in mind though that our presumtions are based on guessing only.
3.1. Small guess-ology:
It appears to be logical that A* will find a solution faster than Dijkstra if our presumtions are all correct. But what happens if not? What if only some of them are wrong? Let's discover the different degrees of, hmm, wrongness? wrongity? anyone? If our estimated distance is wrong it can be either too large or too small. Overestimating is dangerous in that we may be skipping potential solutions. Understimating is not only harmless, but essential to ensure that the returned solution requires the least number of transitions to be reached.
3.2. It's all in the heuristics:
Let's check the heuristic above against this. It is obvious that if n tiles are in wrong locations it takes n moves at best to reach the solution. Since A* uses the heuristic as a decisive means to cut down computational effort, the heuristic's quality is the key component to success. If it comes close to the actual effort it unleashes A*'s power. In fact, if every guess is correct, i.e. we have a perfect heuristic, A*'s very first try at the puzzle will return the best possible solution. However, our heuristic only returns values in the range of [0..15] and becomes somwhat void after about 100 moves. In the introduction I said that 'it might not be the best approach'. There is some computational overhead involved in calculating the heuristic. In our case this might not really matter, however, if our chosen heuristic is very poor, A* can become even more timeconsuming than Dijkstra! In other words: While Dijkstra will find the best solution, A*'s heuristic is in charge of the time spent to discover it.
So what do we have now? In section 1 we found a way to present the problem in a machine-readable form. Section 2 introduced a method to blindly search for a solution. In section 3 we discovered a possibility to bring orientation into the darkness. 'Yeah, I know, but this is all theoretical. Don't you have a more specific explanation, a more visual one?' I hear you ask.
4. Can you picture this?:
Well, no. The 1-dimensionality of the 15 puzzle seems to be ungraspable for my mind. If you don't mind, let's leave this problem behind and look at something different. Pretend we're implementing pathfinding strategies for a tile-based RTS-game. The search space is defined by our grid consisting of w * h tiles. In this case the open list can be depicted as the outer border of all tiles that have been examined in search of a solution. The closed list contains all tiles 'inside' the open list. When applying Dijkstra's algorithm to find the shortest path from A to B, the search radius will extend in a circular fashion around A (if we allow diagonal moves, otherwise it would be a square) until the border touches B. Thus the open list forms a circle, and closed contains everything inside forming a disc. A*'s search pattern is more irregular and extends more towards the presumably best path. If we have a perfect heuristic the closed list will be nothing but a single line containing the path with the open list surrounding it. In a worst case scenario though, after an A*-search has completed, the closed list can contain all positions, but the goal B, which would be the last one in the open list. I hope this can help to clarify why an A* equipped with a bad - even though correctly underestimating - heuristic can perform worse than Dijkstra.
This is it. For now. Give me a day and I'll come up with some code. If anyone cares about, let me know and I'll mail it to you. I'd like to post it here, but without a fixed-font (and possibly syntax highlighting) it doesn't really turn out readable. If you have questions, insults, comments, ... let me know.
regards,
.:fl0yd:.
------------------------------------------------------------------------------------
errata (guess noone is perfect, oh well...):
c.) for each legal dir { open.push_back( n ); n.tile_state = transform( n.tile_state, dir ); n.dir_parent
= rev_dir( dir ); goto b.); }
should be:
c.) closed.push_back( n );
++n.move_count;
for each legal dir {
n.tile_state = transform( n.tile_state, dir );
if( !closed.find( n ) ) { // == if not already visited
n.dir_parent = rev_dir( dir );
goto b.)
}
}
return FAILED; // no solution
f.) for( char d = 1; d <=8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node n_new = transform( n.tile_state, d );
if( !closed.find( n_new ) && !open.find( n_new ) ) {
open.push_back( n_new );
}
}
}
should be:
f.) ++n.move_count;
for( char d = 1; d <= 8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node node_new( transform( n.tile_state, d ), rev_dir( d ), n.move_count );
if( !closed.find( n_new ) ) // not visited yet
if( !open.find( n_new ) ) // and not already in examination queue
open.push_back( n_new );
else // if already in examination queue
if( *open.find( n_new ).move_count > n_new.move_count )
*open.find( n_new ) = n_new; // if faster to reach replace it
}
}
disclaimer: no animals were harmed during the course this production
Not quite done benchmarking yet. However for the special case of start_state =
[[ 0, 1, 2, 3]
[ 6, 7, 8, 4]
[ 5, 9, 10, 11]
[ 13, 14, 15, 12]]
Dijkstra's algorithm will find the 12-move solution in about 8 minutes, while A* will do it in less than a second!!!
Just in case: The solution is: left, left, left, up, right, right, right, up, left, left, left, up.
.:fl0yd:.
p.s.: updates will follow, as soon as i implemented the rest of the benchmarking stuff.
0
With monday.comâ€™s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.
Here is the code I wrote when I was a 1'st degree student
in AI course, It implements A* on 8-puzzle...
The puzzle is represented by a LONG type 9 digits number.
As the code is self documented,
Ask me please any question.
class node
{
public:
long puzzle;
int val;
bool WasOpened;
int TreeLevel;
};
class puzzle
{
int WhereIsDigitInNum(int,long);
node list[MaxSize];
int ListIndex, CurrentTreeLevel;
long original, goal;
int MDistance(long,long);
void ReturnSons(long,long&,long&,long&,long&);
long swap(long, int, int);
void SolvePuzzle();
void InsertToList(long,long,long,long);
long FindBest();
//int LinerConflict(long);
public:
puzzle();
};
puzzle::puzzle()
{
int i;
float AvPath=0, AvListIndex=0;
goal=123456789;
for (i=0; i<NumberOfPuzzles; i++)
{
ListIndex=0;
CurrentTreeLevel=-1; // first level is zero...
long puzzle::FindBest()
{
int min, i, j, mini;
bool found=false;
// set the first minimal value
for (i=0; i<ListIndex && !found; i++)
if (list[i].WasOpened==false)
{
found=true;
min=list[i].val;
mini=i;
}
// search the most minimal value
for (j=i; j<ListIndex; j++)
if ((list[j].val<=min) && (list[j].WasOpened==false))
{
min=list[j].val;
mini=j;
}
void puzzle::InsertToList(long a,long b,long c,long d)
{
long arr[4];
int index=0, i;
bool found;
if (a)
{
arr[index]=a;
index++;
}
if (b)
{
arr[index]=b;
index++;
}
if (c)
{
arr[index]=c;
index++;
}
if (d)
{
arr[index]=d;
index++;
}
index--;
while (index>=0)
{
found=false;
for (i=0; i<ListIndex && !found; i++)
if (arr[index]==list[i].puzzle)
found=true;
// if not found OR found with better Mdistance.
if ((found && CurrentTreeLevel+1+MDistance(arr[index],goal)<list[i-1].val) || (!found))
{
list[ListIndex].puzzle=arr[index];
list[ListIndex].WasOpened=false;
list[ListIndex].TreeLevel=CurrentTreeLevel+1;
list[ListIndex].val=list[ListIndex].TreeLevel+MDistance(arr[index],goal);
ListIndex++;
}
index--;
}
}
long puzzle::swap(long num,int a, int b)
{
long v[10];
int i, temp;
for (i=9; i>=1; i--)
{
v[i]=num%10;
num/=10;
}
temp=v[a];
v[a]=v[b];
v[b]=temp;
num=0;
for (i=1; i<=9; i++)
{
num*=10;
num+=v[i];
}
return num;
}
int puzzle::WhereIsDigitInNum(int digit,long num)
{
bool found=false;
int DigitFromNum, pos=9;
while (!found && num)
{
DigitFromNum=num%10;
if (digit==DigitFromNum)
found=true;
else
{
pos--;
num/=10;
}
}
// shift with right
if (SpacePos%3==0)
sr=0;
else
sr=swap(num,SpacePos,SpacePos+1);
// shift with left
if (SpacePos%3==1)
sl=0;
else
sl=swap(num,SpacePos,SpacePos-1);
// shift with upper
if (SpacePos<4)
su=0;
else
su=swap(num,SpacePos,SpacePos-3);
// shift with lower
if (SpacePos>6)
sd=0;
else
sd=swap(num,SpacePos,SpacePos+3);
}
int puzzle::MDistance(long org, long tar)
{
int i,MSum=0,OrgPos,TarPos,OrgRow,TarRow,OrgLine,TarLine;
for (i=2; i<=9; i++)
{
OrgPos=WhereIsDigitInNum(i,org);
TarPos=WhereIsDigitInNum(i,tar);
OrgLine=(OrgPos-1)/3;
TarLine=(TarPos-1)/3;
OrgRow=OrgPos%3;
if (OrgRow==0)
OrgRow=3;
TarRow=TarPos%3;
if (TarRow==0)
TarRow=3;
MSum+=abs(OrgLine-TarLine)+abs(OrgRow-TarRow);
}
//MSum+=LinerConflict(org);
return MSum;
}
/*
int puzzle::LinerConflict(long puzzle)
{
int OrgPos,NextPos,OrgRow,NextRow,OrgLine,NextLine,DownPos,DownLine, DownRow,i,r=0;
for (i=2; i<=8; i++)
{
OrgPos=WhereIsDigitInNum(i,puzzle);
NextPos=WhereIsDigitInNum(i+1,puzzle);
OrgLine=(OrgPos-1)/3;
NextLine=(NextPos-1)/3;
OrgRow=OrgPos%3;
if (OrgRow==0)
OrgRow=3;
NextRow=NextPos%3;
if (NextRow==0)
NextRow=3;
if ((OrgLine==NextLine) && (OrgRow-NextRow==1))
r+=2;
if (i<=6)
{
DownPos=WhereIsDigitInNum(i+3,puzzle);
DownLine=(DownPos-1)/3;
DownRow=DownPos%3;
if (DownRow==0)
DownRow=3;
if ((OrgRow==DownRow) && (OrgLine-DownLine==1))
r+=2;
}
Thanks a heap for NOT responding to my post at all. Since there was no feedback whatsoever I won't post any results nor will I share my src -- btw, it's way more structured and speed optimized than yairy's "1'st degree student in AI course"-implementation, with tons of information I gathered when working in the gaming industry. Too bad...
Yairy, you don't talk about your heuristic - the heart and soul of any A*-implementation. Looks like you're using the sum of all tile-distances to their respective goal-positions. However, this will only speed up the last portion of the search and MAY significantly slow down search in more complex situations.
somewhat disappointed,
.:fl0yd:.
ps: I don't believe that posting src-code without any explanation is helpful. It certainly doesn't do justice to "Can anyone show me how to do this in details".
Don't be mad at me.
I am only tring to help.
I read your answer and agree with most of it.
I think you expanded the subject far too long.
I didn't attached a document cause I wanted to filter
fox that just know to cut and paste.
I still think is a good program.
I used Manhatten-distance (total sum of distnces) to evalute f().
It a good heuristic, not perfect.
but it apply the rules and very fast to calculate.
Maybe it can be even updated instead of re-calculating from father to sons.
I'll be very interested to hear how you "speed optimized"
the algorithm.
ahhhh, crappy internet connections at our university pool, didn't mean to say nothing :(
yairy,
sorry, I got a little carried away. I hope I didn't insult you, I just felt that posting uncommented src isn't too helpful. I'll have to stick to my principles though and won't post any of my own src. However, I can point you in the right direction. First of all, using long's might seem reasonable at first sight, however, I used a char[16] instead. Could have packed 2 tiles into one byte and used char[8] with a bit of overhead for access. Using long's has two backdraws: a.) if you use base 10 for encoding you won't make life easy from a computer's point of view - try using base 2 whenever possible. b.) it's dangerous, as you cannot make any assumptions on the size. long's could very well be 1 byte long and still comply with the ANSI standard. [sizeof( char ) <= sizeof( long )].
Btw. you're solving an 8-puzzle, not a 15-puzzle...
As far as speed is concerned your LinerConflict and MDistance make excessive use of '/' and '%', both are computationally expensive, with '%' being even worse than '/'. If you want speed, get rid of those first.
you say that manhatten distance is a good heuristic. Like I said in my previous (non-empty) post, it only speeds up the last portion of the search, but tends to slow down the rest of it in complex situations.
Hope that helps, bare with me, sorry, again,
.:fl0yd:.
hi, all, can i talk with you guys? i'm kinda lost in a star algorithm, i've been studying pathfinding algorithm from bryan stout's tutorial, i've tried to imitate his program in msvc++ but i'm wholly stuck in best-first search, and the a* algorithm, well... my dijkstra's algorithm runs in a bit different manner than his'... i guess, there's something wrong with the cost function (for dijkstra) and the heuristic estimate (for a* algo)... can you help me out guys? can we get in contact? my email is copet@lycos.com
ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.
One of a set of tools we're offering as a way to say thank you for being a part of the community.
this question is surely worth the 200 points. To answer your question right away: A* *CAN* be used to solve the 15 puzzle. However it might not be the best approach; I'll get to that in a minute.
As this is going to become a bit lengthy let me offer you a table of contents so you don't get lost:
1. Breaking down the problem
2. Dijkstra's algorithm
3. Dijkstra + knowledge -> A*
4. Can you picture this?
All code priveded is optimized for readablity only.
1. Breaking down the problem:
As with all problems you'd like to present to a computer you will have to transform it, so that a machine can 'understand' it. Thus transformation usually means abstraction of the nature of the problem.
Let's go back to the 15 puzzle. There are 4 pieces of information to describe the entire problem. A set of states (S), a set of transitions (T) to move from one state to another, a start state (start), and a goal state (goal).
Set of states (S): this is a machine-readable description of all possible constellations of the puzzle. I'd suggest using a 4x4 array
char tile[16];
to describe the layout, where tile[0] is the top left corner, tile[3] the top right corner, tile[15] the bottom right corner. Fill this array with the respective number of the tile and mark the empty spot with a '0'. This way you have just created the start state (start). Your goal state (goal) is {1, 2, 3, ..., 14, 15, 0}.
Set of transitions (T): this refers to sliding pieces on the board to get from one layout to another. For any state of the puzzle this can be 2, 3, or 4 legal moves (2 at corners, 3 on edges, and 4 on the interior). We'll use
char dir;
for transitions and declare the directions as follows:
right: 00000001b (1)
top: 00000010b (2)
left: 00000100b (4)
bottom: 00001000b (8)
Information on which tile is to be moved can be gathered from the direction code (d) and the current state (cs). Let's say d == 4 (left) and cs = { 0, .... } then the 2nd tile (tile[1]) is to be moved.
Let's take a step back and see what we have so far: We know WHAT the puzzle looks like (start), we know WHERE we are headed (goal), and we know HOW to walk (set of transitions T). Still with me? Good!
2. Dijkstra's algorithm
With all the WHAT, WHERE, and HOW we still don't know WHICH step at any give puzzle state will get us closer to our goal. There aren't many means to choose from when there is nothing to decide upon, so let's face it: a situation like this calls for brute force. Beginnig with the start state we do the following:
a.) set cs = start
b.) if( cs == goal ) return GOAL_REACHED;
c.) for each legal direction set cs = transform( cs, dir ) and goto b.)
[transform( const char[16]& state, const char dir ) returns new puzzle state after sliding the appropriate tile into the specified direction]
Simplified - and not quite accurate, I admit - this is Dijkstra's algorithm: Check for ALL possibilities until we reach the goal. Cool! We've reached the goal then? Technically speaking, yes, cs == goal. From a human perspective, though, the interest is more towards 'can you tell me how?'. Damn, we forgot the housekeeping. We need some structure to hold information on where we came from.
struct node {
char tile_state[16];
char dir_parent;
};
And we need some means to 'remember' where a possible parent of a parent came from. What about some sort of long term memory that stores all puzzle states we've examined so far? Let's just call it closed (as in 'closed for examination'):
#include <list>
std::list<node> closed;
Let's refine the algorithm above:
a.) node n = {start, 0};
b.) if( n.tile_state == goal ) return solution;
c.) for each legal dir { open.push_back( n ); n.tile_state = transform( n.tile_state, dir ); n.dir_parent = rev_dir( dir ); goto b.); }
Now we have all the information to construct a solution. Starting at goal, we check for equality with start. If not, we retrieve node n from closed, where n.tile_state == cs, and append n.dir_parent to our solution list, ... The list is still doubly inverted. All we have to do is to change the order from back to front and reverse each direction. Voila - here it is.
Well, possibly, but not necessarily. We did not take any precautions to avoid ending up in an endless loop (i.e. moving a tile to the left and moving it to the right again, then left, right, left, right, ...) And possibly we could use the little information we have gathered on our way to speed up calculation. Let's redesign our node structure:
class node {
char tile_state[16];
char dir_parent;
int move_count;
};
move_count is set to 0 for the start node and increased by 1 for each expansion. We'll also be using a short term memory list that holds all nodes open for examination and call it open. Before expanding a node the open list is sorted in ascending order, so we'll expand all nodes whose tile_state can be reached with one move, then those, that can be reached in two moves, and so on.
To finish this section, here is the more complete algorithm in pseudo-code:
a.) node n = { s, 0, 0 }; open.push_back( n );
b.) if( 0 == open.size() ) return FAILED; // no solution!
c.) open.sort( ASCENDING ); n = open.front(); open.pop_front();
d.) if( n.tile_state == goal ) return solution;
e.) closed.push_back( n );
f.) for( char d = 1; d <=8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node n_new = transform( n.tile_state, d );
if( !closed.find( n_new ) && !open.find( n_new ) ) {
open.push_back( n_new );
}
}
}
g.) goto b.)
Enough for today, my girlfriend needs attention...
The rest will follow tomorrow.
regards,
.:fl0yd:.