Advanced Search
Article Contents
Article Contents

A non-iterative algorithm for generalized pig games

  • * Corresponding author: Ernesto Mordecki

    * Corresponding author: Ernesto Mordecki
Abstract Full Text(HTML) Figure(1) / Table(4) Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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 <a$ and $v(b, a, \tau)\colon 0\leq \tau <b$
    4:   end for
    5: end for
     | Show Table
    DownLoad: CSV
    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
     | Show Table
    DownLoad: CSV

    Table 1.  Pig Game with different targets

    Target of the game ($N$)value of the game $v(N, N)$
    1 Obtained by Neller and Presser [16]
     | Show Table
    DownLoad: CSV

    Table 2.  Values of $v(a, b)$ for the piglet game with $N = 3$

     | Show Table
    DownLoad: CSV
  • [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šekM. 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. TripathiE. 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. VriezeS. H. TijsT. E. S. Raghavan and J. A. Filar, A finite algorithm for the switching control stochastic game, Operations-Research-Spektrum, 5 (1983), 15-24. 
  • 加载中




Article Metrics

HTML views(586) PDF downloads(218) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint