Executory argentite

As usual, better version at http://writer.zoho.com/public/rekamyenom/Executory-argentite1

executory (adj.): (Law) something not yet performed or done (i.e, an executory contract).

argentite (n.): a valuable silver ore consisting of silver sulfide (Ag2S)



So, I implemented the genetic algorithm for the logic problem 4. And it works well. Really well, actually. In fact, it beat me.

When I first looked at logic problem 4, I tried solving it by hand. Pretty quickly, after 2 or 3 minutes, I got this solution:

A _ _ _ _ C
_ _ _ D D _
_ _ _ A _ _
C _ B _ _ _
_ A A D _ B
_ _ _ D A _

(note: I've taken liberty with my labelling - in the grids, an A unit can kill an attacking A unit - all other units die to an attacking A unit. Basically A takes the place of D, D of C, C of B and B of A)



There were 13 units in this one. And it turned out that this was the 'correct' answer - to the extent that when I compared with Josh, he said he got the same answer.


And then I started to try to solve it with my computer. By pruning. That turned out to be ugly (see last post). So I decided to use a genetic algorithm - which was pretty risky, since they usually aren't all too good. But I did implement it (it didn't take very long, surprisingly), and it returned this 12 unit solution:

A _ _ _ D C
_ _ _ D C _
_ _ _ _ _ _
C _ B _ _ _
C A _ _ _ B
_ _ D A _ _

And by increasing the batch size a bit more, it even found an 11 unit solution:

A _ _ _ _ C
_ _ _ D _ _
_ _ _ _ D _

C _ B _ _ _

_ B _ A _ B
_ D _ _ A _

There's not even any guarantee that this is the best solution, since the genetic algorithm I wrote varies widely in performance. So Josh's and my answer weren't just off by one, but by at least 2. Admittedly, I only spent 2-3 minutes on it, and Josh probably didn't spend very long either checking for smaller solutions. Nevertheless, it appears like it's very hard to come up with the minimum value (for a human at least) - so these puzzles can be very tricky.


Onto how the program works (you can see the code on the side bar at the right). We start with a population of 50 'species'. Each species has one chromosome - a string of 36 characters, that describes a possible solution to the puzzle (one character per square). There are 5 possibilities (bases) for each character - "A", "B", "C", "D", which are what they say, and "X", which denotes an empty square.


Each species has a fitness value, calculated by how well it solves the puzzle. For example, the less units a species uses, the higher its fitness value - but if its solution results in some of our units being killed, the fitness drops. I believe the fitness formula I used was 5*enemyKills-20*ourKills-nUnits (where enemyKills is the number of enemies we've killed, ourKills is the number of our own casualties, and nUnits is the number of units we've used). This just seemed like it would filter the characteristics I want - but it would probably do a lot better with a bit of tuning.


Anyway, the fitness value of each species is calculated. Then the species sexually reproduce. Two parents are chosen from the current population of species, and they create two children. Species with a higher fitness level are more likely to be chosen as parents (whether a certain species is chosen as a parent or not is determined with a uniform tournament selection with p=0.2 - again this should probably be tuned) The children's chromosomes are determined by a crossover method on the parents two chromosomes. For example, if the parents' chromosomes (just for demonstration purposes - the actual chromosomes only have 5 bases, remember) were:


Parent 1's chromosome: "HELLOIAMACHROMOSOME".
Parent 2's chromosome: "OHHNOWHEREISTHECAKE".

A crossover point would now be determined randomly - say, after the 7th character:

Pieces:


"HELLOIA"
"MACHROMOSOME"
"OHHNOWH"
"EREISTHECAKE"

And these pieces combine to form new, different chromosomes:

"HELLOIAEREISTHECAKE"
"OHHNOWHMACHROMOSOME"

And these are the chromosomes of the children. The parents then die, the children grow up, and the cycle repeats - for 100 generations, in my program.

There is another important step in the middle of all that though - genetic mutation.

The idea is that crossover promotes genetic diversity, while natural selection maintains the quality of the species. This causes the overall species of a fitness to increase. A good analogy is that you are an ant looking for the tallest point on some 'mountain':

Every turn, the ant looks around and sees which way leads up the fastest (where the steepest slope upward is) and follows it. So, eventually he gets to the top of a hill. But wait, he's not on top of the mountain! But when he looks around, he sees that all paths lead downwards:

So our mentally impaired ant thinks he's reached the highest point on the mountain, because, after all, no matter what direction he goes, he'll end up going down. How can he reach the summit then? Well he's not going anywhere himself. He feels perfectly happy where he is.

The key is, we mutate him. Or, perhaps more fitting to the context, a gust of wind comes and moves him a bit in some direction:

And now our ant is on the way to the summit. Note, though, that the direction of the wind is chosen randomly. The wind could have not blown him at all - or worse, blown him to the left, where he would just climb back up and twiddle his thumbs again.

Nevertheless, after sufficiently many sufficiently powerful gusts of wind, the ant should be able to escape the hill and find the summit. The same idea applies to the genetic algorithm. Every time after the children are born, we slightly mutate them by passing through all the 36*50 characters and changing each of them with a 0.005 probability (again, could be tuned) to another random character. This way we don't get stuck at some solution which is locally optimal but not globally optimal.

That more or less sums up the entire algorithm. A good benefit of the algorithm is that if the conditions of the problem are changed slightly, it's very easy to adapt - we just change the fitness function. However, my criticism with how genetic algorithms often don't work too well still holds. Right now I run 200 batches of 50 species - that is, I simulate the evolution 200 times - hoping that one of them will give the optimal 11 unit solution. Even sometimes out of all the 200 batches, the 11 unit solution doesn't emerge and we're stuck with a 12 unit solution.

I'm fairly convinced this could be fixed with tuning though. If anyone wants to try tuning the fitness function or the probabilities, that would be pretty cool. Also, I haven't applied the algorithm to any of Josh's other problems, but do that at your leisure (or to check your answer). You input the initial enemy units into the unitsTop, unitsRight, etc. and typesTop, typesRight, etc. arrays. Take a look at what's in them right now - that corresponds to the original puzzle. From that you should be able to figure out how input works.

Anyway, that's all for now. I think my next few posts will be non-technical (or until, of course, Josh tries to make another weirdly constructed puzzle). Until then, ciao.

-squid out.

PS: random genetic algorithm pages:

http://www.cs.bgu.ac.il/~sipper/ga.html

http://citeseer.ist.psu.edu/cache/papers/cs/4086/http:zSzzSzgal4.ge.uiuc.eduzSzpubzSzpaperszSzIlliGALszSz95006.pdf/miller95genetic.pdf

http://www.obitko.com/tutorials/genetic-algorithms/

and Wikipedia, of course =).

PS2: Apparently, Blogger can't count, since it says I have 16 posts when I actually have 17 =S. Doesn't matter, of course =P.