i was wondering if anyone had any ideas about how to go about setting up genes and fitness tests for a GA to solve pentominoes. if you have never heard of it, go to http://www.cs.cmu.edu/~desilva/pento/pento.html and play the applet. right now the only thing i can think of for a fitness test is how many spots on the grid are covered, but i am getting the feeling that it won''t be enough. any suggestions? cyn

Your fitness function seems fine. Absolute fitness functions are okay, you don''t have to get clever.
As to the rest of it, have the positions and rotations (not that I could get any of the blocks to rotate properly in the app) as integer values. Mutate using two values, first the chance of mutation, which should be set so that approximately one mutation occurs per genotype (if you have 30 numbers in your genotype, 20 for x,y position and 10 for rotation, then have a 1/30 chance of each mutating). The second chance is how much the values change, this should have a high chance for a small change and a low (but possible) chance for a large change. For instance, if you can place the block up to 10 positions away from its current position in the x, have the chance of moving 10 positions be 1 / 2^10, i.e. generate a random number between 0 and 1 and if it is less than 1 / 2^10, move it ten spaces. If that fails, move it 9 spaces if you generate a number smaller than 1 / 2^9. Continue this until you get to the point of moving it one space (1/2) and either move it that one space or move it with 50% chance, not moving it at all if none of the probabilities come up.
When performing crossover I''m not sure of an optimum chance, I normally go with something that''s likely to switch between the two parents at least once.
Try a small population, for example 30 individuals is reasonable, and choose parents by rank selection. This is done by ordering the parents high fitness first and having double the chance of choosing the most fit as a parent, as you have of choosing the individual in the middle of the population. The lowest fitness individual should have a small, but possible chance of being chosen as a parent. Conversely, when choosing a child, re-order the population lowest fitness first and pick in the same way. Don''t use elitism, its not worth it. The two parents should completely over-right the childs genotype.
For blocks which are illegally placed, simply don''t allow the placement and let that be punishment enough in terms of lowering the genotype''s fitness.

I think that covers how I''d do it, any questions don''t hesitate to ask.

Mike

well, i got the fitness function implemented and it seems to be getting stuck. i have been trying to tweak the fitness function so it does more than just count covered spots. it seems as the fitness rises, those illegal moves (which will exist in every genome except for complete solutions) seem to block the entrance of correct pieces. the crossover doesnt seem to be making any progress, the pieces seem to reach a (bad) plateau with the only way to get anywhere else seeming to be randomly generate a better gene. any other ideas for a better fitness function?

cyn

I spent quite some time last year working on solving the Eternity puzzle and was part of the online community working hard to claim the money. Essentially Eternity is a puzzle in the same vein as pentominos, however the state space is far larger (around 10620) and the peices are polydudes (made from 12 drafters triangles) so it was a lot tougher.

One of the avenues we investigated was applying a genetic algorithm to the problem of optimal packing, which pentominos is an example of. I had some lengthy discussions with one of my colleagues who had worked on applying simulated annealing to such problems. The general consensus was that it would be difficult to do.

The primary reason is this. You must find a method of evaluating arrangements of peices that take three things into account: 1) are there any holes within the boundary; 2) are there any overlaps withing the boundary; and, 3) does the boundary satisfy the desired shape.

It is not trivial to come up with an evaluation function that measures all three of these properties correctly. However, one idea (that was not implemented) was this. Optimise two functions at once with the same GA. The first function is a function of the area encompassed by the boundary, which you want to maximise. The second function was a function of the length of the boundary, which you want to minimise. An appropriate choice of such functions should result in the optima of both functions coinciding and representing the correct solution of the puzzle. To use both functions in the GA, you need to make a third (objective) function of them. Eg, f(u(x),v(x)) = u(x)/v(x), where x is the decoded chromosome value. Here u(x) would be the function to maximise and v(x) the function to minimise, giving f(u,v) a maximum when u=umax and v=vmin. I make no promises as to whether this function would work though as I haven't bothered to prove that the pentominos solution coincides with a maximum area and minimum boundary.

Anyway, getting back to the point. Optimal packing problems are, in general, non-trivial to solve. Thankfully Pentominos is one that is fairly trivial to solve using brute force search as the state space is tiny.

