Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-16T18:01:24.618Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimax functions on Galton–Watson trees

Part of: Stochastic processes Game theory Markov processes

Published online by Cambridge University Press:  06 December 2019

James B. Martin  and
Roman Stasiński
James B. Martin
Affiliation:
Department of Statistics, University of Oxford, Oxford OX1 3LB, UK Email: [email protected]
Roman Stasiński
Affiliation:
Department of Statistics, University of Oxford, Oxford OX1 3LB, UK Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the behaviour of minimax recursions defined on random trees. Such recursions give the value of a general class of two-player combinatorial games. We examine in particular the case where the tree is given by a Galton–Watson branching process, truncated at some depth 2n, and the terminal values of the level 2n nodes are drawn independently from some common distribution. The case of a regular tree was previously considered by Pearl, who showed that as n → ∞ the value of the game converges to a constant, and by Ali Khan, Devroye and Neininger, who obtained a distributional limit under a suitable rescaling.

For a general offspring distribution, there is a surprisingly rich variety of behaviour: the (unrescaled) value of the game may converge to a constant, or to a discrete limit with several atoms, or to a continuous distribution. We also give distributional limits under suitable rescalings in various cases.

We also address questions of endogeny. Suppose the game is played on a tree with many levels, so that the terminal values are far from the root. To be confident of playing a good first move, do we need to see the whole tree and its terminal values, or can we play close to optimally by inspecting just the first few levels of the tree? The answers again depend in an interesting way on the offspring distribution.

We also mention several open questions.

MSC classification

Primary: 60J80: Branching processes (Galton-Watson, birth-and-death, etc.)
Secondary: 60G99: None of the above, but in this section 91A46: Combinatorial games
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 3 , May 2020 , pp. 455 - 484
Copyright
© Cambridge University Press 2019

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

Aldous, D. J. and Bandyopadhyay, A. (2005) A survey of max-type recursive distributional equations. Ann. Appl. Probab. 15 1047–1110.CrossRefGoogle Scholar
Ali Khan, T., Devroye, L. and Neininger, R. (2005) A limit law for the root value of minimax trees. Electron. Comm. Probab. 10 273–281.CrossRefGoogle Scholar
Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987) Regular Variation, Vol. 27 of Encyclopedia of Mathematics and its Applications, Cambridge University Press.CrossRefGoogle Scholar
Broutin, N., Devroye, L. and Fraiman, N. (2018) Recursive functions on conditional Galton–Watson trees. arXiv:1805.09425Google Scholar
Broutin, N. and Mailler, C. (2018) And/or trees: A local limit point of view. Random Struct. Alg. 53 15–58.CrossRefGoogle Scholar
Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S. and Colton, S. (2012) A survey of Monte Carlo tree search methods. IEEE Trans. Comput. Intell. AI Games 4 1–43.CrossRefGoogle Scholar
Gelly, S., Kocsis, L., Schoenauer, M., Sebag, M., Silver, D., Szepesvári, C. and Teytaud, O. (2012) The grand challenge of computer Go: Monte Carlo tree search and extensions. Comm. Assoc. Comput. Mach. 55 106–113.Google Scholar
Holroyd, A. E. and Martin, J. B. (2019) Galton–Watson games. arXiv:1904.04150Google Scholar
Mach, T., Sturm, A. and Swart, J. M. (2018) A new characterization of endogeny. Math. Phys. Anal. Geom. 21 30.CrossRefGoogle Scholar
Pearl, J. (1980) Asymptotic properties of minimax trees and game-searching procedures. Artif. Intell. 14 113–138.CrossRefGoogle Scholar
Pemantle, R. and Ward, M. D. (2006) Exploring the average values of Boolean functions via asymptotics and experimentation. In Proceedings of the Workshop on Analytic Algorithmics and Combinatorics (ANALCO), SIAM, pp. 253–262.CrossRefGoogle Scholar
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M.et al. (2016) Mastering the game of Go with deep neural networks and tree search. Nature 529 (7587) 484–489.CrossRefGoogle ScholarPubMed