Mixed Strategy Extraction from UCT Tree in Security Games

Jan Karwowski , Jacek Mańdziuk

Abstract

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.
Author Jan Karwowski ZSIMO
Jan Karwowski,,
- Department of Artificial Intelligence and Computational Methods
, Jacek Mańdziuk ZSIMO
Jacek Mańdziuk,,
- Department of Artificial Intelligence and Computational Methods
Pages1746-1747
Publication size in sheets0.3
Book Kaminka Gal A., Fox Maria, Bouquet Paolo, Dignum Virginia, Dignum Frank, van Harmelen Frank (eds.): The proceedings of the Twenty-second European Conference on Artificial Intelligence (ECAI 2016), Frontiers in Artificial Intelligence and Applications, vol. 285, 2016, IOS Press, ISBN 978-1-61499-671-2, [978-1-61499-672-9], 1834 p., DOI:10.3233/978-1-61499-672-9-90
Keywords in EnglishStrong Stackelberg Equilibrium, mixed strategy, UCT, Security Games
Abstract in PolishPraca wprowadza nową metodę znajdowania przybliżonej strategii lidera w grach Stackelberga przy użyciu wielokrotnych symulacji Monte-Carlo. Część eksperymentalna pracy pokazuje, że metoda jest w stanie znaleźć dobre (w sensie wartości oczekiwanej wyniku gry) strategie przy znacznie mniejszym wykorzystaniu pamięci w porównaniu w metodą dokładną.
DOIDOI:10.3233/978-1-61499-672-9-1746
URL http://ebooks.iospress.com/volumearticle/45012
Languageen angielski
Score (nominal)15
ScoreMinisterial score [Punktacja MNiSW] = 15.0, 22-06-2017, BookChapterSeriesAndMatConf
Ministerial score (2013-2016) [Punktacja MNiSW (2013-2016)] = 15.0, 22-06-2017, BookChapterSeriesAndMatConf
Citation count*0
Cite
Share Share

Get link to the record
msginfo.png


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back