Essays, Posts & Presentations

How to Win at Risk: Exact Probabilities

Jon McLoone

Author

Jon McLoone

Title

How to Win at Risk: Exact Probabilities

Description

How to Win at Risk: Exact Probabilities

How to Win at Risk: Exact Odds, Probability, Strategy

November 20, 2017

Jon McLoone
Director of Technical Services

The classic board game Risk involves conquering the world by winning battles that are played out using dice. There are lots of places on the web where you can find out the odds of winning a battle given the number of armies that each player has. However, all the ones that I have seen do this by Monte Carlo simulation, and so are innately approximate. The Wolfram Language makes it so easy to work out the exact values that I couldn’t resist calculating them once and for all.

Here are the basic battle rules: the attacker can choose up to three dice (but must have at least one more army than dice), and the defender can choose up to two (but must have at least two armies to use two). To have the best chances of winning, you always use the most dice possible, so I will ignore the other cases. Both players throw simultaneously and then the highest die from each side is paired, and (if both threw at least two dice) the next highest are paired. The highest die kills an army and, in the event of a draw, the attacker is the loser. This process is repeated until one side runs out of armies.
So my goal is to create a function pBattle[a, d] that returns the probability that the battle ends ultimately as a win for the attacker, given that the attacker started with a armies and the defender started with d armies.

I start by coding the basic game rules. The main case is when both sides have enough armies to fight with at least two dice. There are three possible outcomes for a single round of the battle. The attacker wins twice or loses twice, or both sides lose one army. The probability of winning the battle is therefore the sum of the probabilities of winning after the killed armies are removed multiplied by the probability of that outcome.

pBattle

[a_,d_]/;(a≥3&&d≥2):=Once[pWin2[a,d]

pBattle

[a,d-2]+pWin1Lose1[a,d]

pBattle

[a-1,d-1]+pLose2[a,d]

pBattle

[a-2,d]];

We also have to cover the case that either side has run low on armies and there is only one game piece at stake.

pBattle

[a_,d_]/;(a>1&&d≥1):=Once[pWin1[a,d]

pBattle

[a,d-1]+pLose1[a,d]

pBattle

[a-1,d]];

This sets up a recursive definition that defines all our battle probabilities in terms of the probabilities of subsequent stages of the battle.

Once

prevents us working those values out repeatedly. We just need to terminate this recursion with the end-of-battle rules. If the attacker has only one army, he has lost (since he must have more armies than dice), so our win probability is zero. If our opponent has run out of armies, then the attacker has won.

pBattle

[1,_]=0;

pBattle

[_,0]=1;

Now we have to work out the probabilities of our five individual attack outcomes: pWin2, pWin1Lose1, pLose2, pWin1 and pLose1.

When using two or three dice, we can describe the distribution as an

OrderDistribution

or a

DiscreteUniformDistribution

because we always want to pair the highest throws together.

diceDistribution[n:3|2]:=OrderDistribution[{DiscreteUniformDistribution[{1,6}],n},{n-1,n}];

For example, here is one outcome of that distribution; the second number will always be the largest, due to the

OrderDistribution

part.

RandomVariate[diceDistribution[3]]

{5,6}

The one-dice case is just a uniform distribution; our player has to use the value whether it is good or not. However, for programming convenience, I am going to describe a distribution of two numbers, but we will never look at the first.

diceDistribution[1]:=DiscreteUniformDistribution[{{1,6},{1,6}}];

So now the probability of winning twice is that both attacker dice are greater than both defenders. The defender must be using two dice, but the attacker could be using two or three.

pWin2[a_,d_]/;a≥3&&d≥2:=Once[Probability[a1>d1&&a2>d2,{{a1,a2}diceDistribution[Min[a-1,3]],{d1,d2}diceDistribution[2]}]];

The lose-twice probability has a similar definition.

pLose2[a_,d_]:=Once[Probability[a1<=d1&&a2<=d2,{{a1,a2}diceDistribution[Min[a-1,3]],{d1,d2}diceDistribution[2]}]];

