Calculate odds of single Risk battle

risk_dice.py

#! /usr/bin/env python3
#
# Purpose: calculate the odds 
# usage: risk_dice.py [ number of attacking armies ] [ number of defending armies ]
#    eg: risk_dice.py 3 2
#
# I first tried looking this up to see what others had found: https://www.google.com/search?q=risk+dice+odds
# The first 3 Google results have answers which disagree substantially:
# 1) https://www.reddit.com/r/theydidthemath/comments/2h224y/comment/ckottiv/ has an analytic approach
#    which doesn't seem to apply the actual game rules
# 2) http://www.cs.man.ac.uk/~iain/riskstats.php has a probability table which agrees with the results
#    here for 1v1, 1v2, 2v1, 2v2, but not for 3v1 and 3v2, and has to be wrong for the 3vX results
#    because they're worse for the attack than 2vX (which cannot be)
# 3) https://datagenetics.com/blog/november22011/index.html has a nice explanation of the problem,
#    a probability table which agrees with the results here, and extends into a nice followon
#    analysis with visualizations of why the effect per battle is small but compounds over large
#    repeated battles into a significant attacker advantage.
#
# Given the agreement with source (3) I believe the code below is correct.

import sys

[attacker_count, defender_count] = [ int(sys.argv[1]), int(sys.argv[2]) ]
[outcomes_tested, attacker_loses_both, both_lose_one, defender_loses_both] = [0,0,0,0]
double_attack = (attacker_count > 1 and defender_count > 1)

# iterate through every possible dice roll (completely deterministically, every possible combination weighted equally, no randomness)
iterations = 6 ** (attacker_count + defender_count)
for iteration in range(iterations):
	# In each iteration, we use the iteration number to denote a unique set of dice (for both players and the relevant number
	# of dice for the armies in play), convert that set of dice into a more convenient data format for processing, and then
	# apply Risk rules to see who wins/loses.
	#
	# We treat the iteration number as a base 6 number and then we can just read out the individual base-6 digits as the
	# values on each die (the die values will be 0..5 but behave the same as 1..6 on real dice for the game rules).
	# We can easily extract the individual base-6 digits by taking mod 6 to get the last digit, then
	# divide by 6 to discard the last digit, and repeat. I'll use `encoded_dice` to hold that base 6 number as we
	# shift the rightmost digit off of it and onto the attacker_dice and defender_dice lists below.
	encoded_dice = iteration
	# attacker_dice and defender_dice will be lists of integers (again, in range 0..5) representing the dice rolled by
	# that player in this iteration.
	attacker_dice = []
	defender_dice = []
	for i in range(0, attacker_count):
		attacker_dice.append(encoded_dice % 6)
		encoded_dice //= 6
	for i in range(0, defender_count):
		defender_dice.append(encoded_dice % 6)
		encoded_dice //= 6
	# verify we shifted all the dice off the "encoded" list of dice.
	assert(encoded_dice == 0)

	# perform battle
	# we'll sort the dice for each player from smallest to largest, pop off the
	# last entry in each array and compare to see who wins, keep score,
	# and repeat once if both players had at least 2 armies involved.
	attacker_dice.sort()
	defender_dice.sort()
	[alost, dlost] = [0, 0]
	# first battle
	[a_roll, d_roll] = [attacker_dice.pop(), defender_dice.pop()]
	if a_roll > d_roll:
		dlost += 1
	else:
		alost += 1
	if double_attack:
		# second battle
		[a_roll, d_roll] = [attacker_dice.pop(), defender_dice.pop()]
		if a_roll > d_roll:
			dlost += 1
		else:
			alost += 1

	# record outcome
	outcomes_tested += 1
	if double_attack:
		if alost == 2:
			attacker_loses_both += 1
		elif dlost == 2:
			defender_loses_both += 1
		else:
			assert(alost == 1 and dlost == 1)
			both_lose_one += 1
	else:
		if alost == 1:
			attacker_loses_both += 1
		else:
			defender_loses_both += 1

assert(outcomes_tested == iterations)
print("tested %d possible outcomes" % outcomes_tested)
if double_attack:
	print("defender loses 2  : %d (%g)" % (defender_loses_both, defender_loses_both / outcomes_tested))
	print("attacker loses 2  : %d (%g)" % (attacker_loses_both, attacker_loses_both / outcomes_tested))
	print("tie (each loses 1): %d (%g)" % (both_lose_one, both_lose_one / outcomes_tested))
else:
	print("defender loses 1: %d (%g)" % (defender_loses_both, defender_loses_both / outcomes_tested))
	print("attacker loses 1: %d (%g)" % (attacker_loses_both, attacker_loses_both / outcomes_tested))