Two hide-search games with rapid strategies for multiple parallel searches

Abstract

Making a rapid unpredictable decision from NN choices of unequal value is a common control task. When the cost of predictability can be modelled as a penalty hidden under a single option by an intelligent adversary, then an optimal strategy can be found efficiently in O(NlogN)O\left(N\log N) steps using an approach described by Sakaguchi for a zero-sum hide-search game. In this work, we extend this to two games with multiple parallel predictions, either coordinated or drawn independently from the optimal distribution, both of which can be solved with the same scaling. An open-source code is provided online at https://github.com/pec27/rams.

Keywords

• hide-search game
• artificial intelligence in video games
• game artificial intelligence
• game theory
• algorithms