lotus

previous page: 130 competition/games/poker.face.up.p
  
page up: Puzzles FAQ
  
next page: 132 competition/games/rubiks/rubiks.clock.p

131 competition/games/risk.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

131 competition/games/risk.p


What are the odds when tossing dice in Risk?

competition/games/risk.s

Odds calculated with program by David Karr (karr@cs.cornell.edu):

Attacker rolls 3 dice, defender rolls 2 dice:

Attacker   Defender   Probability
  loses      loses
    0          2       2890/7776  =  0.3716563786
    1          1       2611/7776  =  0.3357767490
    2          0       2275/7776  =  0.2925668724

Attacker rolls 3 dice, defender rolls 1 dice:

Attacker   Defender   Probability
  loses      loses
    0          1        855/1296  =  0.6597222222
    1          0        441/1296  =  0.3402777778

Attacker rolls 2 dice, defender rolls 2 dice:

Attacker   Defender   Probability
  loses      loses
    0          2        295/1296  =  0.2276234568
    1          1        420/1296  =  0.3240740741
    2          0        581/1296  =  0.4483024691

Attacker rolls 2 dice, defender rolls 1 dice:

Attacker   Defender   Probability
  loses      loses
    0          1        125/216  =  0.5787037037
    1          0         91/216  =  0.4212962963

Attacker rolls 1 dice, defender rolls 2 dice:

Attacker   Defender   Probability
  loses      loses
    0          1         55/216  =  0.2546296296
    1          0        161/216  =  0.7453703704

Attacker rolls 1 dice, defender rolls 1 dice:

Attacker   Defender   Probability
  loses      loses
    0          1         15/36  =  0.4166666667
    1          0         21/36  =  0.5833333333

---------------------8<------snip here--------8<--------------------
/*
 * riskdice.c  --  prints Risk dice odds
 *
 * This program calculates probabilities for one roll of the dice in Risk.
 * For each possible number of dice that the attacker might roll, for each
 * possible number of dice that the defender might roll, this program
 * lists all the possible outcomes (number of armies lost by attacker
 * and defender) and the probability of each outcome.
 *
 * Copyright 1993 by David A. Karr.
 */
 
#define MAX_ATTACK	3	/* max # of dice attacker may roll */
#define MAX_DEFEND	2	/* max # of dice defender may roll */
#define MAX_DICE	MAX_ATTACK + MAX_DEFEND
 
void main()
{
    int a;	/* number of dice rolled by attacker */
    int d;	/* number of dice rolled by defender */
    void calc();
 
    for (a = MAX_ATTACK; a > 0; --a) {
    	for (d = MAX_DEFEND; d > 0; --d) {
	    calc( a, d );
	}
    }
}
 
void calc( a_dice, d_dice )
/*
 * Purpose:  Print odds for the given numbers of dice rolled
 */
int a_dice;	/* number of dice rolled by attacker */
int d_dice;	/* number of dice rolled by defender */
{
    int num_dice;	/* total number of dice rolled */
    int num_armies;	/* # armies that will be lost by both sides, total */
    int kill_count[MAX_DEFEND + 1];
		/* entry [i] counts # of times attacker loses i armies */
    int roll[MAX_DICE + 1];	/* holds one roll of the dice */
    int a_roll[MAX_ATTACK];	/* holds attacker's dice */
    int d_roll[MAX_DEFEND];	/* holds defender's dice */
    int n;		/* cursor into the arrays */
    int num_lost;	/* # of armies lost by the attacker */
    int cases;		/* total # of events counted */
    void dsort();
 
    /*
     * The method is pure brute force.  roll[] is set successively to
     * all possible rolls of the total number of dice; for each roll
     * the number of armies lost by the attacker (the outcome) is
     * computed and the event is counted.
     * Since all the counted events are equiprobable, the count of each
     * outcome merely needs to be scaled down by the total count to
     * obtain the probability of that outcome.
     */
    /* The number of armies at stake is  min(a_dice, d_dice) */
    num_armies = a_dice < d_dice ? a_dice : d_dice;
    /* initialize event counters */
    for (n = 0; n <= num_armies; ++n)
    	kill_count[n] = 0;
    /*
     * The roll[] array is treated as a funny odometer whose wheels each
     * go from 1 to 6.  Each roll of the dice appears in roll[0] through
     * roll[num_dice - 1], starting with all 1s and counting up to all 6s.
     * roll[num_dice] is used to detect when the other digits have
     * finished a complete cycle (it is tripped when they go back to 1s).
     */
    num_dice = a_dice + d_dice;
    for (n = 0; n <= num_dice; ++n)
    	roll[n] = 1;
    while (roll[num_dice] == 1) {
    	/* examine a new possible roll of the dice */
	/*
	 * copy attacker's and defender's dice so as not to disturb
	 * the "odometer" reading.
	 */
	for (n = 0; n < a_dice; ++n)
	    a_roll[n] = roll[n];
	for (n = 0; n < d_dice; ++n)
	    d_roll[n] = roll[n + a_dice];
	/*
	 * sort attacker's and defender's dice, highest first.
	 */
	dsort(a_roll, a_dice);
	dsort(d_roll, d_dice);
	/*
	 * compare attacker's and defender's dice, count attacker's loss
	 */
	num_lost = 0;
	for (n = 0; n < num_armies; ++n)
	    if (d_roll[n] >= a_roll[n]) 
	    	++num_lost;
	++kill_count[num_lost];
    	/*
	 * Find next roll values (bump the "odometer" up one tick).
	 */
	n = 0;
	roll[0] += 1;
	while (roll[n] > 6) {
	    /* place [n] rolled over */
	    roll[n] = 1;
	    /* Carry 1 into the next place (which may in turn roll over) */
	    ++n;
	    roll[n] += 1;
	}
    }
    cases = 0;
    for (n = 0; n <= num_armies; ++n)
	cases += kill_count[n];
    printf( "Attacker rolls %d dice, defender rolls %d dice:\n\n",
		a_dice, d_dice );
    printf( "Attacker   Defender   Probability\n" );
    printf( "  loses      loses\n" );
    for (n = 0; n <= num_armies; ++n)
	printf( "%5d      %5d      %5d/%d  =  %12.10lf\n",
		n, num_armies - n, kill_count[n], cases,
		((double) kill_count[n]) / ((double) cases) );
    printf( "\n\n" );
}
  
 
void dsort( array, length )
/*
 * Sort the given array in descending order.
 */
int *array;
int length;	/* number of slots in the array */
{
    int level, n, tmp;
 
    /* Use bubble sort since the array will be tiny in this application */
    for (level = 0; level < length - 1; ++level) {
	/*
	 * Slots [0] through [level - 1] are already "stable."
	 * Bubble up the value that belongs in the [level] slot.
	 */
	for (n = length - 1; n > level; --n) {
	    if (array[n - 1] < array[n]) {
		/* swap them */
		tmp = array[n - 1];
		array[n - 1] = array[n];
		array[n] = tmp;
	    }
	}
    }
}

 

Continue to:













TOP
previous page: 130 competition/games/poker.face.up.p
  
page up: Puzzles FAQ
  
next page: 132 competition/games/rubiks/rubiks.clock.p