Jump to content
  • Advertisement
Sign in to follow this  
tczyp

How to use GA to slove the 8 - puzzle?

This topic is 4795 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
First offer yours. What is the 8-puzzle? What have you discovered so far?

Greetz,

Illco

Share this post


Link to post
Share on other sites
A GA is probably not the best choice for the 8-puzzle. In fact, it may be a poor choice. You could compose your chromosome as a series of moves (left, right, up, down), but this will very likely get stuck in cycles (left, right, left, right, left, ...) and will need measures to prevent such cycles.

Why have you chosen GAs? Some insight on your decision would be helpful.

-Kirk

Share this post


Link to post
Share on other sites

I have an application with solves an 8-puzzle with Genetic Algorithms. Must be said, this is definately not the most effective or efficient way, but I just did it for fun.

If you want to solve the 8-puzzle (efficiently), you might want to look into A* (or even standard Backtracking will do). The way I coded it with a GA:

- You have a pool of chromosomes (30-50)
- Each chomosome has a number of genes (maximum number of moves you want to search).
- Each gene is a 2-bit value (1 0 for left, 0 1 for right etc...).

You either penalize chromosomes which contains illegal moves, or just ignore them. If you implement it the right way, it could be fast and would not get stuck in endless loops.

But then again, GA is not the optimal tool for this problem.

Edo

Share this post


Link to post
Share on other sites
If you are looking for efficient solutions to the n-queens problem, you may want to look into constraint satisfaction problems (CSP).

Share this post


Link to post
Share on other sites
Thanks all for answer my question, if you all said that GA is not the optimal tool to slove the 8-puzzle, I agree with it. But I only want to make some thing interesting to show the GA. Do you have some wanderful advice?

Share this post


Link to post
Share on other sites
The bin packing problem is usually a good start, or also known as the knapsack problem.

Given: You have a bag of a fixed volume or size and n items each with a specific volume/size and a value.

Problem: Which items would you put in the bag from the n items available tus to optimize the total value.

Solution: Binary coded GA

Share this post


Link to post
Share on other sites
If it is just for learning purposes and for an interesting demo, edtorpedo's advice is likely your best option. IMHO

-Kirk

Share this post


Link to post
Share on other sites
Are there any interesting question like TSP sloved by AG will very efficiency?

Share this post


Link to post
Share on other sites

Quote:

Are there any interesting question like TSP sloved by AG will very efficiency?


Ehmmm... what?

The thing with GA is: you can not guarantee that a solution given by a GA is the optimal solution or even the most efficient. I think you should look into the workings of Genetic Algorithms a bit further and just start experimenting with a few simple problems.

Found a nice example once:
You have a rectangular area filled with random circles, all with different diameters.
Question: what is the largest circle (ie a circle having the largest radius) you can fit in to that area without overlapping other circles?

Start your Algorithms!

Edo

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!