daily pastebin goal
4%
SHARE
TWEET

Pig dice game optimal strategy

a guest Mar 2nd, 2014 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <cmath>
  3. #include <iostream>
  4.  
  5. struct Pig
  6. {
  7.     // value[0][i][j][k] is the probability of the current player winning with
  8.     // score i, opponent score j, and current roll total k.
  9.     double value[2][256][256][256];
  10.     int roll_max;
  11.     int roll_pig;
  12.  
  13.     // Compute value[] array for the game where each roll is in the range
  14.     // 1..roll_max, rolling roll_pig ends a turn, and reaching the given win
  15.     // score ends the game.  Return the number of iterations required to
  16.     // converge within the given tolerance.
  17.     int reset(int roll_max = 6, int roll_pig = 1, int win = 100,
  18.         double tolerance = 1e-15)
  19.     {
  20.         // Initialize value array.
  21.         this->roll_max = roll_max;
  22.         this->roll_pig = roll_pig;
  23.         for (int n = 0; n < 2; ++n)
  24.         {
  25.             for (int i = 0; i < win + roll_max; ++i)
  26.             {
  27.                 for (int j = 0; j < win + roll_max; ++j)
  28.                 {
  29.                     for (int k = 0; k < win + roll_max; ++k)
  30.                     {
  31.                         // Start with all values 0, except for winning states
  32.                         // on the boundary.
  33.                         value[n][i][j][k] = ((i + k >= win) ? 1 : 0);
  34.                     }
  35.                 }
  36.             }
  37.         }
  38.  
  39.         // Iterate state transitions.
  40.         double err = 2;
  41.         int n = 0;
  42.         int iterations = 0;
  43.         while (err > tolerance || n == 0)
  44.         {
  45.             int m = 1 - n;
  46.             err = 0;
  47.             for (int i = 0; i < win; ++i)
  48.             {
  49.                 for (int j = 0; j < win; ++j)
  50.                 {
  51.                     for (int k = 0; k < win - i; ++k)
  52.                     {
  53.                         double v = std::max(
  54.                             value_hold(i, j, k, m),
  55.                             value_roll(i, j, k, m));
  56.                         value[n][i][j][k] = v;
  57.                         err = std::max(err, std::abs(v - value[m][i][j][k]));
  58.                     }
  59.                 }
  60.             }
  61.             n = 1 - n;
  62.             ++iterations;
  63.         }
  64.         return iterations;
  65.     }
  66.  
  67.     // Return probability of the current player winning by passing the die with
  68.     // score i, opponent score j, and current roll total k.
  69.     double value_hold(int i, int j, int k, int m = 0)
  70.     {
  71.         return 1 - value[m][j][i + k][0];
  72.     }
  73.  
  74.     // Return probability of the current player winning by rolling the die with
  75.     // score i, opponent score j, and current roll total k.
  76.     double value_roll(int i, int j, int k, int m = 0)
  77.     {
  78.         double v = 1 - value[m][j][i][0];
  79.         for (int roll = 1; roll <= roll_max; ++roll)
  80.         {
  81.             if (roll != roll_pig)
  82.             {
  83.                 v += value[m][i][j][k + roll];
  84.             }
  85.         }
  86.         return v / roll_max;
  87.     }
  88. };
  89.  
  90. int main()
  91. {
  92.     Pig *pig = new Pig;
  93.     int iterations = pig->reset();
  94.  
  95.     // Display tuples (i, j, k, v_hold, v_roll).
  96.     for (int i = 0; i < 100; ++i)
  97.     {
  98.         for (int j = 0; j < 100; ++j)
  99.         {
  100.             for (int k = 0; k < 100 - i; ++k)
  101.             {
  102.                 std::cout << i << " " << j << " " << k << " " <<
  103.                     (pig->value_hold(i, j, k) < pig->value_roll(i, j, k)) <<
  104.                     std::endl;
  105.             }
  106.         }
  107.     }
  108.     delete pig;
  109. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top