Finding optimal strategies for group deception games

Abstract

We present a solution method for deception-based games, which are zero-sum games without perfect information, and apply it to the popular party game The Resistance. The methods presented include adaptations of the techniques from (KOLLER; MEGIDDO; von Stengel, 1994), together with novel improvements such as symmetry reductions. These methods allow us to solve the game with up to 8 players, which would require the analysis of 8:5 1011 game tree nodes, if without symmetry reductions, and even more without knowledge trees.

Apresentamos um método de solução para jogos de estratagemas — jogos de soma zero sem informação perfeita — e o aplicamos ao popular jogo The Resistance. Os métodos apresentados incluem adaptações das técnicas de (KOLLER; MEGIDDO; von Stengel, 1994), além de novas melhorias como, por exemplo, reduções de simetrias. Esses métodos permitem soluções para até 8 jogadores, o que necessitaria a análise de 8:5 1011 nodos da árvore do jogo caso não utilizássemos reduções de simetria, e um número maior ainda caso não utilizássemos árvores de conhecimento.