Mixed Strategy Extraction from UCT Tree in Security Games

摘要

In this paper a simulation-based approach to finding optimal defender strategy in multi-act Security Games (SG) played on a graph is proposed. The method employs the Upper Confidence Bounds applied to Trees (UCT) algorithm which relies on massive simulations of possible game scenarios. Three different variants of the algorithm are presented and compared with each other as well as against the Mixed Integer Linear Program (MILP) exact solution in terms of computational efficiency and memory requirements. Experimental evaluation shows that the method has a few times lower memory demands and is faster than MILP approach in majority of test cases while preserving quality of the resulting mixed strategies.