Tuesday, 10 November 2009

Polynomials, dice and pensions!!

OK a weird title for a blog. I'm typing this with a few loose thoughts in my head. OK to business, the journey begins...

This is quite simple, but I'll further restrain our space with both p & q are positive but less than one. Now as seen before in the previous blog, if there is a game or situation where someone has n attempts, if they see a certain situation they stop, if not they try again (persistence). For example you have 4 tries to throw a six, if you get it on the first go, then you stop, if not try again for up to 4 attempts. Looking at this situation q, represents the probability that you "go again", p the probability you "stop". All the permutations for n attempts are (as previously shown)

p + pq + pq2 + pq3 + .. + pqi +.. + pq(n-1) + qn == 1

p(1 + q + q2 + q3 + .. + qi +.. + q(n-1) )+ qn == 1

Well the above is fine, except that most people would not recognise it, rather gravitate to the expansion of (p+q)n == 1

On the face of it, there is absolutely nothing wrong with either formulae. So lets run with this, recognising that qn will cancel from both formulae.

p(1 + q + q2 + q3 + .. + qi +.. + q(n-1) ) + qn == 1
pn +np(n-1)q .. nCi piq(n-i) .. + npq(n-1) + qn == 1

Well the qn cancels, and we can divide through by p to get

1 + q + q2 + q3 + .. + qi +.. + q(n-1) ==
pn-1 +np(n-2)q .. nCi p(i-1)q(n-i) .. + nq(n-1)

The top formulae has a very well known simplification, namely (1-qn)/(1-q) or (1-qn)/p (as p+q=1). The formulae is thus

(1-qn)/p = sum(i=0..n-1) nCi p(i-1)q(n-i)

Looking carefully at the above this is merely a re-write of (p+q)n .

This can also be broken down to look like the following..

(p+q)n + p(p+q)(n+1) + p2(p+q)(n-2) + .. pi(p+q)(n-i) + .. pn

So we are now back to our original formulae as p+q=1!!

However, lest assume p+q!=1. let us assume p+q=K instead, and use a similar method (that I stumbled upon by chance) to see where it leads. so

(p+q)n = kn

and thus

sum(i=0..n) nCi piq(n-i) = kn


sum(i=0..n) nCi p(i-1)q(n-i) = (kn-qn)/p

and so we can transform the above into

(p+q)n-1 + p(p+q)(n-2) + p2(p+q)(n-3) + .. pi(p+q)(n-i-1) + .. pn-1 = (kn-pn)/(k-p)


k(n-1) + pk(n-2) + p2k(n-3) + .. p(n-2)k + p(n-1) = (kn-pn)/(k-p)

An alternate method..

So lets do something similar, let
S = an + a(n-1)b + a(n-2)b2 + .. a(n-i)bi .. + bn

Sa = an+1 + anb + a(n-1)b2 + .. a(n-i+1)bi .. + abn

Sb = anb+ a(n-1)b2 + a(n-2)b3 + .. a(n-i)bi+1 .. + bn+1

Sa - Sb = an+1 - bn+1

and so
S = (an+1 - bn+1)/(a-b)

This is identical to above formula (and far quicker to run through!!!)

Saturday, 4 October 2008

Not More Yahtzee Maths

It has been a while since I lasted blogged. In the intervening time I have made a few more discoveries about Mathematics of Yahtzee. So for completeness I thought I'd put the electronic pen to internet paper and note down my conclusions. By advertising it in this way I can virtually guarantee that my discoveries will be kept as secret as the true identity of JFK's assassin, the formula for everlasting youth etc.

The route to my conclusion was far more tortuous that I will outline here. I used about 100 sheets of paper proving what could be written down in only a few lines. So I will now present the shortcut solution... But first the question..... Oh Guru Tim please can you provide me with a formula to give me the probability of getting a specific 5-of-a-kind, 4-of-a-kind, 3-of-a-kind and so on when playing Yahtzee.