And the draw probability is what’s left.

pWin1Lose1[a_,d_]:=Once[1-pWin2[a,d]-pLose2[a,d]]

The one-army battle could be because the attacker is low on armies or because the defender is. Either way, we look only at the first value of our distributions.

pWin1[a_,d_]/;a===2||d===1:=Once[Probability[a2>d2,{{a1,a2}diceDistribution[Min[a-1,3]],{d1,d2}diceDistribution[Min[d,2]]}]];

And pLose1 is just the remaining case.

pLose1[a_,d_]:=1-pWin1[a,d];

And we are done. All that is left is to use the function. Here is the exact (assuming fair dice, and no cheating!) probability of winning if the attacker starts with 18 armies and the defender has only 6.

pBattle

[18,6]

9804653220306498422549071803237023496256898193745

9885757284390281416111900904364482836234411966464

We can approximate this to 100 decimal places.

N[%,100]

0.9917958673523325122074555320397625291457271237542460366609745260803536003378927287553399877033534269

We can quickly enumerate the probabilities for lots of different starting positions.

table=Text@Grid[Prepend[Table[Prepend[Table[

pBattle

[a,d],{d,1,4}],StringForm["Attack with "<>ToString[a]]],{a,2,16}],Prepend[Table[StringForm["Defend with "<>ToString[n]],{n,1,4}],""]],FrameAll,FrameStyleLightGray]

	Defend with 1	Defend with 2	Defend with 3	Defend with 4
Attack with 2	5 12	275 2592	15125 559872	831875 120932352
Attack with 3	1955 2592	235 648	692225 3359232	5520775 60466176
Attack with 4	342035 373248	6610505 10077696	511817135 1088391168	296211210125 940369969152
Attack with 5	52218275 53747712	2279684105 2902376448	402241935565 626913312768	16132151698115/33853318889472
Attack with 6	7664728115 7739670528	1115640793115 1253826625536	208367138941435/270826551115776	1166853115687865/1828079220031488
Attack with 7	1110840377795 1114512556032	168631009513555/180551034077184	33419034783800035/38999023360671744	784333593461520355/1052973630738137088
Attack with 8	160309871334995/160489808068608	75396772054890025/77998046721343488	15330318348947652185/16847578091810193408	379255059981803538265/454884608478875222016
Attack with 9	23101715461932515/23110532361879552	11010545947512242585/11231718727873462272	765661249717909710275/808683748406889283584	19384653448927872063835/21834461206986010656768
Attack with 10	3327484632013250675/3327916660110655488	4804137726516316407515/4852102490441335701504	1013459658332291779695595/1048054137935328511524864	26311547467453520350587875/28297461724253869811171328
Attack with 11	479198829679161554435/479219999055934390272	694646957336195395611115/698702758623552341016576	148067345670131742879946235/150919795862687305659580416	3887120942290472253065082035/4074834488292557252808671232
Attack with 12	69006642564592683243155/69007679864054552199168	300962155889276196344558065/301839591725374611319160832	64440291685823636356332515105/65197351812680916044938739712	1711111396114731196946838360265/1760328498942384733213345972224
Attack with 13	9937055072750223937835555/9937105900423855516680192	43390866245523557496203624225/43464901208453944029959159808	9327322280274148197449473512785/9388418661026051910471178518528	248922104532701663141997947014265/253487303847703401582721820000256
Attack with 14	1430940759105027247038560435/1430943249661035194401947648	18760835741048540619680293306355/18776837322052103820942357037056	4039696080231765512322958484159875/4055796861563254425323549120004096	108336796588704520992900356911169915/109506515262207869483735826240110592
Attack with 15	206055705913944678573074487875/206055827951189067993880461312	2702515557859627884913858290531715/2703864574375502950215699413336064	64750616096531038839754548013802555/64892749785012070805176785920065536	5220636002299494528690924260485944025/5256312732585977735219319659525308416
Attack with 16	29672033245146250709499293730515/29672039224971225791118786428928	1167778035067942745763251501508940345/1168069496130217274493182146561179648	251967690660885851900319162907228880105/252303011164126931290527343657214803968	6785250680402762506055722310968440010705/6812181301431427144844238278744799707136

