The tree search game for two players

MaRDI QIDQ5080909zbMATH OpenFDO

Authors Ravi B. Boppana, Joel Brewster Lewis

Publication date 31 May 2022

Full work available at URL https://arxiv.org/abs/2008.11543, http://ajc.maths.uq.edu.au/pdf/82/ajc_v82_p119.pdf

zbMATH Keywords

star-like treessubdivisions of stars

Mathematics Subject Classification ID

Trees (05C05) 2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: We consider a two-player search game on a tree $T$. One vertex (unknown to the players) is randomly selected as the target. The players alternately guess vertices. If a guess $v$ is not the target, then both players are informed in which subtree of $Tsmallsetminusv$ the target lies. The winner is the player who guesses the target. When both players play optimally, we show that each of them wins with probability approximately $1/2$. When one player plays optimally and the other plays randomly, we show that the player with the optimal strategy wins with probability between $9/16$ and $2/3$ (asymptotically). When both players play randomly, we show that each wins with probability between $13/30$ and $17/30$ (asymptotically).

Recommendations

• A SEARCH GAME WITH TRAVELING COST ON A TREE
• Game tree algorithms and solution trees
• The game of arboricity
• The game of arboricity
• A search game with one object and two searchers
• scientific article; zbMATH DE number 42543
• Trees and Ehrenfeucht-Fraïssé games
• Two-player tower of Hanoi
• A Game Tree Search by Probability Method
• An Evasion Game on a Finite Tree

Cites work

• Cutting down random trees
• Cutting down trees with a Markov chainsaw
• Deterministic and probabilistic binary search in graphs
• Grabbing the gold

Cited in

(3)

• Search games on trees with asymmetric travel times
• scientific article; zbMATH DE number 3900780 (Why is no real title available?)
• A SEARCH GAME WITH TRAVELING COST ON A TREE

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: The tree search game for two players

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080909)