Agent subset adversarial search for complex non-cooperative domains

We investigate reduction of the complexity of a multi-agent adversarial search in the domain of n-player games. We describe a method that decomposes the game into a set of smaller overlapping sub-games, solves each sub-game separately, and then combines the results into a global solution. This way, the exponential dependence of the adversarial search complexity on the number of agents can be reduced to polynomial. Still, the proposed method performs well in the domains with sparse agents´ interactions. The method can be used with a generic adversarial search algorithm. For the experimental evaluation, we implement it on top of an existing adversarial search algorithm designed for complex domains and we evaluate its performance on a game, which is a model of a humanitarian relief operation in conflict environment. The results show that the method often finds the same solutions as the complete search, but the search efficiency is significantly improved.