Solving The 8 Puzzle Using Genetic Algorithm

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.

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

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

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__

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