The Journey ... caught in a trap

The last exciting episode left me on the verge of discovering new vistas in the realm of Yahtzee. I had successfully started to breed slightly better solutions. This got me excited, I like to play Yahtzee for fun, but agonise over the best strategy at various points in the game. Now I never need play another game of Yahtzee, I'll just let my trusted computer do it for me. Get the man out of the loop, automate the whole process. In effect make myself redundant in the fun department. Yep, I need never have fun again, now that's progress. Only a true engineer/scientist would truly embrace this sort of human obsolescence.

One of the driving forces behind doing this was to see if the computer would be able to answer this question for me. I did tentatively try a pen and paper analytical approach. A small tip for anyone who would like to pursue this further than I was able to. If you come quickly at the problem from behind, you can distract it with the pen and bash it with the paper, this is why it is advisable to have lots of paper for these types of problems, a hefty weight of paper can stun or even knock out problems of this sort. But be warned, problems have a habit of striking back!!

Back to the analysis stuff.

1. Should you be aggressive from the start? If you have 2x6 and 2x1 and a 3 is it better to be optimistic and hold the 6s or play defensively and go for the 1s?
   
2. Is it ever right to give up on attempt and not hold anything, and just re-roll all 5 dice?
3. If a game is going badly is it worth logging a poor score in Yahtzee, as you are unluckily to get a Yahtzee anyway, and logging it in another slot will mean you will loose the chance of achieving that score.
4. If you do stick to never filling the Yahtzee with a non-Yahtzee roll, when logging the score in a less than optimal pattern, do you log it in the highest scoring (least likely) slot (say large straight) or in a low scoring slot (say 1s) where you might be able to make up for the difference latter in the game.

These questions (even full discussions) were never answered satisfactorily or conclusively. It always boiled down to ... do you feel lucky ... punk. This is a semi-ironic , the whole point of the game is to see how lucky you can be, what your best score is, the maximum number of Yahtzee's etc. The reality is the game shows how unlucky you are, and it is usually ... your nothing special, and sometimes your really poor ... Do lottery winners get excellent score when they play Yahtzee? Will a triple roll over winner get 10 Yahtzee's and have a score in the 1,000 point range? Is there a fixed amount of luck in the universe? If so why do the lottery winners get so much? Or is it that you have a fixed amount of luck for your life, and it is a case of "luck management". The luckiest people actually succeed on the same amount of luck as the other people, so it is really a case of an individual to manage the luck they are given? If so, then should companies hire lucky people, as they are actually successful "good luck managers", and it is probable that they will be good at other styles of management. If so does this hiring them decrement from there luck total? ... Time to stop here.. you probably get the drift.

So my basic questions about Yahtzee were strategy based. My attempt to write a genetic algorithm to solve the above has been listed in earlier blogs. The fundamental thing is... the methods I've used (up to now), will not be any use in answering the questions!!! Why, because

1. My maps/genes to play the game took no account of the number of rolls one was on. This means you cannot re-roll (otherwise you will end up in an infinite loop, and never finish the game)
2. If you make no differentiation between the first and third roll you cannot truly say you are throwing away points, as you may be on the first roll being optimistic (e.g. 2x6 and you hold the 6s going for 3x6s, or 4x6s or 5x6s, where as logging 2x6s against 6s is a different matter).
3. It was a gross over simplification to only have one map/gene for the game. (but it sort of worked!!)
   

So after chastising myself, realising how far from the original motivation I had strayed, I decided to inject 3 maps/genes for each attempt. One map/gene for each roll. There are a couple of problems though...

1. Using a genetic algorithm to search a 20x18 space is a large problem, in the order of 20x18! (that contains lots of zeros). Now I had triplied this space. It took a long time to previously, now it will take even longer
2. The code I had written was expressly written with the assumption that there was only one map... I have to unpick the code to accommodate the new maps. This is proof that my java design was poor.. (I can at least say I'm a beginner at Java ... but it is a fair criticism)

As such, I have adapted the code to read 3 maps (an array of 3 maps/genes, one for each roll). But alas, I was not able to insert a "roll again" command in the first two maps/genes.. The code is too complicated for me to unpick at the moment... Possibly time to re-design the code and review it.

This is my trap. can I re-write the code plus unit tests to reliable re-structure (re-factor) my code? Or should I continue on my current path with less than perfect maps/genes (in that they do not have a "roll again" genome/instruction).

Well that is Tim inTheBlogOSphere signing out. Boldly going nowhere fast, but finding all train to nowhere are delayed or cancelled.

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.