Here are the corresponding numeric values to only 20 decimal places.

N[table,20]

	Defend with 1	Defend with 2	Defend with 3	Defend with 4
Attack with 2	0.41666666666666666667	0.10609567901234567901	0.027015103452217649749	0.0068788457864443089637
Attack with 3	0.75424382716049382716	0.36265432098765432099	0.20606644614007011126	0.091303524800377652458
Attack with 4	0.91637463563100137174	0.65595399980312960423	0.47025109174719065710	0.31499433185017083586
Attack with 5	0.97154414684666018900	0.78545431505651468131	0.64162289645595149768	0.47653087576981756610
Attack with 6	0.99031710552421075876	0.88978872389001409505	0.76937485664896960785	0.63829461158021717422
Attack with 7	0.99670512618532171652	0.93397974913545334248	0.85691978680423048098	0.74487486729530025318
Attack with 8	0.99887882766028308409	0.96664948962444149538	0.90994196705340697635	0.83373904703002517732
Attack with 9	0.99961848996773521612	0.98030819808438213564	0.94679935293155810999	0.88780086053718082089
Attack with 10	0.99987018061402101104	0.99011464328721206935	0.96699170553232296158	0.92982005678982103704
Attack with 11	0.99995582534782659403	0.99419524076969884496	0.98109956234534777135	0.95393345507862799410
Attack with 12	0.99998496834752432714	0.99709303928261094326	0.98838817673097527356	0.97204095550505292133
Attack with 13	0.99999488506269925021	0.99829667246739337583	0.99349236724971247245	0.98199042221955015200
Attack with 14	0.99999825950050182820	0.99914780211762443907	0.99603018053392272828	0.98931827324883349929
Attack with 15	0.99999940774669853876	0.99950107837180172369	0.99780971389019702447	0.99321259367516149959
Attack with 16	0.99999979846936269722	0.99975047626597549943	0.99867096115225137633	0.99604669637565198497

More permutations :

Text@Grid[Prepend[Table[Prepend[Table[pBattle[a,d],{d,1,20}],StringForm["Attack with `1`",a]],{a,2,30}],Prepend[Table[StringForm["Defend with ``",n],{n,1,20}],""]],ItemSizeAll,FrameAll,FrameStyleLightGray]

Text@Grid[Prepend[Table[Prepend[Table[N[pBattle[a,d],30],{d,1,20}],StringForm["Attack with `1`",a]],{a,2,30}],Prepend[Table[StringForm["Defend with ``",n],{n,1,20}],""]],ItemSizeAll,FrameAll,FrameStyleLightGray]

Appendix: Code for Generating the Outcomes Graph

vf[{x_,y_},name_,{w_,h_}]:={Black,Circle[{x,y},w],Black,Text[If[StringQ[name],Style[name,12],Style[Row[name,"vs"],9]],{x,y}]};edge[e_,th_]:=Property[e,EdgeStyle{Arrowheads[th/15],Thickness[th/40]}];Graph[Flatten[Table[If[a≥3&&d≥2,{edge[{a,d}{a,d-2},pWin2[a,d]],edge[{a,d}{a-1,d-1},pWin1Lose1[a,d]],edge[{a,d}{a-2,d},pLose2[a,d]]},{edge[{a,d}{a,d-1},pWin1[a,d]],edge[{a,d}{a-1,d},pLose1[a,d]]}],{a,2,6},{d,1,4}]]/.{{a_,0}"Win",{1,d_}"Lose"},ImageSizeFull,VertexShapeFunctionvf,VertexSize1]

Cite this as: Jon McLoone, "How to Win at Risk: Exact Probabilities" from the Notebook Archive (2017), https://notebookarchive.org/2018-07-6xhkxjj