论文标题
两个玩家的树搜索游戏
The tree search game for two players
论文作者
论文摘要
我们考虑在树$ t $上的两人搜索游戏。一个顶点（玩家未知）被随机选择为目标。玩家交替猜测顶点。如果猜测$ v $不是目标，那么两个玩家都将在哪个$ t \ smallsetminus v $的子树中获悉。获胜者是猜测目标的球员。 当两个玩家最佳地打球时，我们都表明他们每个人都以大约$ 1/2 $的可能性获胜。当一个玩家发挥最佳作用，另一个玩家随机播放时，我们表明具有最佳策略的玩家以$ 9/16 $和$ 2/3 $（渐近）（渐近）获胜。当两个玩家随机打球时，我们都表明，每个玩家都以$ 13/30 $和$ 17/30 $的概率（渐近）获胜。
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 $T \smallsetminus v$ 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).
