Risk Management

This post will be about risk management.  Well not really, I just wanted to post that clip.  Anyway, a few days ago I posted about a site that does some good data analyses.  One of them was on the game Risk.  This post will be a hodgepodge of random items related to Risk.

The Game

Risk is one of the staples of my gaming diet.  The computer version of Risk, that I've been playing for at least 10 years, is called TurboRisk.  Risk is notorious for taking a long time to play.  But that program, while maintaining almost identical rules, reduces games to 5 minutes.  The reason is simply automation.  I'd estimate a large battle (100 vs 100 armies) would take at least 15 minutes (possibly closer to an hour) in real life, but in TurboRisk would happen in about a second.

The speed increase is not the only benefit of TurboRisk though.  It allows anyone to write AI programs that you can play against.  There are about a dozen AI scripts included and they all have some interesting varieties of strategy.

The Program
My strategy is pretty formulistic, and I've long wanted to program an AI script based on it.  Unfortunately, the scripts must be written in pascal.  I had never used pascal, and figured it couldn't be that bad.  However, pascal is an old language and is closer to BASIC than C.  While I've defended BASIC a lot in my life, and still think it's a valid first language, after using C like syntax for so long the thought of using 'begin' and 'end' to deliminate code blocks wasn't appealing.  Still, I gave it a shot, but the combinations of the whole new API, having to code in the custom IDE instead of Notepad++, and length needed even for simple AI caused me to give up after a few hours.

Basic Rules
Before I get on to the fun* stuff I feel the need to explain the basic rules of Risk.  Feel free to skip over them if you are already a Risk master, however no other reason for skipping is acceptable.

Risk is a turn based strategy game.  There are about 40 territories that players can control.  You can attack any territory bordering one of yours (a handful of black lines make some territories border across an ocean).  You can attack as many times as you want on one turn.  To attack you must have at least 2 armies in the attack territory.  The mechanics of attacking are a bit odd.  The attacker can use from 1 to 3 dice, the defender only 1 or 2.  Both players must have at least 1 army per dice being used.  So, if I'm attacking with 2 armies a territory with 1 army I can only use 1 or 2 dice and the defender can only use 1.  It's best to use as many dice as you can.

Both players roll, and then the dice are arranged in order and paired up.  Each pair is compared and who ever has a higher number wins (defender wins ties).  The loser loses 1 army for each loss.  Example: Attacker rolls 5, 3, 1; defender rolls 4, 3.  5 beats 4 (defender loses 1 army), but 3 ties 3 (attacker loses one army).  If the defender had only rolled 1 dice only one army in total could have been lost, but the attacker would have had 3 chances to roll higher than him.

This odd rolling method means that the attacker has a clear advantage (being able to roll more dice), but ties going to the defender is also a clear advantage.  The net result is that for 12 vs 12 and below the defender has the advantage; above 12, the attacker has the advantage.

Moving on, if you defeat all the defending armies you win the territory, and may move any number of armies from the attacking territory into it (you must maintain at least 1 army in all your territories at all times).  The attacker cannot lose his territory in an attack (but if reduced to 1 army it could be an easy target come someone else's turn).  After attacking however many territories you want on one turn, you get one free move.  You can move armies from one of your territories to another bordering it (the same as if you had just conquered it).  Then your turn ends.

Going back to the start of your turn, you are given new armies to place on any of your territories.  The amount you get is the sum of three sources.  First is the number of territories you control (at the start of that turn) divided by 3 (integer only).  The second is a bonus for controlling an entire continent.  The bonus is hardcoded, but ranges from 2-7, and depends on the size.  The last source of armies is for trading in cards.  You get one card at the end of any turn where you captured at least one territory.  There are three kinds of cards; you need either one of each, or 3 of one kind to trade in.  The number of armies you get starts at 4 and grows to 15 for the 6th set, and adding 5 for each set after that.  An important note, in the real game this count is for all card sets traded in by anyone.  In TurboRisk each player has his own count.

To summarize: each turn consists of 3 parts.  Part 1, getting armies based on territories, continents and cards.  Part 2, attacking.  Part 3 moving.

My Strategy

My strategy is a somewhat common one.  Capture a continent and hold it while getting the bonus armies, and slowly build up forces.  Many of the bots do this with Australia as it only has one choke point to control.  I, however, prefer South America.  It has 2 choke points, and the same bonus as Australia , but it has much better options for growth.  From Australia you can only go into Asia, which is wide open and hotly contested.  From SA you can expand up through NA and only have 3 choke points total.  Then you can further expand to take both Europe and Africa while still only having 3 choke points (6, 7 in map).  If you can control that for a few turns you shouldn't have any problem taking the rest of the map.

A word about choke points.  Take 2 and 5, between SA and Africa, for example.  If you are holding SA you will have to build up forces in that choke point.  However, rather than putting them on your continent (2) put them in Africa (5).  This not only gives you 1 more territory, but also denies the Africa continent bonus to anyone else.  The same can be done for all the choke points.

My Analysis
I pointed out this great analysis above.  I wanted to write a program to check these odds, and it was a good excuse to do something in C++.  I spent a while working on speed improvements, with mild success.  My results match his pretty closely, except for one key fact.  As I mentioned above, you must leave 1 army behind when you conquer a new territory.  You must also have at least 2 armies before you can attack at all.  This, in effect, means if you are attacking with 15 armies, only 14 are useful.  As far as all the math is concerned this is the way to go.  This is what he did, but he never added that army back into his analysis.  This was intentional on his part: "All my calculations are based on the number of characters doing the actual attacking, not the number of armies on the starting square."

Still, I feel like it gives the wrong impression about the odds.  He says that 5 vs 5 is the cross over point, when it is actually 13 vs 13 when you count all armies.  Again, it's really just a matter of semantics, but I think it's important to remember which version you are dealing with.

Anyway, I felt like this would be a good thing to code up in javascript, so I largely replicated my C++ code in javascript.  This gave me the excuse to compile some common javascript functions I've used several times into a common shared file.
http://daleswanson.org/things/risk.htm

After finishing it I noted it was fast enough (50 vs 50 and 10,000 rounds takes about 2 seconds for me), but, still I would have liked it to be faster.  A search for risk odds turns up several much better versions.  I decided to blame it on the default javascript PRNG.  Several hours of hunting and benchmarking later, and I can say the default is the fastest.  The first site seems to do the calculations on the server side, which seems odd, but does result in about 2 orders of magnitude of speed increase.  The second site is all javascript though.  Looking at the script shows the key difference.  It has hardcoded the odds for each of the six possible dice combinations.  This is not only faster and more accurate, but is exactly how the guy in the post that started this all did it.

Making a program to calculate this all with recursive probability seems fun, so maybe I'll do that at some point.  History says that I won't though.


* May not actually be fun.