Viliam Lisy

IS Journal 2016 Journal Article

Case Studies of Network Defense with Attack Graph Games

• Karel Durkota
• Viliam Lisy
• Christopher Kiekintveld
• Branislav Bosansky
• Michal Pechoucek

The increasing complexity of securing modern computer networks makes decision support systems an important tool for administrators. A challenge many existing tools fail to address is that attackers react strategically to new security measures, adapting their behaviors in response. Game theory provides a methodology for making decisions that takes into account these reactions, rather than assuming static attackers. The authors present an overview of how game theory can be used to inform one type of security decision: how to optimally place honeypots in a network. They demonstrate this approach on a realistic case study and present initial validation results based on a study comparing their approach with human decision makers.

AAAI Conference 2016 Conference Paper

Counterfactual Regret Minimization in Sequential Security Games

• Viliam Lisy
• Trevor Davis
• Michael Bowling

IJCAI Conference 2016 Conference Paper

Monte Carlo Tree Search in Continuous Action Spaces with Execution Uncertainty

• Timothy Yee
• Viliam Lisy
• Michael Bowling

Real world applications of artificial intelligence often require agents to sequentially choose actions from continuous action spaces with execution uncertainty. When good actions are sparse, domain knowledge is often used to identify a discrete set of promising actions. These actions and their uncertain effects are typically evaluated using a recursive search procedure. The reduction of the problem to a discrete search problem causes severe limitations, notably, not exploiting all of the sampled outcomes when evaluating actions, and not using outcomes to help find new actions outside the original set. We propose a new Monte Carlo tree search (MCTS) algorithm specifically designed for exploiting an execution model in this setting. Using kernel regression, it generalizes the information about action quality between actions and to unexplored parts of the action space. In a high fidelity simulator of the olympic sport of curling, we show that this approach significantly outperforms existing MCTS methods.

AAAI Conference 2016 Conference Paper

Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games

• Jiri Cermak
• Branislav Bosansky
• Karel Durkota
• Viliam Lisy
• Christopher Kiekintveld

Strong Stackelberg Equilibrium (SSE) is a fundamental solution concept in game theory in which one player commits to a strategy, while the other player observes this commitment and plays a best response. We present a new algorithm for computing SSE for two-player extensive-form general-sum games with imperfect information (EFGs) where computing SSE is an NP-hard problem. Our algorithm is based on a correlated version of SSE, known as Stackelberg Extensive- Form Correlated Equilibrium (SEFCE). Our contribution is therefore twofold: (1) we give the first linear program for computing SEFCE in EFGs without chance, (2) we repeatedly solve and modify this linear program in a systematic search until we arrive to SSE. Our new algorithm outperforms the best previous algorithms by several orders of magnitude.

NeurIPS Conference 2013 Conference Paper

Convergence of Monte Carlo Tree Search in Simultaneous Move Games

• Viliam Lisy
• Vojta Kovarik
• Marc Lanctot
• Branislav Bosansky

In this paper, we study Monte Carlo tree search (MCTS) in zero-sum extensive-form games with perfect information and simultaneous moves. We present a general template of MCTS algorithms for these games, which can be instantiated by various selection methods. We formally prove that if a selection method is $\epsilon$-Hannan consistent in a matrix game and satisfies additional requirements on exploration, then the MCTS algorithm eventually converges to an approximate Nash equilibrium (NE) of the extensive-form game. We empirically evaluate this claim using regret matching and Exp3 as the selection methods on randomly generated and worst case games. We confirm the formal result and show that additional MCTS variants also converge to approximate NE on the evaluated games.

IJCAI Conference 2013 Conference Paper

Using Double-Oracle Method and Serialized Alpha-Beta Search for Pruning in Simultaneous Move Games

• Branislav Bosansky
• Viliam Lisy
• Jiri Cermák
• Roman Vítek
• Michal Pechoucek

We focus on solving two-player zero-sum extensive-form games with perfect information and simultaneous moves. In these games, both players fully observe the current state of the game where they simultaneously make a move determining the next state of the game. We solve these games by a novel algorithm that relies on two components: (1) it iteratively solves the games that correspond to a single simultaneous move using a double-oracle method, and (2) it prunes the states of the game using bounds on the sub-game values obtained by the classical Alpha-Beta search on a serialized variant of the game. We experimentally evaluate our algorithm on the Goofspiel card game, a pursuitevasion game, and randomly generated games. The results show that our novel algorithm typically provides significant running-time improvements and reduction in the number of evaluated nodes compared to the full search algorithm.