论文标题
一般警察和强盗游戏随机性
General Cops and Robbers Games with randomness
论文作者
论文摘要
在过去的几十年中，在计算机科学和数学方面已经研究了警察和强盗游戏。就像一般追求逃避游戏一样，追随者（警察）试图占领逃避者（强盗）；但是，玩家依次移动并受到约束以在离散结构（通常是图形）上移动，并知道对手的确切位置。 2017年，Bonato和MacGillivray对警察和强盗游戏进行了一般性表征，以便将其全球研究。但是，他们的模型不涵盖可能发生随机事件的情况，例如强盗以随机的方式移动。在本文中，我们介绍了一个新颖的模型，该模型具有随机元素，我们称之为广义的概率警察和强盗游戏（GPCR）。典型的这样的游戏是强盗根据概率分布进行移动的游戏，因为她既迷失又醉，而不是逃避，或者是因为她是机器人。我们提出了解决GPCR游戏的结果，从而使人们能够研究与大型警察和强盗游戏中最佳策略有关的属性。一些经典的警察和强盗游戏属性也被扩展。
Cops and Robbers games have been studied for the last few decades in computer science and mathematics. As in general pursuit evasion games, pursuers (cops) seek to capture evaders (robbers); however, players move in turn and are constrained to move on a discrete structure, usually a graph, and know the exact location of their opponent. In 2017, Bonato and MacGillivray presented a general characterization of Cops and Robbers games in order for them to be globally studied. However, their model doesn't cover cases where stochastic events may occur, such as the robbers moving in a random fashion. In this paper we present a novel model with stochastic elements that we call a Generalized Probabilistic Cops and Robbers game (GPCR). A typical such game is one where the robber moves according to a probabilistic distribution, either because she is rather lost or drunk than evading, or because she is a robot. We present results to solve GPCR games, thus enabling one to study properties relating to the optimal strategies in large classes of Cops and Robbers games. Some classic Cops and Robbers games properties are also extended.
