The tree search game for two players

zbMATH Open1490.05180arXiv2008.11543MaRDI QIDQ5080909FDOQ5080909

Authors: Ravi B. Boppana, Joel Brewster Lewis 

Publication date: 31 May 2022

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).

Full work available at URL: https://arxiv.org/abs/2008.11543

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

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Search games on trees with asymmetric travel times
• A SEARCH GAME WITH TRAVELING COST ON A TREE

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)