scientific article; zbMATH DE number 3900780
[For the entire collection see Zbl 0547.00011.] The authors consider the following game, played on a finite rooted tree by two players who take alternating turns: the first player occupies a node adjacent to the root; on succeeding turns a player occupies a previously-unoccupied node adjacent to the one last occupied, if such a node exists. The winner is the player who first occupies an end-node. A tree is winning if the first player has a winning strategy; if not, then the second player has a winning strategy and the tree is called losing. In the first part of the paper the authors show that for a certain kind of family of trees called simply-generated (a condition on the generating function for the number of n-node trees in the family, implying that if the root is removed from a tree in the family, all the remaining components are members of the family), the ratio of winning n-trees to all n-trees in the family approaches a limit. This limit is at least one- half for any simply-generated family; its value is given for certain common families such as the family of binary trees. In the remainder of the paper the authors restrict the strategies allowed the players to a certain class (the admissible strategies), and consider the probability that the first player wins if an n-node tree is chosen at random from a simply-generated family of trees and the players adopt a fixed pair of admissible strategies. An expression for the limiting value of this probability is obtained, and is evaluated for certain families of trees and certain pairs of simple strategies.
- Trees and Ehrenfeucht-Fraïssé games
- Tree-connected peer group situations and peer group games
- When does a random Robin Hood win?
- The eigen-distribution of weighted game trees
- The asymptotic behaviour of coefficients of powers of certain generating functions
- Enumeration by kernel positions for strongly Bernoulli type truncation games on words
- Golden games
- Timber game as a counting problem
- Percolation and the complexity of games
- Extended Sprague-Grundy theory for locally finite games, and applications to random game-trees
- Thick Subtrees, Games and Experiments
- scientific article; zbMATH DE number 3902439 (Why is no real title available?)
- scientific article; zbMATH DE number 4097150 (Why is no real title available?)
- The Variance of Two Game Tree Algorithms
- Games with Unknown Past
- On majority voting games in trees
- Games characterizing Levy-Longo trees.
- scientific article; zbMATH DE number 850228 (Why is no real title available?)
- Minimax functions on Galton-Watson trees
- scientific article; zbMATH DE number 7362735 (Why is no real title available?)
- ``Pass the buck on a complete binary tree
- Combinatorial games on multi-type Galton-Watson trees
- Galvin’s “racing pawns” game and a well-ordering of trees
- The game of timber!
- Disks on a Tree: Analysis of a Combinatorial Game
- “Pass the Buck” on a Rooted Tree
- Galton–Watson games
- On the number of matchings of a tree
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3679207)