## Wednesday, January 2, 2013

### Finding probabilities for RISK

During holidays we find ourselves playing board games. One of the best out there is RISK. During game-play, one might wonder what are the probabilities for each battle scenario. Moreover, if that someone is, well, a geek, he might write a program during game-play to support his army with a little of, em, technology.
So, do we know an equation to find those probabilities? No. Probably we'll find one with a little google search, but why not study it using a more programming method? We have the technology, we know a little bit of programming, so, let's take our chances.

1. import java.util.Arrays;
2. public class RiskProbability
3. {
4. private static int[] diceThrow(int n)
5. {
6. int[] dice = new int[n];
7. for (int i = 0; i < dice.length; i++)
8. dice[i] = (int)(Math.random()*6) + 1;
9. Arrays.sort(dice);
10. return dice;
11. }
12. public enum winner {ATTACKER, DEFENDER, TIE};
13. private static winner battle(int a, int d)
14. {
15. int[] attacker = diceThrow(a);
16. int[] defender = diceThrow(d);
17. int aSoldiersLost=0;
18. int dSoldiersLost=0;
19. int j=defender.length - 1;
20. for (int i = attacker.length - 1; i >= 0 && j >= 0 ; i--)
21. {
22. if (attacker[i] > defender[j--])
23. dSoldiersLost++;
24. else
25. aSoldiersLost++;
26. }
27. if (aSoldiersLost > dSoldiersLost)
28. return winner.DEFENDER;
29. else if (dSoldiersLost > aSoldiersLost)
30. return winner.ATTACKER;
31. else
32. return winner.TIE;
33. public static void main(String[] args)
34. {
35. int experimentSize = Integer.parseInt(args[0]);
36. int attWins = 0, defWins = 0, ties = 0;
37. int attStyle = Integer.parseInt(args[1]);
38. int defStyle = Integer.parseInt(args[2]);
39. for (int ex = 1; ex <= experimentSize; ex++)
40. {
41. winner w = battle(attStyle, defStyle);
42. switch (w)
43. {
44. case ATTACKER: attWins++; break;
45. case DEFENDER: defWins++; break;
46. case TIE: ties++; break;
47. defaultbreak;
48. }//switch
49. }
50. System.out.println("Experiment is with " + attStyle + " attackers and " + defStyle + "
51. defenders " + experimentSize + " times");
52. System.out.println((attWins/(double)experimentSize) + " attackers");
53. System.out.println((defWins/(double)experimentSize) + " defenders");
54. System.out.println((ties/(double)experimentSize) + " ties");
55. }//main
56. }
Let's explain the code a bit.
Lines 4-11 is the definition of a throw dice function. You specify the number of dice to throw, and a sorted array of the values of each die is returned. Watch out because the dice are sorted in ascending order.

Line 12 is an enumeration to be used for specifying the winner.
Line 13 is the definition of the battle function that takes two arguments, the number of dice the attacker will use and those of the defender as a second argument. Then the diceThrow is called and the battle begins on lines 20-26 until one runs out of dice.
Line 34 is the main method where the battle is initiated for 'experimentSize' number of times using the specified number of dice for each player.
To run this properly you have to pass 3 integer arguments, the experiment size (1000000 should be more than enough), the number of dice of the attacker and the number of dice of the defender. These are the results obtained by using the above program:

\$ java RiskProbability 1000000 3 2
Experiment is with 3 attackers and 2 defenders 1000000 times
0.371734 attackers
0.291923 defenders
0.336343 ties

java RiskProbability 1000000 2 2
Experiment is with 2 attackers and 2 defenders 1000000 times
0.227412 attackers
0.448301 defenders
0.324287 ties

\$ java RiskProbability 1000000 3 1
Experiment is with 3 attackers and 1 defenders 1000000 times
0.66038 attackers
0.33962 defenders
0.0 ties

\$ java RiskProbability 1000000 2 1
Experiment is with 2 attackers and 1 defenders 1000000 times
0.578971 attackers
0.421029 defenders
0.0 ties

\$ java RiskProbability 1000000 1 1
Experiment is with 1 attackers and 1 defenders 1000000 times
0.416221 attackers
0.583779 defenders
0.0 ties

\$ java RiskProbability 1000000 1 2
Experiment is with 1 attackers and 2 defenders 1000000 times
0.25389 attackers
0.74611 defenders
0.0 ties

So, the next time you'll play RISK, you'll know.