As for Eternity, it was finally solved using an Expectation Maximisation algorithm applied to a probabilistic model derived from a specialised search. Alex Selby collected the prize money of 1 million pounds stirling!

Cheers,

Timkin



Edited by - Timkin on July 25, 2001 12:44:29 AM

actually, the eternity puzzle was my ultimate goal in all of this. i knew it was already solved, but i still resolved to figure out a way of solving it, or finding one of the alternative solutions. i just stumbled upon GA''s about a month ago and struck on the idea of trying to apply them to puzzles instead of simulated life. thanks for the guidance.

cyn

hehe... I had an inkling this is where you were going... hence my mentioning the Eternity puzzle.

Had I gotten off my butt earlier and dedicated more time to coding my solution, I might have been the one collecting the prize money (well, I can dream can''t I)!

Actually, I had a provable method that guaranteed a solution was the only possible final state of my algorithm and that it was solvable in finite time (if a solution existed, which we were assured was the case). It was a beautiful concept that evolved a solution containing the correct pieces, rather than trying to fit the pieces inside a boundary with no overlaps or holes (the standard search approach). I just never got around to finishing my program... maybe I should some day... as there was plans for an Eternity II puzzle (in 3-D which my algorithm would extend to with absolutely no problems)! Actually, it works in n-D as well!

Cheers,

Timkin

Stupid question, but you are applying mutation aren''t you? At a rate of about 1 mutated variable per genotype? Once the population is converged crossover does little apart from spreading the one good gene you come across in the random search. Also, you could try increasing the population size, this would allow a lot more potential for crossing low fitness space between sub-optimal solutions.

Mike

of course i am doing mutations. the problem is that one variable will only shift its position, the piece type, or the rotation of the piece. if you move a piece on a mostly covered board, you end up covering different spaces, which keeps the fitness level the same or lowers it a little bit in most cases. right now i''m toying with the ideas that timkin posted. im going to take each piece and evaluate how much of its border is successfully touching another piece and try to get a better way to determine fitness as opposed to just being a number from 0(empty) to 60(solved). hopefully this will allow greater precision and that the genes that are marginally better to survive as opposed to the ones that plateau out at a near solution. if you have any other ideas i''m still open to suggestion.

cyn

Maybe you need a more radical mutation operator which is selected at a lower frequency. If you consider the fitness landscape of Pentominoes, it probably looks a lot like the street in front of my apartment - lots of near solutions that drop very deep, but are not truly the goal. Generally, I would think that crossover alone would take any particular local well and drive you right to the bottom of it. The simple mutation operator you suggest might not give the system enough entropy to jump clear of that local well and you end up falling back into that well. Or, you step from one local to another. Have you tried other mutation operators? I''m at a loss to come up with one now, but if I''m struck by inspiration, I''ll post back.

-Kirk

Okay, here''s some more ideas... a different approach to my last post.

Enforce the game board border, meaning that no piece can be placed so as to overlap the border. This means that you need an extra test after applying any operator that checks for a violation of the game board.

Second, encode for each piece the board location of each of the elements that make up the piece (5 squares for pentominos). Since the board is 6x10 in the example then you need 3 bits for the y coordinate and 4 bits for the x coordinate (for each square) which is 35 bits per piece. That''s not too bad. Alternatively, encode only the postition of a reference square in each piece and then its rotation number (0,1,2,3). This latter method will require more evaluation computation and more computation when mutation is applied.

To evaluate the fitness of a piece placement, it gets zero if it overlaps an edge and gets 5-(number of overlaps with other pieces). Then, each piece fitness should be weighted by the overall performance of the population. So, compute the percentage of good squares
= (60-(number of overlaps plus number of holes))/60
and multiply each pieces fitness by this number. This will mean that the fitness function is dynamic. The reason for doing this is so that the population doesn''t converge into a local minima cause by 1 piece not being overlapped, which could happen if all other pieces are stacked on top of each other so as to leave the original piece isolated.

Now, for mutation, use two separate mutation operators with their own probability: rotation and translation. Since the chromosome is an ordered set of pieces then crossover will ensure that any two boards (sets of pieces) still only have 1 copy of each in them.

Hope this idea helps.

Cheers,

Tim