Article Contents
Article Contents

A non-iterative algorithm for generalized pig games

• * Corresponding author: Ernesto Mordecki
• We provide a polynomial algorithm to find the value and an optimal strategy for a generalization of the Pig game. Modeled as a competitive Markov decision process, the corresponding Bellman equations can be decoupled leading to systems of two non-linear equations with two unknowns. In this way we avoid the classical iterative approaches. A simple complexity analysis reveals that the algorithm requires $O(\mathbf{s}\log\mathbf{s})$ steps, where $\mathbf{s}$ is the number of states of the game. The classical Pig and the Piglet (a simple variant of the Pig played with a coin) are examined in detail.

Mathematics Subject Classification: Primary: 91A15, 91A60; Secondary: 90C47.

 Citation:

• Figure 1.  Function $y = f_{b, a}(x)$ (solid line) intersects $x = f_{a, b}(y)$ (dashed line) at the solution $x = v(a, b)$, $y = v(b, a)$ in one instance of the Piglet game

 Algorithm 1 General backward algorithm. 1: for $b$ from $1$ to $N$ do 2:   for $a$ from $1$ to $b$ do 3: Find $v(a, b, \tau)\colon 0\leq \tau  Algorithm 2 Solving step 3 for fixed a, b. 1: for$i$from$1$to$a$do 2: Find the points defining$f_{a, b, i}$3: end for 4: for$i$from$1$to$b$do 5: Find the points defining$f_{b, a, i}$6: end for 7: Find$x$and$y$that solve system (7) 8: for$i$from$1$to$a-1$do 9: compute v(a, b, a-i) 10: end for 11: for$i$from$1$to$b-1$do 12: compute v(b, a, b-i) 13: end for Table 1. Pig Game with different targets  Target of the game ($N$) value of the game$v(N, N)$10 0.70942388 50 0.54615051 100 0.530592071 200 0.52152913 500 0.51362019 1000 0.50963900 1 Obtained by Neller and Presser [16] Table 2. Values of$v(a, b)$for the piglet game with$N = 3\$

•  [1] D. Auger, P. Coucheney and Y. and Strozecki, Finding optimal strategies of almost acyclic simple stochastic games, Theory and applications of models of computation, Lecture Notes in Comput. Sci., 8402 (2014), 67–85. [2] M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, (2nd. rev. ed.) Springer, Berlin 2000. doi: 10.1007/978-3-662-04245-8. [3] A. Condon, The complexity of stochastic games, Information and Computation, 96 (1992), 203-224.  doi: 10.1016/0890-5401(92)90048-K. [4] A. Condon, On algorithms for simple stochastic games, Advances in Computational Complexity Theory, J. Cai (Ed.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science AMS, 14 (1993), 51–71. [5] J. Filar and K. Vrieze, Competitive Markov Decision Processes, Springer, New York, 1997. [6] H. Gimbert and F. Horn, Simple stochastic games with few random vertices are easy to solve, Foundations of software science and computational structures, 5–19, Lecture Notes in Comput. Sci., 4962, Springer, Berlin. 2008 doi: 10.1007/978-3-540-78499-9_2. [7] J. Haigh and M. Roters, Optimal strategy in a dice game, Journal of Applied Probability, 37 (2000), 1110-1116.  doi: 10.1239/jap/1014843089. [8] N. Halman, Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems, Algorithmica, 49 (2007), 37-50.  doi: 10.1007/s00453-007-0175-3. [9] T. D. Hansen, P. B. Miltersen and U. Zwick, Strategy iteration is strongly polynomial for 2- player turn-based stochastic games with a constant discount factor, Innovations in Computer Science (ICS'11), (2011), 253–263. [10] A. J. Hoffman and R. M. Karp, On nonterminating stochastic games, Management Science, 12 (1966), 359-370.  doi: 10.1287/mnsc.12.5.359. [11] R. Ibsen-Jensen and P. B. Miltersen, Solving simple stochastic games with few coin toss positions, Algorithms–ESA 20112, LNCS, 7501 (2012), 636–647. doi: 10.1007/978-3-642-33090-2_55. [12] G. Louchard, Recent studies on the dice race problem and its connections, Math. Appl. (Warsaw), 44 (2106), 63-86.  doi: 10.14708/ma.v44i1.1124. [13] T. M. Liggett and S. A. Lippman, Stochastic games with perfect information and time average payoff, SIAM Review, 11 (1969), 604-607.  doi: 10.1137/1011093. [14] J. Matoušek, M. Sharir and E. Welzl, A subexponential bound for linear programming, Algorithmica, 16 (1996), 498-516.  doi: 10.1007/BF01940877. [15] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, New Jersey. 1944. [16] T. Neller and C. Presser, Optimal play of the dice game pig, The UMAP Journal, 25 (2004), 25-47. [17] M. Roters, Optimal stopping in a dice game, Journal of Applied Probability, 35 (1998), 229-235.  doi: 10.1239/jap/1032192566. [18] L. S. Shapley, Stochastic games, Proceedings of the Natural Academy of Sciences, USA, 39 (1953), 1095-1100.  doi: 10.1073/pnas.39.10.1953. [19] R. Tripathi, E. Valkanova and V. S. Anil Kumar, On strategy improvement algorithms for simple stochastic games, Journal of Discrete Algorithms, 9 (2011), 263-278.  doi: 10.1016/j.jda.2011.03.007. [20] H. Tijms, Dice games and stochastic dynamic programming, Morfismos, 11 (2004), 1-14. [21] H. Tijms and J. van der Wal, A real-world stochastic two-person game, Probab. Engrg. Inform. Sci., 20 (2006), 599-608.  doi: 10.1017/S0269964806060372. [22] O. J. Vrieze, S. H. Tijs, T. E. S. Raghavan and J. A. Filar, A finite algorithm for the switching control stochastic game, Operations-Research-Spektrum, 5 (1983), 15-24.

Figures(1)

Tables(4)