Shortest-path games are two-player zero-sum games played on a graph equipped with integer weights. One player, that we call Min, wants to reach a target set of states while minimising the total weight, and the other one has an antagonistic objective. This combination of a qualitative reachability objective and a quantitative total-payoff objective is one of the simplest setting where Min needs memory (pseudo-polynomial in the weights) to play optimally. In this article, we aim at studying a tradeoff allowing Min to play at random, but using no memory. We show that Min can achieve the same optimal value in both cases. In particular, we compute a randomised memoryless $\varepsilon$-optimal strategy when it exists, where probabilities are parametrised by $\varepsilon$. We then characterise, and decide in polynomial time, the class of games admitting an optimal randomised memoryless strategy.
翻译:最短路径的游戏是在配有整数重量的图表上玩的双玩游戏零和游戏。 一个玩家, 我们称之为敏, 想要达到一组目标, 同时最小化总重量, 而另一个玩家则想要达到一组国家的目标, 而另一个玩家则具有对抗性的目标。 这种质量可达性目标和量化总回报目标的结合, 是Min需要记忆( 重量的假体- Polynomial ) 最优化地玩游戏的最简单环境之一 。 在此篇文章中, 我们的目标是研究一个折中法, 允许 Min 随机玩耍, 但是没有内存 。 我们显示 Min 在两种情况下都能达到相同的最佳值 。 特别是, 我们计算出一个随机化的内存 $\ varepsilon- 最佳策略, 其概率由 $\ varepsilon 匹配 。 我们然后在多音制时间决定一个游戏的类别, 接受一个最优随机化的无记忆策略 。