Throwing One Dice Three Times
To answer the question we need to realize that you need three attempts (see www.yahtzee.org.uk for the rules). So lets start there, and only consider throwing one dice... regular dice p=1/6 (successful throw) q=5/6 (unsuccessful throw)
1st Attempt, success p, failure q
2nd Attempt, success qp, failure q2
3rd Attempt, success q2p, failure q3

So adding this up p + pq + pq2 + q3 ==> p(1+q+q2) + q3 which is == 1
Extending this further for n throws 1 = p(1+q+q2+ .. +q(n-1)) + qn

The first thing to note is that is not normally how one would write it. Normally one would expect a binomial expansion e.g.
(p+q)3 = p3+3pq2+3p2q+q3 == 1

However, the way in which we progress is different. The binomial expansion means that you would throw the dice 3 times no matter what you got, hence there is an option for throwing 3 correct dice in a row. So what the new expansion does for us is to allow us to stop throwing when the target is reached. The expansion is no less valid than the binomial, but it simply describes a different set of mechanics.

Throwing Five Dice Three times

OK Now we have a simple expression for throwing 1 dice three times, lets use five dice, and have 3 attempts. We are now armed with a new set of formula which is expressed like so

Probability of getting target number P = p(1+q+q2)
Probability of failing to get Target number Q = q3

Now remember that P+Q = 1 (and also p+q=1, p=1/6, q=5/6), Throwing the 5 dice with 3 attempts will yield a binomial expansion of (P+Q)5 = 1

Throwing 5-of-a-kind is P5 or p5(1+q+q2)5 or 1.33%
Throwing 4-of-a-kind is 5P4Q or 5p4(1+q+q2)4q3 or 9.12%
Throwing 3-of-a-kind is 10P3Q2 or 10p3(1+q+q2)3q6 or 25.04%
Throwing 2-of-a-kind is 10P2Q3 or 10p2(1+q+q2)2q9 or 34.40%
Throwing 1-of-a-Kind is 5PQ4 or 5p(1+q+q2)q12 or 23.63%
Throwing 0-of-a-kind is Q5 or q15 or 6.49%

The Long Way 'round

So taking a look at the above, one might say .. hey this is way too simple, I don't believe it. Well the as I said at the start I used up a small forest working the above through the long way round. If you wish to do it feel free. The long way round is to simply look at the binomial expansion for all the permutations (you can get a flavor from my previous posts), but remember that when you get the target number you stop. So look at the chances of getting 5 in one go (5M), then 5 in two goes, (4M:5M 3M:5M; 2M;5M; 1M:5M; 0M;5M), then in three goes (4M:4M;5M 3M:4M:5M 3M:3M:5M etc.... ) .. This will give you 5-of-a-kind, then repeat whole process for 4-of-a-Kind
etc... after a few forests and a couple of pencils you should end up with the above set of simple formulas.....

Time to go now, kids are suspiciously quiet...

Saturday, 26 January 2008

Double Maths (again!)

Probability of throwing Any Yahtzee
last time we left off with the result of getting a specific Yhatzee was
p5 [1+q(1+q)]5 . Which I thought was a very neat (p=1/6, q=5/6). The next, and probably more realistic question is "what are the chances of throwing ANY Yahtzee". My first attempts were very much based on the previous attempts, and indeed I came up with a result of p4 [1+q(1+q)]4 . This However was wrong, this evaluates to 3.15%, when I did my test runs on it I came up with a value closer to 4.5%. My first thoughts were, the Java random algorithm was poor, but it did match the previous formulae for a specific Yahtzee, so I was wondering if my algorithm was wrong or I had a bug!!

After some further thought I realised that a potential for getting more Yahtzees was obvious.
  • When you are going for a specific yahtzee and you have 0 1 or 2 matching numbers, you forge on...
  • BUT if you need ANY old Yahtzee, then of you have 2 matching numbers, you are not tied to these. So lets say roll 1 gave you 2,2, 3,4,6 You hold the twos, roll again ... now there is a chance that you then roll a full house say 2,2,5,5,5. At this point you abandon yahtzees in 2's and go for the more fruitful 5's. And this is what my Yahtzee algorithm will do. Hence the extra Yahtzees.
