• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

This topic is now archived and is closed to further replies.

__Daedalus__

Solving The 8 Puzzle Using Genetic Algorithm

10 posts in this topic

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?
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

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]
0

Share this post


Link to post
Share on other sites
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..
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites
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__
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites