• API
• FAQ
• Tools
• Archive
daily pastebin goal
37%
SHARE
TWEET

# Pig dice game optimal strategy

a guest Mar 2nd, 2014 109 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.                     {
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.

Top