My problem now was converting this into neat formulae as per my previous result. This was not so easy. So turning to google ... I found this ...http://www.yahtzee.org.uk/theory.html which was a different approach to me, but none the less had a very interesting set of results. The Yahtzee.ork.uk paper says getting any Yahtzee is about 3.7% (a bit low), and in general it dealt with the maths quite nicely, BUT, when dealing with 2-of-a-kind it did not consider abandoning it when a full house was thrown. When you start to look at the numbers throwing any two-of-a-kind (a pair and 3 other numbers or two pair and a single number) it is nearly 70% of the time... We are on the right track (thanks Yahtzee.org.uk)

So I perseveered. The eventual formula was derrived is a very similar way to previous with inspiration from the above paper. I'll not do all the maths but, here is a summary

5M (Yahtzee) --> 6/7776 == 6.p5
4M (4-of-a-kind) --> 150/7776 == 6.5.p4q
3M (3-of-a-kind) --> 1500/7776 == 6.10.10p3q2
2M(a pair) --> 5400/7776 == 6.Q.p2
0M(nothing) --> 720/7776 == 6.R.p

so p = 1/6, q=5/6, Q is a fudge and is 5400/1296 R is also a fudge and is 720/7776

1st Attempt
This is simple, roll a Yahtzee probability is
  • 5M --> 6.p5
or 0.077%

2nd Attempt
A few more combinations here
  • 4M:5M --> 6.5.p4q . p
  • 3M:5M --> 6.10.10p3q2 . p2
  • 2M:5M --> 6.Qp2 .p3
  • 0M:5M --> 6.p5
adding it up, after the 2nd attempt (so adding in the 1st attempt) we get

6p5(1 + 5q + 10q2 + Q + R), or 1.26%

3rd attempt

4 of a kind, 4 of a kind, then yahtzee ..
  • 4M:4M:5M --> 6.5p4q . q . p
3 of a kind to 3 & 4 of a kind to Yahtzee
  • 3M:4M:5M --> 10.6.p3q2 . 2pq . p
  • 3M:3M:5M --> 10.6.p3q2 . q2 . p2

2 of a kind to 2,3,4 of a kind and then Yahtzee PLUS, 2 of one kind to 3 of another, to yahtzee

  • 2M:4M:5M --> 6Qp2 . 3p2q . p
  • 2M:3M:5M --> 6Qp2 . 3pq2 . p2
  • 2M:2M:5M --> 6Qp2 . q3 . p3
  • 2M:2N:5N --> 6Qp2 . 5p3 . p2

Nothing to something better to yahtzee (basically 6RP * 2nd attempt)

  • 0M:0-4M:5M --> 6Rp . 6P5(5q + 10q2 + Q + R)
The whole lot

6p5{1+ (5q + 10q2 + Q + R)(1+6Rp) + 5q2 + 10q2[(1+q)2 – 1] + q[(1+q)3 -1] + 5Qp2}

Not so nice but is 4.610%, which is 3.47 times larger than a specific Yahtzee.

If anyone has suggestions for substitutions for P & Q (preferably to fit in with the binomial expansions) that make the above simpler feel free to comment..

Tally ho, I'm going to be running 10,000,000 games tonight.

Wednesday, 23 January 2008

Some Mathematics and Yahtzee

Probability of getting a Yahtzee...

OK, quick recap of what a Yahtzee is. You roll 5 regular cubic dice, and if all the dice score are the same it is a Yahtzee (e.g. 5 dice each showing 1). That said, you don't have to do it on the first go. You can have up to 3 attempts, and you can roll as many dice you choose. So if you wanted a Yahtzee in 1s you might roll 1,2,1,4,5.. You can keep the two 1s and roll the remaining 3 dice.

So now look at some of the mathematics. Let

p = probability of rolling a specific number on one dice (1/6)

q = the probability of not throwing the specific number (1-p) or (5/6)

I'm using p & q as it is easier than writing 1/6 and 5/6 each time. Additionally, there are some arithmetic simplifications that are easier to deal with using algebra, rather than hard numbers.

Some fundamental probability combinations. I will use these latter. Rolling 5,4,3,2 or 1 dice gives the following binomial permutations

