Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T09:14:04.758Z 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.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 1 , March 2016 , pp. 91 - 105
Copyright
Copyright © Applied Probability Trust 2016 

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