The Journey Continues .. to Darwin and beyond

Where did I get to... Hmmm I remember. Darwin & Yahtzee. Well I concluded my genetic algorithm for playing Yahtzee was not giving good results. My first thought was "damn, blast & pooh!!", my next was .. "what did you expect". I had a sudden rush of "Darwinism is sort of ridiculous". How can a random shuffling + pruning the worst lead to a optimum solution. Its way too simple.. It needs to have more subtlety, elegance... or some confusion... So my previous reasons for this were

1. Not enough games being played, so actual game statistics are too unreliable. In other words you can't tell the difference between lucky games and good maps (genes).
2. Not enough generations.. well I suppose we took millions of years to evolve
3. Not enough mixing of the maps (genes)
4. Expectations too high. I was rather hoping that this approach would yield a good set of results. In fact I was half expecting someone to say .. of course this sequence is correct because .. insert some mumbo jumbo here .. If you were to ask the same person before hand, you would get a very non committal reply. This is the difference between doers and thinkers. Sometimes doers think and do, where as thinkers just think, and usually of reasons of why inaction is the best course of action (or is it inaction).

I think 3 & 4 are probably right. After some digging with my colleague (brain size of planet sort of guy). He educated me (well, in a nice way said, I had the brain the size of a peanut). A summary of what he said is

1. My generation breeding technique was unique, in his experience (translation, wrong!) the pruning was far too sever, usually 40%ish makes it through to next generation.
   
2. Because of this I was probably only able to "hill climb" to a local maximum value.

His suggestion was to

1. Select the best 40% (there were a couple of methods)
2. Mutate 1% from the population
   
3. breed 59% from randomly selecting parents from the population
   

What this would do in comparison to previous methods is to provide far more random mixing, keep a few poor maps/genes in the mix, this would hopefully mean that there would be a better chance of jumping from one local hill (maxima) to the next set of hills/moutains (maxima).

This basically means, in Darwin terms, you can't be too selective. If you are, you risk only settling on a less than optimum values (breeds) as you end up not being able to cross the valley (because you throw results away that too far frpm where you are, your hill top). To put this in a different way, if you breed too selectively, it is likely that the resulting population will contain defects. Isn't this what dog breeders do!!! No wonder some animal activists are up in arms about breeding and selection. I did not realise!!! (OK.. this looks strange, I must have my geek hat on today. I don't believe people, when they say "selective breeding is bad", but am quite convinced by running an abstract computer simulation of a game of chance, and bingo I see the light.. hmmm. too much beer tonight)

Objective1: use above method to breed from a totally random generated game rules (see previous blog)..

Objective2: Use above method but with a seed of the best I have achieved.

My main problem is that these missions will eat severely into my free time. Kids need attention, wife needs compliments, work needs to be attended. Hey ho, who said this was going to be simple. When the results are in I'll publish a few more results...

result of objective2: I did some tests and it does look like things are getting better. I used a population of 101, each gene/map was given 100 games to prove their worth (probably too small, but 100 games takes about 1 second). I ran this for 20 generations. This takes 30 minutes or so to run. I then take the best map and run it for 100,000 games (get a really good statistical average), this takes about 15 minutes or so. This will really show what the map/genes are really made of. results for 100,000 games
max score 720, max number of Yahtzees 5, average score 218 top 1% score 477, bottom 1% 105. Average number of Yahtzees per game 0.48. The game logic takes 25% of the computers time and the response (interpreting the map/gene) takes 75% of the time.

Pretty good results. Lets take a look at how the system converged...
What you can see here is all the results per generation plotted at each generation. At generation 7 (gens 0-6 disappeared, never to be seen again.. probably a good explanation for this but I suspect a higher intelligence has whipped them from my computer files, they may appear in some remote desktop somewhere at some point ion the future... lets get back to the graph). Where was I oh yeah, generation 7 is essentially 3 groups of solutions, the top one around 215 average score, the next at 175, and the lowest at 90 ish. The lowest one disappears and becomes extinct by generation 12. No way for me to know if this generation X migrated to one of the two solutions or it simply became extinct. The next two remain until the last generation, but the 175 solution set thins out (like my hair). This leaves the biggest set. This set not only grows in size but also the best value increases to 235 ish. This is the map/genes I used for the 100,000 games run.

The astute reader (that means you!!) will realise that the above set of runs topped out at 235 average score, but the 100,000 runs ended up at 218 average score. Well I'm putting this down to statistical variation.. The sceptical reader (at the back wearing the black tee shirt and very dirty shoes) may suggest poor Java programming or sloppy organisation. I must confess, that may be true as well, but I'm trying to put the kids to bed, chasing them with a tooth brush saying.. "brush your teeth to keep the tooth-decay gnome away" (evil uncle of the tooth fairy).. and do this.

More results as and when they come in... I might give up on objective 1... objective2 is more fruitful than I thought...

Boldly going where no sane Java programmer would dare admit.. Continually repeating "your mistakes will guide you a a safer harbour than fair winds and a good navigator would ever lead you"

Tim inTheBlogOSphere signing out.