..............0M ......1M.....2M........3M......4M.......5M

(p+q)5 = q5 + 5pq4 + 10p2q3 + 10p3q2 + 5p4q+ p5 ... rolling all 5 dice

(p+q)4 = q4 + 4pq3 + 6p2q2 + 4p3q+ p4­­­ ... rolling 4 dice

(p+q)3 = q3 + 3pq2 + 3p2q+ p3 ... rolling 3 dice

(p+q)2 = q2 + 2pq + q2 ... rolling 2 dice

(p+q)1 = q + p ... rolling just 1 dice

Note that each row adds to 1 (as p+q=1, and 1x = 1), this fact will be used (lots) later on.

The top row (5M, 4M etc) shows the number of matching dice rolled (so Yahtze is 5M, 4 of the same number is 4M, and so on). Each row corresponds to throwing 5 dice, 4 dice etc. These permutations will be used latter on, and it is assumed that the reader is familiar with the concept of binomial permutations... if not .. sorry no tutorial here

Also below I will use some short hand to denote the way the dice were rolled. So 1M:3M:5M represents 3 attempts, 1st attempt rolled 1 target number, the next attempt the remaining 4 dice were rolled and 3 target numbers (in total) were matched (or two new target numbers), and the last attempt gave a Yahtzee with 5 matching target numbers.

The last thing is that if you roll a target number, it is assumed you hold it, thus the following combination would not occur 4M:3M:5M, if you rolled 4 target numbers you would hold all four, so it would be impossible (stupid) to have less than 4 target numbers after the second roll.

1st Attempt

Only 1 permutation to get Yahtzee, roll 5 dice & get it, the probability is

5M is p5

2nd Attempt

There a few permutations here, you could roll 4,3,2,1 or 0 matching dice, then throw a Yahtzee from the remaining, the combinations are listed below along with the probabilities.

  • 4M:5M is 5p4q . p
  • 3M:5M is 10p3q2 . p2
  • 2M:5M is 10p2q3 . p3
  • 1M:5M is 5pq4 . p4
  • 0M:5M is q5 . p5

Adding these up

p5 {5q + 10q2 + 10q3 + 5q4 + q5}

The expression within the { } brackets is (1+q)5 – 1, so this simplifies further to

p5 {(1+q)5 – 1}

3rd Attempt

There are lots of permutations here (as one might expect)

4M:4M:5M is 5p4q . q . p

==> p5{ 5q2 } ==>

p5 { 5q (( 1+q) -1)} (this complication will become apparent as the other terms are calculated)

  • 3M:4M:5M is 10p3q2 . 2pq . p
  • 3M:3M:5M is 10p3q2 . q2 . p2

So 3M:3-4M:5M is the sum of the above

==> p5{ 10q2 ( 2q + q2 ) } == > (note that 2q + q2 == (1+q)2 -1, hence the above complication!)

p5 { 10q2 ((1+q)2 -1) }

  • 2M:4M:5M is 10p2q3 . 3p2q . p
  • 2M:3M:5M is 10p2q3 . 3pq2 . p2
  • 2M:2M:5M is 10p2q3 . q3 . p3

So 2M:2-4M:5M is the sum of the above

==> p5{ 10q3( 3q + 3q2 + q3 ) } == > (again note 3q+3q2+q3=(1+q)3-1)

p5 { 10q3((1+q)3 -1) }

  • 1M:4M:5M is 5pq4 . 4p3q . p
  • 1M:3M:5M is 5pq4 . 6p2q2 . p2
  • 1M:2M:5M is 5pq4 . 4pq3 . p3
  • 1M:1M:5M is 5pq4 . q4 . p4

So 1M:1-4M:5M is the sum of the above

==> p5{ 5q4( 4q + 6q2 + 4q3 + q4) } == > (you should be getting the idea now..)

p5 { 5q4((1+q)4 -1) }

  • 0M:4M:5M is q5 . 5p4q . p
  • 0M:3M:5M is q5 . 10p3q2 . p2
  • 0M:2M:5M is q5 . 10p2q3 . p3
  • 0M:1M:5M is q5 . 5pq4 . p4
  • 0M:0M:5M is q5 . q5 . p5

So 0M:0-4M:5M is the sum of the above

==> p5{ q5( 5q + 10q2 + 10q3 + 5q4 + q5) } == >

p5 { q5((1+q)5 -1) }

The 3rd attempt can now be summed up and reduced (if that is the word!!) to

p5 { 5q(1+q) + 10q2(1+q)2 + 10q3(1+q)3 + 5q4(1+q)4 + q5(1+q)5 – [(1+q)5 -1]}

Adding it All Up

Adding together the 3 terms for 1st attempt, 2nd attempt and 3rd attempt

  • 5M is p5
  • 1-4M:5M is p5 {(1+q)5 – 1}
  • 1-4M:1-4M:5M is p5 { 5q(1+q) + 10q2(1+q)2 + 10q3(1+q)3 + 5q4(1+q)4 + q5(1+q)5 – [(1+q)5 -1]}

This simplifies as the bit in [...] cancels with 2nd attempt expression, to

p5 { 1 + 5q(1+q) + 10q2(1+q)2 + 10q3(1+q)3 + 5q4(1+q)4 + q5(1+q)5}

Replacing q(1+q) with x gives

p5 {1 + 5x + 10x2 + 10x3 + 5x4 + x5}

The bit in the { } is a simple expansion of (1+x)5 becomes

p5 (1 + x)5

Now as the above is a very simple expression (considering where we started), and back substituting x=q(1+q) gives the final result

Of probability of getting a specific Yahtzee in 3 attempts is

p5 [1+q(1+q)]5

Putting in some numbers the result is 915/615 or 0.01327. So to get any Yahtzee is 6 times this or

915/614, or 0.0796, or just under 8%. This is much larger than I had originally thought.

As each game has 13 sets, then one would expect to see 0.66 Yahtzees per game.

Max Score Yahtzee
The maximum score yopu can get in Yahtzee is 1575, and means not only you get 13 Yahtzees in a row, but you some are specific Yhatzees. Doing some more maths the first two yahtzees can be any type of yahtzee, then you have 8 specific Yahtzees and 3 any old yahtzees, this. So denoting p(ay) for any Yahtzee, and p(y) as a specific Yahtzee

p(ay).p(ay).[any order of 8 p(y), 3 p(ay)]

The way to arrange 11 things with 8 and 3 is 11*10*9/3*2 ==> 165
also p(ay) = 3.47*p(y) (see next blog, Double Maths (again!) )


(3.47)2 p(y)2 . 165 . p(y)8 . (3.47)3p(y)3


p(y)13.(3.47)5. 165

as above p(y) = 0.01327, doing some maths, if my computer can run 130 games per second, to have a relatively good chance of getting this I need to run the simulation for 7.4 billion years!

Thursday, 13 December 2007

Lies, damn lies and measurements

