Jump to content

  • Log In with Google      Sign In   
  • Create Account

Solving The 8 Puzzle Using Genetic Algorithm


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 __Daedalus__   Members   -  Reputation: 480

Like
Likes
Like

Posted 17 January 2004 - 02:57 AM

Hello, I''ve been reading the "AI Techniques For Game Programmers" book and am trying to think up a way to solve the infamous 8 puzzle (eight squares numbered 1-8 and a blank square in a 3X3 grid) using a genetic algorithm. Can someone give me an idea of the best way encode the chromosone? I was thinking of one chromosone containing a list of structures that identify a tile number and a direction to try moving it in. If the instruction can''t be followed (e.g. not moving in to the space) then it is ignored ad the next one tried. A fitness could be applied depending on how many of the tiles are left in the right place at the end. I''m not sure of how many instructions to have as a maximum for the chromosone though. I''d appreciate some idead on how would you tackle this problem?

Sponsor:

#2 SiCrane   Moderators   -  Reputation: 9670

Like
Likes
Like

Posted 17 January 2004 - 04:25 AM

At any given point, you can only move a tile into the blank spot, so really, each link only needs to be a direction. That direction would be which tile to move compared to the current blank spot. That should cut down the number of different possibilities by an order of magnitude.

#3 Nekhmet   Members   -  Reputation: 132

Like
Likes
Like

Posted 17 January 2004 - 08:50 AM


Do you want to evolve a solution to a particular layout, or do you want to evolve an algorithm that can solve any layout?

Either way, this doesn't sound feasible to me, now that I think about it. For evolution to work, you need a selection criterion that judges some species "better" than others. However, for 8-puzzle, I can't think of any "better" metric, other than just "works" or "doesn't work". If you were just solving a single layout, and not trying to do evolutionary algorithm design, you could measure the number of tiles in the right place... but that wouldn't work, because in 8-puzzle, it's easy to get the first 7 tiles in the right place, but getting that last tile in place usually requires that you move everything.

- Josh


[edited by - Nekhmet on January 17, 2004 3:55:40 PM]

#4 BiTwhise   Members   -  Reputation: 134

Like
Likes
Like

Posted 17 January 2004 - 09:17 AM

couldn''t you use the number of moves used to finish the puzzle as a measurement of fitness? And have a deadlock prevention, saying more than N moves and the solver dies..

#5 RenderTarget   Members   -  Reputation: 398

Like
Likes
Like

Posted 17 January 2004 - 09:27 AM

I get the feeling that on most generations, almost all of the species will die at >N moves. GAs work best when you can find out in short order how close you came to success, whether you did succeed or not.

But, why ask? Why not just try it out?

I like pie.

#6 Timkin   Members   -  Reputation: 864

Like
Likes
Like

Posted 18 January 2004 - 04:06 PM

This problem has been attempted before... ''google'' for more information. You can use, for example, the inverse average displacement of each tile from its desired location as a measure of fitness (use average Manhattan distance). As for a chromosome, it should be a sequence of moves relating to the open square. For example, label the four squares adjacent to the open square as N,S,E & W. A move of N would be ''move the northern tile into the open square''. Not all moves will be legitimate. You can either discard that chromosome as defective (giving it an appropriate fitness) or ignore that suggested move, finishing the rest of the decoding of the chromosome. Mating is a little tricky with variable length chromosomes, but again there''s plenty of literature out there on techniques for GAs with variable length chromosomes.

Ultimately though, this puzzle is trivially solved with a traditional search algorithm, so ask yourself is applying a GA to this problem the right thing to do.

Cheers,

Timkin

#7 Ferretman   GDNet+   -  Reputation: 276

Like
Likes
Like

Posted 18 January 2004 - 05:24 PM

quote:
Original post by Timkin
This problem has been attempted before... ''google'' for more information.


Some sites from the references on GameAI.Com would include:

http://www.geocities.com/jheyesjones/astar.html

and

http://sciris.shu.edu/~borowski/Puzzle/

Hope that helps.




Ferretman

ferretman@gameai.com

From the High Mountains of Colorado

GameAI.Com


#8 edotorpedo   Members   -  Reputation: 198

Like
Likes
Like

Posted 19 January 2004 - 01:39 AM


Hey!

I''ve tried that before. Each chromosome had the length of the estimated number of moves for the solution, and was made up of a sequence of moves (NSWE). If a move within the chromosome wasn''t valid, it was discarded. This way it could still find the shortest path even if the chromosome length exceeded the least amount of moves.

As a fitness function I used the famous ''Manhatten'' distance, which was very simple and quite effective:


float SlideP::getFitnessValue() { // return how good this field is


int value;
int startRow,startColumn;
float fitness = 0;

for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {

value = getValue(i,j) - 1 ;

if (value != emptyValue - 1) { // do not include empty spot in valuation

startRow = (int) value / dim;
startColumn = value % dim;
fitness += abs(startRow - i);
fitness += abs(startColumn - j);
}

}
}

// with a higher value you get lower fitness,

// because you are further away from the solution

if (fitness == 0)
return 100.0f;
else
return 1.0f/fitness;

}


This function evaluated the fitness of an instance of SlideP (a 3x3 field). Dim = 3 in this example.

This code of mine worked quite well. Note that I coded this GA for the 8-puzzle just to apply a GA to a simple problem.

If you really want to solve the 8-puzzle use A* (or backtracking). If you want the code (it''s a VB project with a C++ DLL for calculations) let me know.

Edo


#9 __Daedalus__   Members   -  Reputation: 480

Like
Likes
Like

Posted 19 January 2004 - 11:32 AM

Thank you guys for this information. This just reaffirms for me why Gamedev is my favourite web site on the WWW.

I am in the process of writing some code to solve the problem graphically using DirectX (takes more time than doing the genetic algorithm!). This is my first foray in to AI and I wanted to do this to help consolidate what I have been reading about genetic algorithms. It was set as a task in one of the chapters in the AI Techniques book.

I''ll post the source code once I get it done for anyone that''s interested. My biggest problem was coming up with a suitable fitness evaluation but I think this should be really helpful.

Cheers

__Daedalus__

#10 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 08 April 2004 - 06:35 AM

Hi,

I''m also working on putting a genetic algorithm to the 8-puzzle, and I would like the source code to study. If you can, Edo, send it to me at dmuser@aol.com.

Thanks,
Vchell

#11 Timkin   Members   -  Reputation: 864

Like
Likes
Like

Posted 12 April 2004 - 03:01 PM

Was it necessary to Necro this post just to ask edotorpedo for his source code. Next time this requirement comes up (and I''m talking to everyone here) PLEASE just send an email to the person you want to contact. There''s absolutely no need to necro a post for this purpose.

Timkin




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS