risk and recursion

Lately, I've been playing a bit of correspondence Risk with some childhood friends. The good thing about correspondence Risk, when you're scattered across twelve timezones is that it is inherently self-limiting. You are forced to wait your turn every day. Well, that was my hope anyway, but it turns out that things are not quite that simple. The problem is that though you may well your turn, nothing is stopping you in the meantime from thinking about World Domination instead of doing something useful.

But maybe something useful just came out of these daydreams. I was thinking that Risk might be a good tool for teaching programming techniques. For example, it seems calculating dice roll outcomes would a rather nice example for teaching recursion and dynamic programming. This is something we typically do with factorial and fibonacci, but for some students, that might get a little boring. Perhaps dice rolls aren't all that exciting either, but maybe you could sell the Risk angle an awaken your audience's inner ten year old. Maybe you could sell this as part of a bigger package... in this class, we'll be putting together our own Risk implementation, with fancy graphics and everything.

The idea is that you want to ask your program "if the attacker has 37 armies and the defender has 10, what is the most probable outcome and its probability (assuming that each side uses as many dice as possible)?"

My belief is that there is no way to calculate this 'instantly' and without computing all possibilities. You would have to basically crunch through each one of the (a * d) eventual outcomes. (anybody with halfway decent math skills want to confirm that?)

One idea you might able to show with this is just plain simple recursion (although you probably want to start with a simpler example first). So I've got 37 and 10, and if I need the expected outcomes of 37/8 (attacker wins), 36/9 (both win one), and 35/10 (defender wins), I could just factor in the probabilities of getting those.

But I thought was interesting was that you could show that there is some redundant computation going on here. You start at 37/10, but then you go into

37/10
37/8	36/9	35/10

which in turn expands into

37/10
37/8			36/9			35/10
37/6	36/5	35/8	36/7	35/8	34/9	35/8	34/9	33/10

Here, we are recalculating the scenarios 36/7, 35/8 and 34/9. What happens if we turn the crank some more? If I'm not mistaken, the naive algorithm would have to do 3^n calculations (loosely speaking), when really we shouldn't be doing any more than n^2.

I suppose what you'd really want is to have some kind of record of all the outcomes you've already computed. I'm not sure how it would work out code-wise or how you'd shift all those weights around (and if you are interested, I do invite you to cook up a quick implementation, RiskBuzz). I will observe, however, that this table could make it simple to turn around and ask a slightly more involved question, like "ok, so what are the three likeliest outcomes and their probabilities?"