This blog started with a chance meeting with a business colleague (how grown up, I'll be wearing a suit and tie next). His basic question was "could you give a talk on something"... my reply, was the only thing I thing you might like is my current line of thought, software measurements, quality etc.

OK lets move onto the where to measure the data. The answer is every where and any where it is produced. But specifically, lets look at unit and module tests. Unit tests are generally run very regularly, many times a day (especially for XP developments). One may use unit tests as profiling and run the occasional test looking for which unit tests take the longest. But there is more information to be gleaned from them... if you care to log it .. imagine a database being populated in the following manner
  1. Test suite resources utilisation: Contiguously (well every 5 minutes) on the test suite, the CPU, memory, network, disk utilisation of all the systems was also logged and the results automatically loaded into a database
  2. Test results: If when every unit tests were run, the result was automatically uploaded to a database with, date, time, package, build no, time taken to run each test and number of times or loops in the test
  3. Test suite configuration: On a weekly basis the test suite uploaded it's configuration, CPU type & speed, total memory, OS and version, patches, java/c/c++/c# version, number of disks and so on
So now we have a database with not only the software metrics such as latencies, throughput etc, but also resource utilisation, and suite configurations. What could we do with this data? How do we make this data work for us?
  • Firstly we can track how each test is performing over time, from it's first run 'till now
  • Secondly we can spot any step changes (either up or down) in the way a single test is performing
  • Lastly, we could pick some specific tests and use these are our KPI, a standard unit of performance, that future versions of the code can be compared to. This could be simple or a string of system states
The above is merely a fairly top level analysis of the software metrics, albeit at a fairly detailed level. In essence the system is being profiled as you test it, and every time you test it. The next trick is correlation. This is slightly harder, as the resource utilisation data will probably be measured as a five minute average, the unit tests may only take 90 seconds or so to run. None the less, in the five minute period when the system is running the unit tests the CPU, memory, disks utilisation etc will all rise. Correlate this rise with the work going on, and you will start to see a pattern of what resources are being consumed as the system is being run.
  • Correlate software measurements such as throughput, latency with resource utilisation, CPU, disk IO etc.
  • look at resource utilisation over time.
Note that we are not striving to ensure each tests footprint is well know (though this is perfectly good approach), but the overall effects of resource required to run the tests is sufficient. Whilst this is gross simplification, it should be noted that working out what the actual resource utilisation under specific load cases is really the job of validation and verification. I'm not suggesting that the V&V stages be replaced by continuous monitoring and measurement process, but merely that what happens in V&V is useful during the development phase of a project. As more data is gathered, it may well (actually should) transpire that the system's performance is a relatively well know and quantified value. This means when it does become time to perform V&V, they have a head start, and may even have a good, well established set of tools to work with.

So how would all this work on a day-to-day basis.

Bedding in: After an initial period of development of the infrastructure and tools, data would be collected. At first it will seem complicated, and far too much detail.
gaining acceptance: Then after a while, the general data patterns will be recognisable, and some general rules of thumb may develop (e.g. each unit test adds about 1-2ms to total test time, each unit test generates 20 IO, 15 read, 5 write and so on).
acceptance: Then deeper patterns will start to emerge. What will also become apparent is when things start to differ. If a new unit test (note new, not existing) takes more than 5ms, look carefully. Or what about a unit test that used to take 1ms to run is now consistently taking 3 ms to run. Once these features are being spotted, the performance of the system is far more quantitative, and far less subjective.
predictive: When the results are being used as engineering data. Performance of module x (as determined by one or more unit test results) is degrading. It will become a bottleneck. redesign activity required. Or even, a better disk subsystem would improve the performance of the tests by 2/3 and mean the unit tests run 1 minute faster.
historical: imagine being able to give quantitative answers to questions like "Architecture have decided to re-arrange the system layout like so (insert diagram here), what will be the effect of this layout compared to the current?". Unusually it would require re-coding the system under the various architectures and performing tests, but all that is now required is to understand the average effects of each of the components, and a good engineering estimate can be arrived at. Taking this a step further imagine "The system's performance indicates that the following architecture would be best like so (insert diagram here), and we/I believe that it would allow 20% more throughput".

Taking stock... Once upon a time tests were done infrequently, but it was realised that testing is the only sure fire way of ensuring features remain stable and bug free. The reduction of the time from bug introduction to bug detection is crucial. Why stop at bugs? Why not use the same approach to performance? When is it easiest to change the software architecture? at the beginning, when is it hardest, at the end? Why change software architecture, there are many reasons, but performance is one.

Lastly the quantification of the software performance is a key feature, because this is the only way to truly make engineering decisions. Developing software is full of contradictions and pro's and cons, it is only be quantifying them that you can confidently take the decisions .

Thursday, 6 December 2007

How do you measure the good?

Well a new week a new topic. I've not finished with the Java stuff, but something else is nibbling at my consciousness. It is vaguely related to the previous blogs. The question I'm going to spout about today is "How do you measure the good?"

Having read "Zen and the art of motor cycle maintenance" [and "Zen and the art of archery"] I'm of the opinion that you cannot easily measure or quantify good (or quality, or excellence, or angles). But we all seem to know what is good when we see it. That.. TV program is good, that dinner is good. That film is good. When you push someone to explain WHY it was so good, you get rather less than quantifiable answers it made it made me laugh, it was tasty, I enjoyed it. In essence not very objective quantities, but certainly positive subjective comments.

This spin on quality ( .. as more than eloquently expressed in Zen & bikes book above) is not new. But it was not until a recent project that I realised the reason you can't quantify how good something is is because you can't count the number of good points. .... BUT you can count the bad points, moreover, you can count specific bad points. Say number of spelling mistakes in a text, and add this to number of words and bingo you have a spelling error rate (e.g. 1 spelling mistake per 100 words or 5 spelling mistakes in the 500 word article).

So let us assume that we want to measure the quality of a text and decide to count number of spelling mistakes, the number of grammatical errors. Lets say we now have an article which scores zero on those counts .. does that make it a high quality article? Does it make the article inherently good? Interesting? compulsive reading? The answer to that is obviously no. But then again these are characteristics of high quality writing. That said, if an article is well written with respect to grammar and spelling it obviously means that the author has taken more than a passing interest in the subject, and so has a fair chance of grabbing your attention.

If we move onto code quality.. told you this was related to Java. I know I'm on a loosing footing if I talk about code quality, so I'm going to change the rules (sign of a cheat!!). For the sake of argument I will not call it "code quality" I will call it "code QQnty". QQnty is like quality, but is a lot more quantifiable. QQnty will have a value, or set of values that you can point at and measure. You can take someones product and say it has a QQnity of X and someone else's product and say it is X+1. To judge if a piece of code is quality code is far too subjective, rather you will need to measure its QQnity. What you want to measure the QQnity against is an open question, but none-the-less, once defined the QQnity of that code will be a measurable number. The reason for this is that judging code quality is far harder than judging the quality of a piece of writing, or how good a film was. The reason for this is two fold
  1. Code developers are a mixed bunch of people, and the chances of any two of them agreeing on any subject, trivial or not, are about as slim as winning the lottery. It does happen, to someone, but I've never witnessed it first hand
  2. Code developers are generally quite passionate about their art (science). Anyone who may have even the slightest difference of opinion from themselves is a heretic. Heretics must die, or at least be argued with.
But there is one extra objective measure that can be performed with code... does the code work in the way it was intended (irrespective of the quality of the underlying code base). If the answer to this is yes, then you are home and dry. So if you define QQnity as the number of functional points (or requirements) minus say the number of bugs since release. Now you have quantified the code..

Well that is at least the theory, when you think a bit harder about it QQnity will itself become a subjective measure as different people will put different models together to measure what they want. What is interesting (to me anyway), it is extremely difficult to measure the good in a piece of code, but much easier to count bad points...
  • number of bugs (# bugs).. this is certainly a quantifiable point, how bad each bug is may or may not be quantifiable, but each bug counts as one.
  • number of functional points achieved/failed (FPA/FPF). it is more usual to use the failed version as there are fewer to count. Again, how important each functional point is is subjective, but you can count it
  • number of lines of code (LOC). This is very misleading. A large code base may mean that the code is highly complex, but it also probably means it is inflexible, or difficult to maintain. Similarly it could be lots of lines of junk. However, a measure none the less.
  • number of passed/failed tests (# PT/ # FT). Again the negative is more common than the positive
With the exception of number of lines of code (LOC) the above is mostly counting poor/failed points. To my mind LOC is a necessary measure, but should not as an absolute measure, and when used used as a denominator

QQnty = total FP/LOC
This measure means that if you succeed in producing the total functional points in fewer LOC, then you do better!! This may lead to more code re-use (should not impact LOC), simpler code (one hopes)


QQnty = total tests/LOC
This way the programmer can either increase total tests, or reduce LOC, either way both would likely (but no certainty) improve quality

However, watch out for .. QQnty = # bugs/LOC
This way the only way to improve (well reduce) QQnty is to increase LOC

This is the end of my splurge, now you've reached the bottom of this text... you can go to bed/work/school satisfied you completed one task today (but how good it is is subjective, but it still counts as one!!)

Monday, 5 November 2007

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.