Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-24T19:03:47.694Z Has data issue: false hasContentIssue false
  • English
  • Français

A finite exact algorithm to solve a dice game

Published online by Cambridge University Press:  24 March 2016

Fabián Crocce  and
Ernesto Mordecki
Ernesto Mordecki
Affiliation:
Centro de Matemática, Facultad de Ciencias, Universidad de la República, Iguá 4225, CP 11400 Montevideo, Uruguay.
Get access Rights & Permissions [Opens in a new window]

Abstract

We provide an algorithm to find the value and an optimal strategy of the Ten Thousand dice game solitaire variant in the framework of Markov control processes. Once an optimal critical threshold is found, the set of nonstopping states of the game becomes finite and the solution is found by a backwards algorithm that gives the values for each one of these states of the game. The algorithm is finite and exact. The strategy to find the critical threshold comes from the continuous pasting condition used in optimal stopping problems for continuous-time processes with jumps.

Keywords

Markov control processdice gameoptimal controlfinite exact algorithm
Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 1 , March 2016 , pp. 91 - 105
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Blackwell, D. (1967). Positive dynamic programming. In Proc. Fifth Berkeley Symp. Math. Statist. Prob. (Berkeley, CA, 1965/66), Vol. I, Statistics, University of California Press, pp. 415–418. Google Scholar
[2]Filar, J. and Vrieze, K. (1997). Competitive Markov Decision Processes. Springer, New York. Google Scholar
[3]Haigh, J. and Roters, M. (2000). Optimal strategy in a dice game. J. Appl. Prob. 37, 1110–1116. Google Scholar
[4]Hald, A. (1990). A History of Probability and Statistics and Their Applications Before 1750. John Wiley, New York. Google Scholar
[5]Hernández-Lerma, O., Carrasco, G. and Pérez-Hernández, R. (1999). Markov control processes with the expected total cost criterion: optimality, stability, and transient models. Acta Appl. Math. 59, 229–269. CrossRefGoogle Scholar
[6]Mordecki, E. (1999). Optimal stopping for a diffusion with jumps. Finance Stoch. 3, 227–236. Google Scholar
[7]Neller, T. W. and Presser, C. G. M. (2004). Optimal play of the dice game pig. The UMAP J. 25, 25–47. Google Scholar
[8]Pliska, S. R. (1978). On the transient case for Markov decision chains with general state spaces. In Dynamic Programming and Its Applications (Proc. Conf., University of British Columbia, Vancouver, 1977), Academic Press, New York, pp. 335–349. Google Scholar
[9]Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley, New York. Google Scholar
[10]Roters, M. (1998). Optimal stopping in a dice game. J. Appl. Prob. 35, 229–235. Google Scholar
[11]Tijms, H. (2007). Dice games and stochastic dynamic programming. Morfismos 11, 1–14. Google Scholar
[12]Tijms, H. and van der Wal, J. (2006). A real-world stochastic two-person game. Prob. Eng. Inf. Sci. 20, 599–608. CrossRefGoogle Scholar