Solving The 8 Puzzle Using Genetic Algorithm
Author
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?
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.
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]
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..
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.
But, why ask? Why not just try it out?
I like pie.
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
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
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
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
Author
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__
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__
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
