Lidé
doc. Mgr. Viliam Lisý, MSc., Ph.D.
Všechny publikace
Classification with Costly Features in Hierarchical Deep Sets
 Autoři: Ing. Jaromír Janisch, doc. Ing. Tomáš Pevný, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Machine Learning. 2024, 113(7), 44874522. ISSN 08856125.
 Rok: 2024
 DOI: 10.1007/s10994024065654
 Odkaz: https://doi.org/10.1007/s10994024065654
 Pracoviště: Centrum umělé inteligence

Anotace:
Classification with costly features (CwCF) is a classification problem that includes the cost of features in the optimization criteria. Individually for each sample, its features are sequentially acquired to maximize accuracy while minimizing the acquired features' cost. However, existing approaches can only process data that can be expressed as vectors of fixed length. In real life, the data often possesses rich and complex structure, which can be more precisely described with formats such as XML or JSON. The data is hierarchical and often contains nested lists of objects. In this work, we extend an existing deep reinforcement learningbased algorithm with hierarchical deep sets and hierarchical softmax, so that it can directly process this data. The extended method has greater control over which features it can acquire and, in experiments with seven datasets, we show that this leads to superior performance. To showcase the real usage of the new method, we apply it to a reallife problem of classifying malicious web domains, using an online service.
Continual Depthlimited Responses for Computing Counterstrategies in Sequential Games
 Autoři: Ing. David Milec, Ing. Ondřej Kubíček, doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems. County of Richland: IFAAMAS, 2024. p. 23932395. ISSN 15488403.
 Rok: 2024
 Pracoviště: Katedra počítačů, Centrum umělé inteligence

Anotace:
In zerosum games, the optimal strategy is welldefined by the Nash equilibrium. However, it is overly conservative when playing against suboptimal opponents and it can not exploit their weaknesses. Limited lookahead game solving in imperfectinformation games allows superhuman play in massive realworld games such as Poker, Liar's Dice, and Scotland Yard. However, since they approximate Nash equilibrium, they tend to only win slightly against weak opponents. We propose theoretically sound methods combining limited lookahead solving with an opponent model, in order to 1) approximate a best response in large games or 2) compute a robust response with control over the robustness of the response. Both methods can compute the response in real time to previously unseen strategies. We present theoretical guarantees of our methods. We show that existing robust response methods do not work combined with limited lookahead solving of the shelf, and we propose a novel solution for the issue. Our algorithm performs significantly better than multiple baselines in smaller games and outperforms stateoftheart methods against SlumBot.
Lookahead Search on Top of Policy Networks in Imperfect Information Games
 Autoři: Ing. Ondřej Kubíček, Burch, N., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Proceedings of the 33rd International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2024. p. 43444352. ISBN 9781956792041.
 Rok: 2024
 DOI: 10.24963/ijcai.2024/480
 Odkaz: https://doi.org/10.24963/ijcai.2024/480
 Pracoviště: Katedra počítačů, Centrum umělé inteligence

Anotace:
Search in test time is often used to improve the performance of reinforcement learning algorithms. Performing theoretically sound search in fully adversarial twoplayer games with imperfect information is notoriously difficult and requires a complicated training process. We present a method for adding testtime search to an arbitrary policygradient algorithm that learns from sampled trajectories. Besides the policy network, the algorithm trains an additional critic network, which estimates the expected values of players following various transformations of the policies given by the policy network. These values are then used for depthlimited search. We show how the values from this critic can create a value function for imperfect information games. Moreover, they can be used to compute the summary statistics necessary to start the search from an arbitrary decision point in the game. The presented algorithm is scalable to very large games since it does not require any search during train time. We evaluate the algorithm's performance when trained along Regularized Nash Dynamics, and we evaluate the benefit of using the search in the standard benchmark game of Leduc hold'em, multiple variants of imperfect information Goofspiel, and Battleships.
NASimEmu: Network Attack Simulator & Emulator for Training Agents Generalizing to Novel Scenarios
 Autoři: Ing. Jaromír Janisch, doc. Ing. Tomáš Pevný, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Computer Security. ESORICS 2023 International Workshops. Cham: Springer International Publishing, 2024. ISSN 03029743. ISBN 9783031542039.
 Rok: 2024
 Pracoviště: Centrum umělé inteligence

Anotace:
Current frameworks for training offensive penetration testing agents with deep reinforcement learning struggle to produce agents that perform well in realworld scenarios, due to the reality gap in simulationbased frameworks and the lack of scalability in emulationbased frameworks. Additionally, existing frameworks often use an unrealistic metric that measures the agents' performance on the training data. NASimEmu, a new framework introduced in this paper, addresses these issues by providing both a simulator and an emulator with a shared interface. This approach allows agents to be trained in simulation and deployed in the emulator, thus verifying the realism of the used abstraction. Our framework promotes the development of general agents that can transfer to novel scenarios unseen during their training. For the simulation part, we adopt an existing simulator NASim and enhance its realism. The emulator is implemented with industrylevel tools, such as Vagrant, VirtualBox, and Metasploit. Experiments demonstrate that a simulationtrained agent can be deployed in emulation, and we show how to use the framework to train a general agent that transfers into novel, structurally different scenarios. NASimEmu is available as opensource.
Value functions for depthlimited solving in zerosum imperfectinformation games
 Autoři: RNDr. Vojtěch Kovařík, Ph.D., Seitz, D., doc. Mgr. Viliam Lisý, MSc., Ph.D., Rudolf, J., Sun, S., Ha, K.
 Publikace: Artificial Intelligence. 2023, 314 ISSN 18727921.
 Rok: 2023
 DOI: 10.1016/j.artint.2022.103805
 Odkaz: https://doi.org/10.1016/j.artint.2022.103805
 Pracoviště: Centrum umělé inteligence

Anotace:
We provide a formal definition of depthlimited games together with an accessible and rigorous explanation of the underlying concepts, both of which were previously missing in imperfectinformation games. The definition works for an arbitrary (perfect recall) extensiveform game and is not tied to any specific gamesolving algorithm. Moreover, this framework unifies and significantly extends three approaches to depthlimited solving that previously existed in extensiveform games and multiagent reinforcement learning but were not known to be compatible. A key ingredient of these depthlimited games is value functions. Focusing on twoplayer zerosum imperfectinformation games, we show how to obtain optimal value functions and prove that public information provides both necessary and sufficient context for computing them. We provide a domainindependent encoding of the domains that allows for approximating value functions even by simple feedforward neural networks, which are then able to generalize to unseen parts of the game. We use the resulting value network to implement a depthlimited version of counterfactual regret minimization. In three distinct domains, we show that the algorithm's exploitability is roughly linearly dependent on the value network's quality and that it is not difficult to train a value network with which depthlimited CFR's performance is as good as that of CFR with access to the full game.
JsonGrinder.jl: Automated Differentiable Neural Architecture for Embedding Arbitrary JSON Data
 Autoři: Mandlík, Š., Račinský, M., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Ing. Tomáš Pevný, Ph.D.,
 Publikace: Journal of Machine Learning Research. 2022, 23 15. ISSN 15324435.
 Rok: 2022
 Pracoviště: Centrum umělé inteligence

Anotace:
Standard machine learning (ML) problems are formulated on data converted into a suitable tensor representation. However, there are data sources, for example in cybersecurity, that are naturally represented in a unifying hierarchical structure, such as XML, JSON, and Protocol Buffers. Converting this data to a tensor representation is usually done by manual feature engineering, which is laborious, lossy, and prone to bias originating from the human inability to correctly judge the importance of particular features. JsonGrinder.jl is a library automating various ML tasks on these difficult sources. Starting with an arbitrary set of JSON samples, it automatically creates a differentiable ML model (called hmilnet), which embeds raw JSON samples into a fixedsize tensor representation. This embedding network can be naturally extended by an arbitrary ML model expecting tensor inputs in order to perform classification, regression, or clustering.
Rethinking formal models of partially observable multiagent decision making
 Autoři: RNDr. Vojtěch Kovařík, Ph.D., Schmid, M., Burch, N., Bowling, M., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Artificial Intelligence. 2022, 303(103645), 121. ISSN 18727921.
 Rok: 2022
 DOI: 10.1016/j.artint.2021.103645
 Odkaz: https://doi.org/10.1016/j.artint.2021.103645
 Pracoviště: Centrum umělé inteligence

Anotace:
Multiagent decisionmaking in partially observable environments is usually modelled as either an extensiveform game (EFG) in game theory or a partially observable stochastic game (POSG) in multiagent reinforcement learning (MARL). One issue with the current situation is that while most practical problems can be modelled in both formalisms, the relationship of the two models is unclear, which hinders the transfer of ideas between the two communities. A second issue is that while EFGs have recently seen significant algorithmic progress, their classical formalization is unsuitable for efficient presentation of the underlying ideas, such as those around decomposition. To solve the first issue, we introduce factoredobservation stochastic games (FOSGs), a minor modification of the POSG formalism which distinguishes between private and public observation and thereby greatly simplifies decomposition. To remedy the second issue, we show that FOSGs and POSGs are naturally connected to EFGs: by “unrolling” a FOSG into its tree form, we obtain an EFG. Conversely, any perfectrecall timeable EFG corresponds to some underlying FOSG in this manner. Moreover, this relationship justifies several minor modifications to the classical EFG formalization that recently appeared as an implicit response to the model’s issues with decomposition. Finally, we illustrate the transfer of ideas between EFGs and MARL by presenting three key EFG techniques – counterfactual regret minimization, sequence form, and decomposition – in the FOSG framework.
Complexity and Algorithms for Exploiting Quantal Opponents in Large TwoPlayer Games
 Autoři: Ing. David Milec, Černý, J., doc. Mgr. Viliam Lisý, MSc., Ph.D., An, B.
 Publikace: Proceedings of the ThirtyFifth AAAI Conference on Artificial Intelligence. Palo Alto, California: Association for the Advancement of Artificial Intelligence (AAAI), 2021. p. 55755583. 35. ISSN 23743468. ISBN 9781577358664.
 Rok: 2021
 Pracoviště: Katedra počítačů, Centrum umělé inteligence

Anotace:
Solution concepts of traditional game theory assume entirely rational players; therefore, their ability to exploit subrational opponents is limited. One type of subrationality that describes human behavior well is the quantal response. While there exist algorithms for computing solutions against quantal opponents, they either do not scale or may provide strategies that are even worse than the entirelyrational Nash strategies. This paper aims to analyze and propose scalable algorithms for computing effective and robust strategies against a quantal opponent in normalform and extensiveform games. Our contributions are: (1) we define two different solution concepts related to exploiting quantal opponents and analyze their properties; (2) we prove that computing these solutions is computationally hard;(3) therefore, we evaluate several heuristic approximations based on scalable counterfactual regret minimization (CFR); and (4) we identify a CFR variant that exploits the bounded opponents better than the previously used variants while being less exploitable by the worstcase perfectlyrational opponent.
Computing Quantal Stackelberg Equilibrium in ExtensiveForm Games
 Autoři: Černý, J., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., An, B.
 Publikace: Proceedings of the ThirtyFifth AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2021. p. 52605268. ISSN 21595399. ISBN 9781577358664.
 Rok: 2021
 Pracoviště: Centrum umělé inteligence

Anotace:
Deployments of gametheoretic solution concepts in the real world have highlighted the necessity to consider human opponents' boundedly rational behavior. If subrationality is not addressed, the system can face significant losses in terms of expected utility. While there exist algorithms for computing optimal strategies to commit to when facing subrational decisionmakers in oneshot interactions, these algorithms cannot be generalized for solving sequential scenarios because of the inherent curse of strategyspace dimensionality in sequential games and because humans act subrationally in each decision point separately. We study optimal strategies to commit to against subrational opponents in sequential games for the first time and make the following key contributions: (1) we prove the problem is NPhard in general; (2) to enable further analysis, we introduce a nonfractional reformulation of the direct nonconcave representation of the equilibrium; (3) we identify conditions under which the problem can be approximated in polynomial time in the size of the representation; (4) we show how an MILP can approximate the reformulation with a guaranteed bounded error, and (5) we experimentally demonstrate that our algorithm provides higher quality results several orders of magnitude faster than a baseline method for general nonlinear optimization.
Analysis of Hannan consistent selection for Monte Carlo tree search in simultaneous move games
 Autoři: RNDr. Vojtěch Kovařík, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Machine Learning. 2020, 109(1), 150. ISSN 08856125.
 Rok: 2020
 DOI: 10.1007/s1099401905832z
 Odkaz: https://doi.org/10.1007/s1099401905832z
 Pracoviště: Centrum umělé inteligence

Anotace:
Hannan consistency, or no external regret, is a key concept for learning in games. An action selection algorithm is Hannan consistent (HC) if its performance is eventually as good as selecting the best fixed action in hindsight. If both players in a zerosum normal form game use a Hannan consistent algorithm, their average behavior converges to a Nash equilibrium of the game. A similar result is known about extensive form games, but the played strategies need to be Hannan consistent with respect to the counterfactual values, which are often difficult to obtain. We study zerosum extensive form games with simultaneous moves, but otherwise perfect information. These games generalize normal form games and they are a special case of extensive form games. We study whether applying HC algorithms in each decision point of these games directly to the observed payoffs leads to convergence to a Nash equilibrium. This learning process corresponds to a class of Monte Carlo Tree Search algorithms, which are popular for playing simultaneousmove games but do not have any known performance guarantees. We show that using HC algorithms directly on the observed payoffs is not sufficient to guarantee the convergence. With an additional averaging over joint actions, the convergence is guaranteed, but empirically slower. We further define an additional property of HC algorithms, which is sufficient to guarantee the convergence without the averaging and we empirically show that commonly used HC algorithms have this property.
Automated Construction of Boundedloss Imperfectrecall Abstractions in Extensiveform Games
 Autoři: Čermák, J., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D.,
 Publikace: Artificial Intelligence. 2020, 282 ISSN 00043702.
 Rok: 2020
 DOI: 10.1016/j.artint.2020.103248
 Odkaz: https://doi.org/10.1016/j.artint.2020.103248
 Pracoviště: Centrum umělé inteligence

Anotace:
Extensiveform games (EFGs) model finite sequential interactions between players. The amount of memory required to represent these games is the main bottleneck of algorithms for computing optimal strategies and the size of these strategies is often impractical for realworld applications. A common approach to tackle the memory bottleneck is to use information abstraction that removes parts of information available to players thus reducing the number of decision points in the game. However, existing informationabstraction techniques are either specific for a particular domain, they do not provide any quality guarantees, or they are applicable to very small subclasses of EFGs. We present domainindependent abstraction methods for creating imperfect recall abstractions in extensiveform games that allow computing strategies that are (near) optimal in the original game. To this end, we introduce two novel algorithms, FPIRA and CFR+IRA, based on fictitious play and counterfactual regret minimization. These algorithms can start with an arbitrary domain specific, or the coarsest possible, abstraction of the original game. The algorithms iteratively detect the missing information they require for computing a strategy for the abstract game that is (near) optimal in the original game. This information is then included back into the abstract game. Moreover, our algorithms are able to exploit imperfectrecall abstractions that allow players to forget even history of their own actions. However, the algorithms require traversing the complete unabstracted game tree. We experimentally show that our algorithms can closely approximate Nash equilibrium of large games using abstraction with as little as 0.9% of information sets of the original game. Moreover, the results suggest that memory savings increase with the increasing size of the original games.
Automated construction of boundedloss imperfectrecall abstractions in extensiveform games
 Autoři: Čermák, J., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D.,
 Publikace: Proceedings of the TwentyNinth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2020. p. 50305034. ISBN 9780999241165.
 Rok: 2020
 Pracoviště: Centrum umělé inteligence

Anotace:
Information abstraction is one of the methods for tackling large extensiveform games (EFGs). Removing some information available to players reduces the memory required for computing and storing strategies. We present novel domainindependent abstraction methods for creating very coarse abstractions of EFGs that still compute strategies that are (near) optimal in the original game. First, the methods start with an arbitrary abstraction of the original game (domainspecific or the coarsest possible). Next, they iteratively detect which information is required in the abstract game so that a (near) optimal strategy in the original game can be found and include this information into the abstract game. Moreover, the methods are able to exploit imperfectrecall abstractions where players can even forget the history of their own actions. We present two algorithms that follow these steps  FPIRA, based on fictitious play, and CFR+IRA, based on counterfactual regret minimization. The experimental evaluation confirms that our methods can closely approximate Nash equilibrium of large games using abstraction with only 0.9% of information sets of the original game.
Classification with Costly Features as a Sequential Decisionmaking Problem
 Autoři: Ing. Jaromír Janisch, doc. Ing. Tomáš Pevný, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Machine Learning. 2020, 109(8), 15871615. ISSN 08856125.
 Rok: 2020
 DOI: 10.1007/s10994020058748
 Odkaz: https://doi.org/10.1007/s10994020058748
 Pracoviště: Katedra počítačů, Centrum umělé inteligence

Anotace:
This work focuses on a specific classification problem, where the information about a sample is not readily available, but has to be acquired for a cost, and there is a persample budget. Inspired by realworld usecases, we analyze average and hard variations of a directly specified budget. We postulate the problem in its explicit formulation and then convert it into an equivalent MDP, that can be solved with deep reinforcement learning. Also, we evaluate a realworld inspired setting with sparse training datasets with missing features. The presented method performs robustly well in all settings across several distinct datasets, outperforming other priorart algorithms. The method is flexible, as showcased with all mentioned modifications and can be improved with any domain independent advancement in RL.
Dinkelbachtype algorithm for computing quantal stackelberg equilibrium
 Autoři: Černy, J., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., An, B.
 Publikace: Proceedings of the TwentyNinth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2020. p. 246253. ISBN 9780999241165.
 Rok: 2020
 Pracoviště: Centrum umělé inteligence

Anotace:
Stackelberg security games (SSGs) have been deployed in many realworld situations to optimally allocate scarce resource to protect targets against attackers. However, actual human attackers are not perfectly rational and there are several behavior models that attempt to predict subrational behavior. Quantal response is among the most commonly used such models and Quantal Stackelberg Equilibrium (QSE) describes the optimal strategy to commit to when facing a subrational opponent. Nonconcavity makes computing QSE computationally challenging and while there exist algorithms for computing QSE for SSGs, they cannot be directly used for solving an arbitrary game in the normal form. We (1) present a transformation of the primal problem for computing QSE using a Dinkelbach's method for any generalsum normalform game, (2) provide a gradientbased and a MILPbased algorithm, give the convergence criteria, and bound their error, and finally (3) we experimentally demonstrate that using our novel transformation, a QSE can be closely approximated several orders of magnitude faster.
Discovering Imperfectly Observable Adversarial Actions Using Anomaly Detection
 Autoři: Petrova, O., Durkota, K., Alperovich, G., Horak, K., Najman, M., doc. Mgr. Branislav Bošanský, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. County of Richland: IFAAMAS, 2020. p. 19691971. ISSN 15488403. ISBN 9781450375184.
 Rok: 2020
 Pracoviště: Centrum umělé inteligence

Anotace:
Defenders in security problems often use anomaly detection (AD) to examine effects of (adversarial) actions and detect malicious behavior. Attackers seek to accomplish their goal (e.g., exfiltrate data) while avoiding the detection. Game theory can be used to reason about this interaction. While AD has been used in gametheoretic frameworks before, we extend the existing works to more realistic settings by (1) allowing players to have continuous action spaces and (2) assuming that the defender cannot perfectly observe the action of the attacker. We solve our model by (1) extending existing algorithms that discretize the action spaces and use linear programming and (2) by training a neural network using an algorithm based on exploitability descent, termed EDA. While both algorithms are applicable for low featurespace dimensions, EDA produces less exploitable strategies and scales to higher dimensions. In a data exfiltration scenario, EDA outperforms a range of classifiers when facing a targeted exploitative attacker.
Classification with Costly Features Using Deep Reinforcement Learning
 Autoři: Ing. Jaromír Janisch, doc. Ing. Tomáš Pevný, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Proceedings of the ThirtyThird AAAI Conference on Artificial Intelligence. Menlo Park, California: AAAI Press, 2019. p. 39593966. ISSN 21595399. ISBN 9781577358091.
 Rok: 2019
 DOI: 10.1609/aaai.v33i01.33013959
 Odkaz: https://doi.org/10.1609/aaai.v33i01.33013959
 Pracoviště: Katedra počítačů, Centrum umělé inteligence

Anotace:
We study a classification problem where each feature can be acquired for a cost and the goal is to optimize a tradeoff between the expected classification error and the feature cost.We revisit a former approach that has framed the problem as a sequential decisionmaking problem and solved it by Qlearning with a linear approximation, where individual actions are either requests for feature values or terminate the episode by providing a classification decision. On a set of eight problems, we demonstrate that by replacing the linear approximation with neural networks the approach becomes comparable to the stateoftheart algorithms developed specifically for this problem. The approach is flexible, as it can be improved with any new reinforcement learning enhancement, it allows inclusion of pretrained highperformance classifier, and unlike prior art, its performance is robust across all evaluated datasets.
Hardening networks against strategic attackers using attack graph games
 Autoři: Durkota, K., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, Ch., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Computers & Security. 2019, 87(87), ISSN 01674048.
 Rok: 2019
 DOI: 10.1016/j.cose.2019.101578
 Odkaz: https://doi.org/10.1016/j.cose.2019.101578
 Pracoviště: Centrum umělé inteligence

Anotace:
We consider the problem faced by a network administrator (defender) when deploying limited security resources to protect a network against a strategic attacker. To evaluate the effectiveness of a defense strategy, one must consider possible counterattacks that an attacker can choose. We use game theory to model the interaction between the defender and the attacker. Game theory provides relevant concepts and algorithms for computing optimal strategies in environments with multiple decision makers. To model the space of attacker's possible actions, we use attack graphs, that compactly represent all known sequences of attacker's action that may lead to successful attack for a given network. We demonstrate our approach on a specific type of defense actions, where the defender deploys deceptive hosts and services (honeypots) to detect and mitigate attacks. We assume the worstcase attacker who has a complete knowledge of the (typically randomized) defense strategy. We seek the optimal defense strategy against this attacker in the form of a Stackelberg equilibrium. Computing this solution exactly using standard techniques has limited scalability, so we investigate several approaches for increasing scalability to realistic problems. We introduce optimization methods for finding exact solutions for these games and then propose a variety of polynomial heuristic algorithms that scale to significantly larger games. We analyze the scalability and the quality of these heuristic solutions on realistic network topologies. We show that the strategies found by the heuristics are often nearoptimal and that they outperform nongametheoretic baselines. Finally, we show how attack graph games can be used to answer various research questions relevant to network security administrators.
Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Games
 Autoři: Ing. Michal Šustr, RNDr. Vojtěch Kovařík, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. New York: ACM, 2019. p. 224232. ISSN 25235699. ISBN 9781450363099.
 Rok: 2019
 Pracoviště: Katedra počítačů, Centrum umělé inteligence

Anotace:
Online game playing algorithms produce highquality strategieswith a fraction of memory and computation required by their offline alternatives. Continual Resolving (CR) is a recent theoretically sound approach to online game playing that has been usedto outperform human professionals in poker. However, parts ofthe algorithm were specific to poker, which enjoys many properties not shared by other imperfect information games. We presenta domainindependent formulation of CR applicable to any twoplayer zerosum extensiveform games (EFGs). It works with anabstract resolving algorithm, which can be instantiated by variousEFG solvers. We further describe and implement its Monte Carlovariant (MCCR) which uses Monte Carlo Counterfactual RegretMinimization (MCCFR) as a resolver. We prove the correctness ofCR and show anO(T−1/2)dependence of MCCR’s exploitabilityon the computation time. Furthermore, we present an empiricalcomparison of MCCR with incremental tree building to OnlineOutcome Sampling and Informationset MCTS on several domains.
Approximating Maxmin Strategies in Imperfect Recall Games Using Aloss Recall Property
 Autoři: Čermák, J., doc. Mgr. Branislav Bošanský, Ph.D., Horák, K., doc. Mgr. Viliam Lisý, MSc., Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: International Journal of Approximate Reasoning. 2018, 93 290326. ISSN 0888613X.
 Rok: 2018
 DOI: 10.1016/j.ijar.2017.11.010
 Odkaz: https://doi.org/10.1016/j.ijar.2017.11.010
 Pracoviště: Centrum umělé inteligence

Anotace:
Extensiveform games with imperfect recall are an important model of dynamic games where the players are allowed to forget previously known information. Often, imperfect recall games result from an abstraction algorithm that simplifies a large game with perfect recall. Solving imperfect recall games is known to be a hard problem, and thus it is useful to search for a subclass of imperfect recall games which offers sufficient memory savings while being efficiently solvable. The abstraction process can then be guided to result in a game from this class. We focus on a subclass of imperfect recall games called Aloss recall games. First, we provide a complete picture of the complexity of solving imperfect recall and Aloss recall games. We show that the Aloss recall property allows us to compute a best response in polynomial time (computing a best response is NPhard in imperfect recall games). This allows us to create a practical algorithm for approximating maxmin strategies in twoplayer games where the maximizing player has imperfect recall and the minimizing player has Aloss recall. This algorithm is capable of solving some games with up to 5⋅109 states in approximately 1 hour. Finally, we demonstrate that the use of imperfect recall abstraction can reduce the size of the strategy representation to as low as 0.03% of the size of the strategy representation in the original perfect recall game without sacrificing the quality of the maxmin strategy obtained by solving this abstraction.
Path Hopping: An MTD Strategy for LongTerm QuantumSafe Communication
 Autoři: SafaviNaini, R., Poostindouz, A., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Security and Communication Networks. 2018, 2018 ISSN 19390114.
 Rok: 2018
 DOI: 10.1155/2018/8475818
 Odkaz: https://doi.org/10.1155/2018/8475818
 Pracoviště: Centrum umělé inteligence

Anotace:
Moving target defense (MTD) strategies have been widely studied for securing computer systems. We consider using MTD strategies to provide longterm cryptographic security for message transmission against an eavesdropping adversary who has access to a quantum computer. In such a setting, today's widely used cryptographic systems including DiffieHellman key agreement protocol and RSA cryptosystem will be insecure and alternative solutions are needed. We will use a physical assumption, existence of multiple communication paths between the sender and the receiver, as the basis of security, and propose a cryptographic system that uses this assumption and an MTD strategy to guarantee efficient longterm information theoretic security even when only a single path is not eavesdropped. Following the approach of Maleki et al., we model the system using a Markov chain, derive its transition probabilities, propose two security measures, and prove results that show how to calculate these measures using transition probabilities. We define two types of attackers that we call risktaking and riskaverse and compute our proposed measures for the two types of adversaries for a concrete MTD strategy. We will use numerical analysis to study tradeoffs between system parameters, discuss our results, and propose directions for future research.
An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large ExtensiveForm Games
 Autoři: Čermák, J., doc. Mgr. Branislav Bošanský, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Proceedings of the International Joint Conference on Artificial Intelligence. Palo Alto, California: Association for the Advancement of Artificial Intelligence (AAAI), 2017. p. 936942. ISSN 10450823. ISBN 9780999241103.
 Rok: 2017
 DOI: 10.24963/ijcai.2017/130
 Odkaz: https://doi.org/10.24963/ijcai.2017/130
 Pracoviště: Centrum umělé inteligence

Anotace:
We solve large twoplayer zerosum extensiveform games with perfect recall. We propose a new algorithm based on fictitious play that significantly reduces memory requirements for storing average strategies. The key feature is exploiting imperfect recall abstractions while preserving the convergence rate and guarantees of fictitious play applied directly to the perfect recall game. The algorithm creates a coarse imperfect recall abstraction of the perfect recall game and automatically refines its information set structure only where the imperfect recall might cause problems. Experimental evaluation shows that our novel algorithm is able to solve a simplified poker game with 7.10^5 information sets using an abstracted game with only 1.8% of information sets of the original game. Additional experiments on poker and randomly generated games suggest that the relative size of the abstraction decreases as the size of the solved games increases.
DeepStack: Expertlevel artificial intelligence in headsup nolimit poker
 Autoři: Moravčík, M., Schmid, M., Burch, N., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: SCIENCE. 2017, 356(6337), 508513. ISSN 00368075.
 Rok: 2017
 DOI: 10.1126/science.aam6960
 Odkaz: https://doi.org/10.1126/science.aam6960
 Pracoviště: Centrum umělé inteligence

Anotace:
Artificial intelligence has seen several breakthroughs in recent years, with games often serving as milestones. A common feature of these games is that players have perfect information. Poker, the quintessential game of imperfect information, is a longstanding challenge problem in artificial intelligence. We introduce DeepStack, an algorithm for imperfectinformation settings. It combines recursive reasoning to handle information asymmetry, decomposition to focus computation on the relevant decision, and a form of intuition that is automatically learned from selfplay using deep learning. In a study involving 44,000 hands of poker, DeepStack defeated, with statistical significance, professional poker players in headsup nolimit Texas hold'em. The approach is theoretically sound and is shown to produce strategies that are more difficult to exploit than prior approaches. © 2017, American Association for the Advancement of Science.
Economically Optimal Variable Tag Length Message Authentication
 Autoři: SafaviNaini, R., doc. Mgr. Viliam Lisý, MSc., Ph.D., Desmedt, Y.G.
 Publikace: 21st International Conference on Financial Cryptography and Data Security. Springer, Cham, 2017. p. 204223. ISSN 03029743. ISBN 9783319709710.
 Rok: 2017
 DOI: 10.1007/9783319709727_11
 Odkaz: https://doi.org/10.1007/9783319709727_11
 Pracoviště: Centrum umělé inteligence

Anotace:
Cryptographic authentication protects messages against forgeries. In real life, messages carry information of different value and the gain of the adversary in a successful forgery and the corresponding cost of the system designers, depend on the "meaning" of the message. This is easy o see by comparing the successful forgery of a $1,000 transaction with the forgery of a $1 one. Cryptographic protocols require computation and increase communication cost of the system, and an economically optimal system must optimize these costs such that message protection be commensurate to their values. This is especially important for resource limited devices that rely on battery power. A MAC (Message Authentication Code) provides protection by appending a cryptographic tag to the message. For secure MACs, the tag length is the main determinant of the security level: longer tags provide higher protection and at the same time increase the communication cost of the system. Our goal is to find the economically optimal tag lengths when messages carry information of different values.
Eqilibrium Approximation Quality of Current NoLimit Poker Bots
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., Bowling, M.
 Publikace: AAAI Workshops. Menlo Park: AAAI Press, 2017. p. 361366. ISBN 9781577357865.
 Rok: 2017
 Pracoviště: Centrum umělé inteligence

Anotace:
Approximating a Nash equilibrium is currently the best performing approach for creating pokerplaying programs. While for the simplest variants of the game, it is possible to evaluate the quality of the approximation by computing the value of the best response strategy, this is currently not computationally feasible for larger variants of the game, such as headsup nolimit Texas hold'em. In this paper, we present a simple and computationally inexpensive Local Best Response method for computing an approximate lower bound on the value of the best response strategy. Using this method, we show that existing pokerplaying programs, based on solving abstract games, are remarkably poor Nash equilibrium approximations.
Optimal Strategies for Detecting Data Exfiltration by Internal and External Attackers
 Autoři: Durkota, K., doc. Mgr. Viliam Lisý, MSc., Ph.D., Kiekintveld, C., Horák, K., doc. Mgr. Branislav Bošanský, Ph.D., doc. Ing. Tomáš Pevný, Ph.D.,
 Publikace: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Düsseldorf: Springer VDI Verlag, 2017. p. 171192. ISSN 03029743. ISBN 9783319687100.
 Rok: 2017
 DOI: 10.1007/9783319687117_10
 Odkaz: https://doi.org/10.1007/9783319687117_10
 Pracoviště: Centrum umělé inteligence

Anotace:
We study the problem of detecting data exfiltration in computer networks. We focus on the performance of optimal defense strategies with respect to an attacker’s knowledge about typical network behavior and his ability to influence the standard traffic. Internal attackers know the typical upload behavior of the compromised host and may be able to discontinue standard uploads in favor of the exfiltration. External attackers do not immediately know the behavior of the compromised host, but they can learn it from observations.We model the problem as a sequential game of imperfect information, where the network administrator selects the thresholds for the detector, while the attacker chooses how much data to exfiltrate in each time step. We present novel algorithms for approximating the optimal defense strategies in the form of Stackelberg equilibria. We analyze the scalability of the algorithms and efficiency of the produced strategies in a case study based on realworld uploads of almost six thousand users to Google Drive. We show that with the computed defense strategies, the attacker exfiltrates 2–3 times less data than with simple heuristics; randomized defense strategies are up to 30% more effective than deterministic ones, and substantially more effective defense strategies are possible if the defense is customized for groups of hosts with similar behavior.
Path Hopping: an MTD Strategy for Quantumsafe Communication
 Autoři: SafaviNaini, R., Poostindouz, A., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Proceedings of the 2017 Workshop on Moving Target Defense. New York: ACM, 2017. p. 111114. ISBN 9781450351768.
 Rok: 2017
 DOI: 10.1145/3140549.3140560
 Odkaz: https://doi.org/10.1145/3140549.3140560
 Pracoviště: Centrum umělé inteligence

Anotace:
Moving target defense (MTD) strategies have been widely studied for securing computer communication systems. We consider using MTD strategies as a cryptographic mechanism for providing se cure communication when the adversary has access to a quantum computer and security is required over a long period of time. We assume Alice and Bob are connected by multiple disjoint paths, not all of which can be eavesdropped by the attacker at the same time. We propose a cryptographic system that uses an MTD strategy that achieves longterm quantumsafe security. We model the system as a Markov chain, and propose two security measures that correspond to two types of adversaries, called risktaking and riskaverse. Our numerical simulations shows dependencies between system parameters, and leads to new insights, such as quantifying the cost of being a riskaverse adversary.
Algorithms for computing strategies in twoplayer simultaneous move games
 Autoři: doc. Mgr. Branislav Bošanský, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D., Lanctot, M., Čermák, J., Winands, M. H. M.
 Publikace: Artificial Intelligence. 2016, 237 140. ISSN 00043702.
 Rok: 2016
 DOI: 10.1016/j.artint.2016.03.005
 Odkaz: https://doi.org/10.1016/j.artint.2016.03.005
 Pracoviště: Centrum umělé inteligence

Anotace:
Simultaneous move games model discrete, multistage interactions where at each stage players simultaneously choose their actions. At each stage, a player does not know what action the other player will take, but otherwise knows the full state of the game. This formalism has been used to express games in general game playing and can also model many discrete approximations of realworld scenarios. In this paper, we describe both novel and existing algorithms that compute strategies for the class of twoplayer zerosum simultaneous move games. The algorithms include exact backward induction methods with efficient pruning, as well as Monte Carlo sampling algorithms. We evaluate the algorithms in two different settings: the offline case, where computational resources are abundant and closely approximating the optimal strategy is a priority, and the online search case, where computational resources are limited and acting quickly is necessary. We perform a thorough experimental evaluation on six substantially different games for both settings. For the exact algorithms, the results show that our pruning techniques for backward induction dramatically improve the computation time required by the previous exact algorithms. For the sampling algorithms, the results provide unique insights into their performance and identify favorable settings and domains for different sampling algorithms. (C) 2016 Elsevier B.V. All rights reserved.
Case Studies of Network Defense with Attack Graph Games
 Autoři: Durkota, K., doc. Mgr. Viliam Lisý, MSc., Ph.D., Kiekintveld, C., doc. Mgr. Branislav Bošanský, Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: IEEE Intelligent Systems. 2016, 31(5), 2430. ISSN 15411672.
 Rok: 2016
 DOI: 10.1109/MIS.2016.74
 Odkaz: https://doi.org/10.1109/MIS.2016.74
 Pracoviště: Centrum umělé inteligence

Anotace:
The increaing 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.
Using Correlated Strategies for Computing Stackelberg Equilibria in Extensiveform Games
 Autoři: Čermák, J., doc. Mgr. Branislav Bošanský, Ph.D., Durkota, K., doc. Mgr. Viliam Lisý, MSc., Ph.D., Kiekintveld, C.
 Publikace: AAAI'16 Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2016. p. 439445. ISBN 9781577357605.
 Rok: 2016
 Pracoviště: Centrum umělé inteligence

Anotace:
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 twoplayer extensiveform generalsum games with imperfect information (EFGs) where computing SSE is an NPhard problem. Our algorithm is based on a correlated version of SSE, known as Stackelberg ExtensiveForm 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.
Approximate Solutions for Attack Graph Games with Imperfect Information
 Autoři: Durkota, K., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, K.
 Publikace: Decision and Game Theory for Security. London: Springer, 2015. p. 228249. ISSN 03029743. ISBN 9783319255934.
 Rok: 2015
 DOI: 10.1007/9783319255941_13
 Odkaz: https://doi.org/10.1007/9783319255941_13
 Pracoviště: Katedra počítačů

Anotace:
We study the problem of network security hardening, in which a network administrator decides what security measures to use to best improve the security of the network. Specifically, we focus on deploying decoy services or hosts called honeypots. We model the problem as a generalsum extensiveform game with imperfect information and seek a solution in the form of Stackelberg Equilibrium. The defender seeks the optimal randomized honeypot deployment in a specific computer network, while the attacker chooses the best response as a contingency attack policy from a library of possible attacks compactly represented by attack graphs. Computing an exact Stackelberg Equilibrium using standard mixedinteger linear programming has a limited scalability in this game. We propose a set of approximate solution methods and analyze the tradeoff between the computation time and the quality of the strategies calculated.
Combining online learning and equilibrium computation in security games
 Autoři: Klíma, R., doc. Mgr. Viliam Lisý, MSc., Ph.D., Kiekintveld, Ch.
 Publikace: Decision and Game Theory for Security. London: Springer, 2015. pp. 130149. ISSN 03029743. ISBN 9783319255934.
 Rok: 2015
 DOI: 10.1007/9783319255941_8
 Odkaz: https://doi.org/10.1007/9783319255941_8
 Pracoviště: Katedra počítačů

Anotace:
Gametheoretic analysis has emerged as an important method for making resource allocation decisions in both infrastructure protection and cyber security domains. However, static equilibrium models defined based on inputs from domain experts have weaknesses; they can be inaccurate, and they do not adapt over time as the situation (and adversary) evolves. In cases where there are frequent interactions with an attacker, using learning to adapt to an adversary revealed behavior may lead to better solutions in the long run. However, learning approaches need a lot of data, may perform poorly at the start, and may not be able to take advantage of expert analysis. We explore ways to combine equilibrium analysis with online learning methods with the goal of gaining the advantages of both approaches. We present several hybrid methods that combine these techniques in different ways, and empirically evaluated the performance of these methods in a game that models a border patrolling scenario.
GameTheoretic Algorithms for Optimal Network Security Hardening Using Attack Graphs
 Autoři: Durkota, K., doc. Mgr. Viliam Lisý, MSc., Ph.D., Kiekintveld, K., doc. Mgr. Branislav Bošanský, Ph.D.,
 Publikace: Autonomous Agents and Multiagent Systems. County of Richland: IFAAMAS, 2015. p. 17731774. 14. ISSN 15488403. ISBN 9781450337717.
 Rok: 2015
 Pracoviště: Katedra počítačů

Anotace:
In network security hardening a network administrator may need to use limited resources (such as honeypots) to harden a network against possible attacks. Attack graphs are a common formal model used to represent possible attacks. However, most existing works on attack graphs do not consider the reactions of attackers to different defender strategies. We introduce a gametheoretic model of the joint problem where attacker’s strategies are represented using attack graphs, and defender’s strategies are represented as modifications of the attack graph. The attack graphs we use allow for sequential attack actions with associated costs and probabilities of success/failure. We present an algorithm for an computing attack policy that maximizes attacker’s expected reward and empirical results demonstrating our methods on a case study network.
Gametheoretic Foundations for the Strategic Use of Honeypots in Network Security
 Autoři: Kiekintveld, C., doc. Mgr. Viliam Lisý, MSc., Ph.D., Píbil, R.
 Publikace: Advances in Information Security. 2015, 56(56), 81101. ISSN 15682633.
 Rok: 2015
 DOI: 10.1007/9783319140391_5
 Odkaz: https://doi.org/10.1007/9783319140391_5
 Pracoviště: Katedra počítačů

Anotace:
An important element in the mathematical and scientific foundations for security is modeling the strategic use of deception and information manipulation. We argue that game theory provides an important theoretical framework for reasoning about information manipulation in adversarial settings, including deception and randomization strategies. In addition, game theory has practical uses in determining optimal strategies for randomized patrolling and resource allocation. We discuss three gametheoretic models that capture aspects of how honeypots can be used in network security. Honeypots are fake hosts introduced into a network to gather information about attackers and to distract them from real targets. They are a limited resource, so there are important strategic questions about how to deploy them to the greatest effect, which is fundamentally about deceiving attackers into choosing fake targets instead of real ones to attack. We describe several game models that address strategies for deploying honeypots, including a basic honeypot selection game, an extension of this game that allows additional probing actions by the attacker, and finally a version in which attacker strategies are represented using attack graphs. We conclude with a discussion of the strengths and limitations of game theory in the context of network security.
Online Monte Carlo Counterfactual Regret Minimization for Search in Imperfect Information Games
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., Lanctot, M., Bowling, M.
 Publikace: Autonomous Agents and Multiagent Systems. County of Richland: IFAAMAS, 2015. p. 2736. 14. ISSN 15488403. ISBN 9781450337717.
 Rok: 2015
 Pracoviště: Katedra počítačů

Anotace:
Online search in games has been a core interest of artificial intelligence. Search in imperfect information games (e.g., Poker, Bridge, Skat) is particularly challenging due to the complexities introduced by hidden information. In this paper, we present Online Outcome Sampling, an online search variant of Monte Carlo Counterfactual Regret Minimization, which preserves its convergence to Nash equilibrium. We show that OOS can overcome the problem of nonlocality encountered by previous search algorithms and perform well against its worstcase opponents. We show that exploitability of the strategies played by OOS decreases as the amount of search time increases, and that preexisting Information Set Monte Carlo tree search (ISMCTS) can get more exploitable over time. In headtohead play, OOS outperforms ISMCTS in games where nonlocality plays a significant role, given a sufficient computation time per move.
Optimal Network Security Hardening Using Attack Graph Games
 Autoři: Durkota, K., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, K.
 Publikace: International Joint Conference on Artificial Intelligence. Menlo Park, California: AAAI Press, 2015. p. 526532. ISSN 10450823. ISBN 9781577357384.
 Rok: 2015
 Pracoviště: Katedra počítačů

Anotace:
Preventing attacks in a computer network is the core problem in network security. We introduce a new gametheoretic model of the interaction between a network administrator who uses limited resource to harden a network and an attacker who follows a multistage plan to attack the network. The possible plans of the attacker are compactly represented using attack graphs, while the defender adds fake targets (honeypots) to the network to deceive the attacker. The compact representation of the attacker’s strategies presents a computational challenge and finding the best response of the attacker is NPhard. We present a solution method that first translates an attack graph into an MDP and solves it using policy search with a set of pruning techniques. We present an empirical evaluation of the model and solution algorithms, evaluating scalability, the types of solutions that are generated for realistic cases, and sensitivity analysis.
ALTERNATIVE SELECTION FUNCTIONS FOR INFORMATION SET MONTE CARLO TREE SEARCH
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Acta Polytechnica. 2014, 45(5), 333340. ISSN 12102709.
 Rok: 2014
 DOI: 10.14311/AP.2014.54.0333
 Odkaz: https://doi.org/10.14311/AP.2014.54.0333
 Pracoviště: Katedra počítačů

Anotace:
We evaluate the performance of various selection methods for the Monte Carlo Tree Search algorithm in twoplayer zerosum extensiveform games with imperfect information. We compare the standard Upper Confident Bounds applied to Trees (UCT) along with the less common Exponential Weights for Exploration and Exploitation (Exp3) and novel Regret matching (RM) selection in two distinct imperfect information games: Imperfect Information Goofspiel and Phantom TicTacToe. We show that UCT after initial fast convergence towards a Nash equilibrium computes increasingly worse strategies after some point in time. This is not the case with Exp3 and RM, which also show superior performance in headtohead matches.
An Exact DoubleOracle Algorithm for ZeroSum ExtensiveForm Games with Imperfect Information
 Autoři: doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, C., doc. Mgr. Viliam Lisý, MSc., Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Journal of Artificial Intelligence Research. 2014, 51 829866. ISSN 10769757.
 Rok: 2014
 Pracoviště: Katedra počítačů

Anotace:
Developing scalable solution algorithms is one of the central problems in computational game theory. We present an iterative algorithm for computing an exact Nash equilibrium for twoplayer zerosum extensiveform games with imperfect information. Our approach combines two key elements: (1) the compact sequenceform representation of extensiveform games and (2) the algorithmic framework of doubleoracle methods. The main idea of our algorithm is to restrict the game by allowing the players to play only selected sequences of available actions. After solving the restricted game, new sequences are added by finding best responses to the current solution using fast algorithms. We experimentally evaluate our algorithm on a set of games inspired by patrolling scenarios, board, and card games. The results show significant runtime improvements in games admitting an equilibrium with small support, and substantial improvement in memory use even on games with large support. The improvement in memory use is particularly important because it allows our algorithm to solve much larger game instances than existing linear programming methods. Our main contributions include (1) a generic sequenceform doubleoracle algorithm for solving zerosum extensiveform games; (2) fast methods for maintaining a valid restricted game model when adding new sequences; (3) a search algorithm and pruning methods for computing bestresponse sequences; (4) theoretical guarantees about the convergence of the algorithm to a Nash equilibrium; (5) experimental analysis of our algorithm on several games, including an approximate version of the algorithm.
Computing Optimal Policies for Attack Graphs with Action Failures and Costs
 Autoři: Durkota, K., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Frontiers in Artificial Intelligence and Applications. Amsterdam: IOS Press, 2014. p. 101110. ISSN 09226389. ISBN 9781614994206.
 Rok: 2014
 DOI: 10.3233/9781614994213101
 Odkaz: https://doi.org/10.3233/9781614994213101
 Pracoviště: Katedra počítačů

Anotace:
An attack graph represents all known sequences of actions that compromise a system in form of an andor graph. We assume that each action in the attack graph has a specified cost and probability of success and propose an algorithm for computing an action selection policy minimizing the expected cost of performing an attack. We model the problem as a finite horizon MDP and use forward search with transposition tables and various pruning techniques based on the structure of the attack graph. We experimentally compare the proposed algorithm to a generic MDP solver and a solver transforming the problem to an Unconstrained Influence Diagram showing a substantial runtime improvement.
Monte Carlo Tree Search in Simultaneous Move Games with Applications to Goofspiel
 Autoři: Lanctot, M., doc. Mgr. Viliam Lisý, MSc., Ph.D., Winands, M.H.M.
 Publikace: Computer Games. Cham: Springer International Publishing AG, 2014. pp. 2843. Communications in Computer and Information Science. ISSN 18650929. ISBN 9783319054278.
 Rok: 2014
 DOI: 10.1007/9783319054285_3
 Odkaz: https://doi.org/10.1007/9783319054285_3
 Pracoviště: Katedra počítačů

Anotace:
Monte Carlo Tree Search (MCTS) has become a widely popular sampledbased search algorithm for twoplayer games with perfect information. When actions are chosen simultaneously, players may need to mix between their strategies. In this paper, we discuss the adaptation of MCTS to simultaneous move games. We introduce a new algorithm, Online Outcome Sampling (OOS), that approaches a Nash equilibrium strategy over time. We compare both headtohead performance and exploitability of several MCTS variants in Goofspiel. We show that regret matching and OOS perform best and that all variants produce less exploitable strategies than UCT.
Online Learning Methods for Border Patrol Resource Allocation
 Autoři: Klíma, R., Kiekintveld, Ch., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Decision and Game Theory for Security. Heidelberg: Springer, 2014. p. 340349. Lecture Notes in Computer Science. ISSN 03029743. ISBN 9783319126005.
 Rok: 2014
 DOI: 10.1007/9783319126012_20
 Odkaz: https://doi.org/10.1007/9783319126012_20
 Pracoviště: Katedra počítačů

Anotace:
We introduce a model for border security resource allocation with repeated interactions between attackers and defenders. The defender must learn the optimal resource allocation strategy based on historical apprehension data, balancing exploration and exploitation in the policy. We experiment with several solution methods for this online learning problem including UCB, slidingwindow UCB, and EXP3. We test the learning methods against several different classes of attackers including attacker with randomly varying strategies and attackers who react adversarially to the defender's strategy. We present experimental data to identify the optimal parameter settings for these algorithms and compare the algorithms against the different types of attackers.
Practical Performance of Refinements of Nash Equilibria in ExtensiveForm ZeroSum Games
 Autoři: Čermák, J., doc. Mgr. Branislav Bošanský, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Frontiers in Artificial Intelligence and Applications. Amsterdam: IOS Press, 2014. pp. 201206. ISSN 09226389. ISBN 9781614994183.
 Rok: 2014
 DOI: 10.3233/9781614994190201
 Odkaz: https://doi.org/10.3233/9781614994190201
 Pracoviště: Katedra kybernetiky, Katedra počítačů

Anotace:
Nash equilibrium (NE) is the best known solution concept used in game theory. It is known that NE is particularly weak even in zerosum extensiveform games since it can prescribe irrational actions to play that do not exploit mistakes made by an imperfect opponent. These issues are addressed by a number of refinements of NE that strengthen the requirements for equilibrium strategies. However, a thorough experimental analysis of practical performance of the Nash equilibria refinement strategies is, to the best of our knowledge, missing. This paper aims to fill this void and provides the first broader experimental comparison of the quality of refined Nash strategies in zerosum extensiveform games. The experimental results suggest that (1) there is a significant difference between the best and the worst NE strategy against imperfect opponents, (2) the existing refinements outperform the worst NE strategy, (3) they typically perform close to the best possible NE strategy, and (4) the difference in performance of all compared refinements is very small.
Randomized Operating Point Selection in Adversarial Classification
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., Kessl, R., doc. Ing. Tomáš Pevný, Ph.D.,
 Publikace: Machine Learning and Knowledge Discovery in Databases  ECML PKDD 2013, part II. Heidelberg: Springer, 2014. pp. 240255. Lecture Notes in Computer Science. ISSN 03029743. ISBN 9783662448502.
 Rok: 2014
 DOI: 10.1007/9783662448519_16
 Odkaz: https://doi.org/10.1007/9783662448519_16
 Pracoviště: Katedra počítačů

Anotace:
Security systems for email spam filtering, network intrusion detection, steganalysis, and watermarking, frequently use classifiers to separate malicious behavior from legitimate. Typically, they use a fixed operating point minimizing the expected cost / error. This allows a rational attacker to deliver invisible attacks just below the detection threshold. We model this situation as a nonzero sum normal form game capturing attacker’s expected payoffs for detected and undetected attacks, and detector’s costs for false positives and false negatives computed based on the Receiver Operating Characteristic (ROC) curve of the classifier. The analysis of Nash and Stackelberg equilibria reveals that using a randomized strategy over multiple operating points forces the rational attacker to design less efficient attacks and substantially lowers the expected cost of the detector. We present the equilibrium strategies for sample ROC curves from network intrusion detection system and evaluate the corresponding benefits.
Search in Imperfect Information Games Using Online Monte Carlo Counterfactual Regret Minimization
 Autoři: Lanctot, M., doc. Mgr. Viliam Lisý, MSc., Ph.D., Bowling, M.
 Publikace: Workshops at the TwentyEighth AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2014. pp. 3441.
 Rok: 2014
 Pracoviště: Katedra počítačů

Anotace:
Online search in games has always been a core interest of artificial intelligence. Advances made in search for perfect information games (such as Chess, Checkers, Go, and Backgammon) have led to AI capable of defeating the world's top human experts. Search in imperfect information games (such as Poker, Bridge, and Skat) is significantly more challenging due to the complexities introduced by hidden information. In this paper, we present Online Outcome Sampling (OOS), the first imperfect information search algorithm that is guaranteed to converge to an equilibrium strategy in twoplayer zerosum games. We show that OOS avoids common problems encountered by existing search algorithms and we experimentally evaluate its convergence rate and practical performance against benchmark strategies in Liar's Dice and a variant of Goofspiel. We show that unlike with Information Set Monte Carlo Tree Search (ISMCTS) the exploitability of the strategies produced by OOS decreases as the amount of search time increases. In practice, OOS performs as well as ISMCTS in headtohead play while producing strategies with lower exploitability given the same search time.
Computing Optimal Attack Strategies Using Unconstrained Influence Diagrams
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., Píbil, R.
 Publikace: Intelligence and Security Informatics. Heidelberg: Springer, 2013. pp. 3846. Lecture Notes in Computer Science. ISSN 03029743. ISBN 9783642396922.
 Rok: 2013
 DOI: 10.1007/9783642396939_5
 Odkaz: https://doi.org/10.1007/9783642396939_5
 Pracoviště: Katedra počítačů

Anotace:
Attack graphs are a formalism for capturing the most important ways to compromise a system. They are used for evaluating risks and designing appropriate countermeasures. Analysis of attack graphs sometimes requires computing the optimal attack strategy that minimizes the expected cost of the attacker in case of stochastically failing actions. We point out several results in AI literature that are highly relevant to this problem, but remain unnoticed by security literature. We note the problem has been shown to be NPhard and we present how the problem can be reduced to the problem of solving an unconstrained influence diagram (UID). We use an existing UID solver to assess the scalability of the approach, showing that it can be used to optimally solve attack graphs with up to 20 attack actions.
Convergence of Monte Carlo Tree Search in Simultaneous Move Games
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., RNDr. Vojtěch Kovařík, Ph.D., Lanctot, M., doc. Mgr. Branislav Bošanský, Ph.D.,
 Publikace: Advances in Neural Information Processing Systems 26. Red Hook: Curran Associates, Inc., 2013. pp. 21122120. ISSN 10495258. ISBN 9781632660244.
 Rok: 2013
 Pracoviště: Katedra počítačů

Anotace:
We study Monte Carlo tree search (MCTS) in zerosum extensiveform 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 epsilonHannan 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 extensiveform game. We empirically evaluate this claim using regret matching and Exp3 as the selection methods on randomly generated games and empirically selected worst case games. We confirm the formal result and show that additional MCTS variants also converge to approximate NE on the evaluated games.
DoubleOracle Algorithm for Computing an Exact Nash Equilibrium in ZeroSum ExtensiveForm Games
 Autoři: doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, C., doc. Mgr. Viliam Lisý, MSc., Ph.D., Čermák, J., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: AAMAS '13 Proceedings of the 2013 international conference on Autonomous agents and multiagent systems. County of Richland: IFAAMAS, 2013. pp. 335342. AAMAS '13. ISBN 9781450319935.
 Rok: 2013
 Pracoviště: Katedra počítačů

Anotace:
We investigate an iterative algorithm for computing an exact Nash equilibrium in twoplayer zerosum extensiveform games with imperfect information. The approach uses the sequenceform representation of extensiveform games and the doubleoracle algorithmic framework. The main idea is to restrict the game by allowing the players to play only some of the sequences of available actions, then iteratively solve this restricted game, and exploit fast bestresponse algorithms to add additional sequences to the restricted game for the next iteration. In this paper we (1) extend the sequenceform doubleoracle method to be applicable on nondeterministic extensiveform games, (2) present more efficient methods for maintaining valid restricted game and computing bestresponse sequences, and finally we (3) provide theoretical guarantees of the convergence of the algorithm to a Nash equilibrium. We experimentally evaluate our algorithm on two types of games: a search game on a graph and simplified variants of Poker. The results show significant runningtime improvements compared to the previous variant of the doubleoracle algorithm, and demonstrate the ability to find an exact solution of much larger games compared to solving full linear program for the complete game.
Using DoubleOracle Method and Serialized AlphaBeta Search for Pruning in Simultaneous Move Games
 Autoři: doc. Mgr. Branislav Bošanský, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D., Čermák, J., Vítek, R., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Proceedings of the TwentyThird International Joint Conference on Artificial Intelligence. Menlo Park, California: AAAI Press, 2013. pp. 4854. ISSN 10450823. ISBN 9781577356332.
 Rok: 2013
 Pracoviště: Katedra počítačů

Anotace:
We focus on solving twoplayer zerosum extensiveform 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 doubleoracle method, and (2) it prunes the states of the game using bounds on the subgame values obtained by the classical AlphaBeta 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 runningtime improvements and reduction in the number of evaluated nodes compared to the full search algorithm.
Anytime Algorithms for Multiagent Visibilitybased Pursuitevasion Games
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems. County of Richland: IFAAMAS, 2012. pp. 13011302. ISBN 9780981738130.
 Rok: 2012
 Pracoviště: Katedra počítačů

Anotace:
We investigate algorithms for playing multiagent visibilitybased pursuitevasion games. A team of pursuers attempts to maintain visibility contact with an evader who actively avoids tracking. We aim for applicability of the algorithms in realworld scenarios; hence, we impose hard constraints on the runtime of the algorithms and we evaluate them in a simulation model based on a realworld urban area. We compare MonteCarlo tree search (MCTS) and iterative deepening minimax algorithms running on the informationset tree of the imperfectinformation game. The experimental results demonstrate that both methods create comparable good strategies for the pursuer, while the later performs better in creating the evader's strategy.
Extending Security Games to Defenders with Constrained Mobility
 Autoři: Vaněk, O., doc. Mgr. Branislav Bošanský, Ph.D., doc. Ing. Michal Jakob, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: AAAI Spring Symposium Technical Report SS1203. Menlo Park: AAAI Press, 2012, pp. 7582. ISBN 9781577355526. Available from: http://www.aaai.org/ocs/index.php/SSS/SSS12/paper/view/4276/4649
 Rok: 2012
 Pracoviště: Katedra počítačů

Anotace:
A number of realworld security scenarios can be cast as a problem of transiting an area guarded by a mobile patroller, where the transiting agent aims to choose its route so as to minimize the probability of encountering the patrolling agent, and vice versa. We model this problem as a twoplayer zerosum game on a graph, termed the transit game. In contrast to the existing models of area transit, where one of the players is stationary, we assume both players are mobile. We also explicitly model the limited endurance of the patroller and the notion of a base to which the patroller has to repeatedly return. Noting the prohibitive size of the strategy spaces of both players, we develop single and doubleoracle based algorithms including a novel acceleration scheme, to obtain optimum route selection strategies for both players. We evaluate the developed approach on a range of transit game instances inspired by realworld security problems in the urban and naval security domains.
Game Theoretic Model of Strategic Honeypot Selection in Computer Networks
 Autoři: Píbil, R., doc. Mgr. Viliam Lisý, MSc., Ph.D., Kiekintveld, C. D., doc. Mgr. Branislav Bošanský, Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Decision and Game Theory for Security. Heidelberg: SpringerVerlag, GmbH, 2012. p. 201220. Lecture Notes in Computer Science. ISSN 03029743. ISBN 9783642342653.
 Rok: 2012
 DOI: 10.1007/9783642342660_12
 Odkaz: https://doi.org/10.1007/9783642342660_12
 Pracoviště: Katedra počítačů

Anotace:
A honeypot is a decoy computer system used in network security to waste the time and resources of attackers and to analyze their behaviors. While there has been significant research on how to design honeypot systems, less is known about how to use honeypots strategically in network defense. Based on formal deception games, we develop two gametheoretic models that provide insight into how valuable should honeypots look like to maximize the probability that a rational attacker will attack a honeypot. The first model captures a static situation and the second allows attackers to imperfectly probe some of the systems on the network to determine which ones are likely to be real systems (and not honeypots) before launching an attack. We formally analyze the properties of the optimal strategies in the games and provide linear programs for their computation. Finally, we present the optimal solutions for a set of instances of the games and evaluate their quality in comparison to several baselines.
Gametheoretic Approach to Adversarial Plan Recognition
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., Píbil, R., Stiborek, J., doc. Mgr. Branislav Bošanský, Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: ECAI 2012  20th European Conference on Artificial Intelligence. Amsterdam: IOS Press, 2012. p. 546551. ISSN 09226389. ISBN 9781614990970.
 Rok: 2012
 DOI: 10.3233/9781614990987546
 Odkaz: https://doi.org/10.3233/9781614990987546
 Pracoviště: Katedra počítačů

Anotace:
We argue that the problem of adversarial plan recognition, where the observed agent actively tries to avoid detection, should be modeled in the game theoretic framework. We define the problem as an imperfectinformation extensiveform game between the observer and the observed agent. We propose a novel algorithm that approximates the optimal solution in the game using MonteCarlo sampling. The experimental evaluation is performed on a syn thetic domain inspired by a network security problem. The proposed method produces significantly better results than several simple baselines on a practically large domain.
Iterative Algorithm for Solving Twoplayer Zerosum Extensiveform Games with Imperfect Information
 Autoři: doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, C., doc. Mgr. Viliam Lisý, MSc., Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: ECAI 2012  20th European Conference on Artificial Intelligence. Amsterdam: IOS Press, 2012. pp. 193198. ISSN 09226389. ISBN 9781614990970.
 Rok: 2012
 Pracoviště: Katedra počítačů

Anotace:
We develop and evaluate a new exact algorithm for finding Nash equilibria of twoplayer zerosum extensiveform games with imperfect information. Our approach is based on the sequenceform representation of the game, and uses an algorithmic framework of doubleoracle methods that have been used successfully in other classes of games. The algorithm uses an iterative decomposition, solving restricted games and exploiting fast bestresponse algorithms to add additional sequences to the game over time. We demonstrate our algorithm on a class of adversarial graph search games motivated by real world border patrolling scenarios. The results indicate that our framework is a promising way to scale up solutions for extensiveform games, reducing both memory and computation time requirements.
Tactical Operations of MultiRobot Teams in Urban Warfare (Demonstration)
 Autoři: Novák, P., Ing. Antonín Komenda, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., Michal Čáp, MSc., Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems. County of Richland: IFAAMAS, 2012, pp. 14731474. ISBN 9780981738130. Available from: http://dl.acm.org/citation.cfm?id=2344067
 Rok: 2012
 Pracoviště: Katedra počítačů

Anotace:
With scaling of multirobot teams deployed in military operations, there is a need to boost autonomy of individual, as well as team behaviors. We developed a featurerich simulation testbed for experimental evaluation of multiagent coordination mechanisms applicable in tactical military operations in urban warfare. In particular, we investigated and implemented four approaches including multiagent mission planning and plan repair, reactive planning for teamwork, patrolling of mobile targets, and tracking of smart targets. Besides the livesystem demonstrator, we aim to showcase a scenario engaging a human in a pursuitevasion game against the algorithms we implemented.
Agentni simulaci proti somalskym piratum
 Autoři: Vaněk, O., prof. Dr. Michal Pěchouček, MSc., doc. Ing. Michal Jakob, Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Scientific American  české vydání. 2011, 2011(2), 89. ISSN 12137723.
 Rok: 2011
 Pracoviště: Katedra kybernetiky

Anotace:
Výzkumníci z Katedry kybernetiky Fakulty elektrotechnické na ČVUT studují použitelnost metod umělé inteligence a agentních technologií při zajišťování bezpečnosti v námořní doméně. Předmětem výzkumu sponzorovaného americkým Úřadem pro námořní výzkum (ONR) je vytvoření podrobného multiagentního modelu chování pirátů v prostředí námořní dopravy a návrh algoritmů pro optimálně znáhodněné plánování bezpečného transitu Adenským zálivem.
Computing TimeDependent Policies for Patrolling Games with Mobile Targets
 Autoři: doc. Mgr. Branislav Bošanský, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Ing. Michal Jakob, Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: AAMAS 2011. County of Richland: IFAAMAS, 2011. pp. 989996. ISBN 9780982657188.
 Rok: 2011
 Pracoviště: Katedra kybernetiky

Anotace:
We study how a mobile defender should patrol an area to protect multiple valuable targets from being attacked by an attacker. In contrast to existing approaches we allow the targets to move through the area according to a priori known deterministic movement schedules. We represent the patrol area by a graph of arbitrary topology and do not put any restrictions on the movement schedules. We assume the attacker can observe the defender and has full knowledge of the strategy the defender employs. We construct a gametheoretic formulation and seek defender's optimal randomized strategy in a Stackelberg equilibrium of the game. We formulate the computation of the strategy as a mathematical program whose solution corresponds to an optimal timedependent Markov policy for the defender.
Iterative Gametheoretic Route Selection for Hostile Area Transit and Patrolling
 Autoři: Vaněk, O., doc. Ing. Michal Jakob, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: AAMAS 2011. County of Richland: IFAAMAS, 2011, pp. 12731274. ISBN 9780982657188.
 Rok: 2011
 Pracoviště: Katedra kybernetiky

Anotace:
A number of realworld security scenarios can be cast as a problem of transiting an area patrolled by a mobile adversary, where the transiting agent aims to choose its route so as to minimize the probability of encountering the patrolling agent, and vice versa. We model this problem as a two player zerosum game on a graph, termed the transit game. In contrast to the existing models of area transit, where one of the players is stationary, we assume both players are mobile. We also explicitly model the limited endurance of the patroller and the notion of a base to which the patroller has to repeatedly return. Noting the prohibitive size of the strategy spaces of both players, we employ iterative oraclebased algorithms including a newly proposed accelerated scheme, to obtain optimum route selection strategies for both players. We evaluate the developed approach on a range of transit game instances inspired by realworld security problems in the urban and naval security domains.
Towards Cooperation in Adversarial Search with Confidentiality
 Autoři: doc. Mgr. Branislav Bošanský, Ph.D., doc. Mgr. Viliam Lisý, MSc., Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Proceedings of the 5th International Conference on Industrial Applications of Holonic and Multiagent Systems for Manufacturing. Berlin: SpringerVerlag, 2011. pp. 246255. ISBN 9783642231803.
 Rok: 2011
 DOI: 10.1007/9783642231810_24
 Odkaz: https://doi.org/10.1007/9783642231810_24
 Pracoviště: Katedra kybernetiky

Anotace:
We investigate the problem of cooperation of selfinterested agents with respect to the confidentiality of their plans and without a presence of any thirdparty mediator. We base our approach on nonzerosum nplayer games in the extensive form focusing on two main goals: (1) the analysis of the maximal improvement of the utility value that an agent can gain by negotiation, and (2) the dependence of this improvement on the basic characteristics of the game  the number of agents, size of the branching factor, and correlation of the utility functions. We provide theoretical definitions together with experimental results evaluated on games abstracting realworld scenarios.
Adversarial Planning for Large Multiagent Simulations
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: AAMAS 2010: Proceedings of the Ninth International Conference on Autonomous Agents and Multi Agent Systems. Dublin: Computer Science Press, 2010, pp. 16651666. ISBN 9780982657119.
 Rok: 2010
 Pracoviště: Katedra kybernetiky

Anotace:
We investigate planning for selfinterested agents in large multiagent simulations. We present two heuristic algorithms that exploit different domainspecific properties in order to find high quality plans with reduced amount of computations. We further suggest finding a formal framework for describing these properties and complementing our previous mostly experimental results by formal guarantees.
Affective ManMachine Interface: Unveiling Human Emotions through Biosignals
 Autoři: van den Broek, E.L., doc. Mgr. Viliam Lisý, MSc., Ph.D., Westerink, J.H.D.M., Schut, M.H., Tuinenbreijer, K.
 Publikace: Biomedical Engineering Systems and Technologies International Joint Conference, BIOSTEC 2009 Porto, Portugal, January 1417, 2009, Revised Selected Papers. Heidelberg: Springer, 2010. p. 2147. Communications in Computer and Information Science. ISSN 18650929. ISBN 9783642117206.
 Rok: 2010
 DOI: 10.1007/9783642117213_2
 Odkaz: https://doi.org/10.1007/9783642117213_2
 Pracoviště: Katedra kybernetiky

Anotace:
Humans exhibit an electrical profile altered through various psychological and physiological processes, which can be measured through biosignals; e.g., electromyography (EMG) and electrodermal activity (EDA). These biosignals reveal our emotions and can serve as an advanced manmachine interface (MMI) for empathic consumer products. This chapter starts with an introduction on biosignals for emotion detection. Next, a stateoftheart review is presented on automatic emotion classification. Moreover, guidelines are presented for affective MMI. Subsequently, a research is presented that explores the use of EDA and three facial EMG signals to determine neutral, positive, negative, and mixed emotions, using recordings of 21 people. A range of techniques is tested, which resulted in a generic framework for automated emotion classification with up to 61.31% correct classification of the four emotion classes.
Agent Subset Adversarial Search for Complex Noncooperative Domains
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., Vaculín, R., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Proceedings of the IEEE Conference on Computational Intelligence and Games 2010. New Jersey: IEEE, 2010, pp. 211218. ISBN 9781424462971. Available from: http://www.vaculin.com/downloads/LisyBosanskyVaculinPechoucek2010CIG.pdf
 Rok: 2010
 DOI: 10.1109/ITW.2010.5593351
 Odkaz: https://doi.org/10.1109/ITW.2010.5593351
 Pracoviště: Katedra kybernetiky

Anotace:
We investigate reduction of the complexity of a multiagent adversarial search in the domain of nplayer games. We describe a method that decomposes the game into a set of smaller overlapping subgames, solves each subgame 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.
Deception in Networks of Mobile Sensing Agents
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., Zivan, R., Sycara, K., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: AAMAS 2010: Proceedings of the Ninth International Conference on Autonomous Agents and Multi Agent Systems. Dublin: Computer Science Press, 2010, pp. 10311038. ISBN 9780982657119.
 Rok: 2010
 Pracoviště: Katedra kybernetiky

Anotace:
In this study we consider deception by an adversary, which is relevant in many (military) applications. The adversary is expected to use deception to prevent the sensor team from performing its tasks. We employ a game theoretic model to analyze the expected strategy of the adversary and find the best response. We represent a Mobile Sensor Team problem using the Distributed Constraint Optimization Problem (DCOP) framework. We propose an optimal method for the selection of a position of a single agent facing a deceptive adversary. This method serves as a heuristic for agents to select their position in a full scale problem with multiple agents in a large area. Our empirical study demonstrates the success of our model as compared with existing models in the presence of deceptions.
GoalBased Game Tree Search for Complex Domains
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., doc. Ing. Michal Jakob, Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Agents and Artificial Intelligence International Conference, ICAART 2009, Porto, Portugal, January 1921, 2009. Revised Selected Papers. Heidelberg: Springer, 2010, pp. 97109. Communications in Computer and Information Science. ISSN 18650929. ISBN 9783642118180.
 Rok: 2010
 DOI: 10.1007/9783642118197_8
 Odkaz: https://doi.org/10.1007/9783642118197_8
 Pracoviště: Katedra kybernetiky

Anotace:
We present a novel approach to reducing adversarial search space by employing background knowledge represented in the form of higherlevel goals that players tend to pursue in the game. The algorithm is derived from a simultaneousmove modification of the max n algorithm by limiting the search to those branches of the game tree that are consistent with pursuing player's goals. The algorithm has been tested on a realworldbased scenario modelled as a largescale asymmetric game. The experimental results obtained indicate the ability of the goalbased heuristic to reduce the search space to a manageable level even in complex domains while maintaining the high quality of resulting strategies.
Planning and DecisionMaking in Complex Dynamic Adversarial Domains
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D.,
 Publikace: Workshop 2010. Praha: České vysoké učení technické v Praze, 2010, pp. 9495. CTU Reports. ISBN 9788001045138.
 Rok: 2010
 Pracoviště: Katedra kybernetiky

Anotace:
We briefly introduce the main research topics in multiagent planning and identify their weaknesses in adversarial settings. The main problem is that the conflicting goals and lack of trust and coordination among the agents causes huge computational complexity of the problem. We introduce two methods to deal with the complexity. The first is incorporating procedural background knowledge to adversarial search and the second is decomposition of the full problem to a set of smaller problems, solving them separately and the aggregating the results to global solution. Other important issues in adversarial planning are partial information about the state of the world, its sharing among the players and its intentional manipulation by opponents ? deception. We summarize our achievements in dealing with these issues and refer to other sources describing our research.
Adversarial Search with Procedural Knowledge Heuristic
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., doc. Ing. Michal Jakob, Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems. New York: ACM Press, 2009. p. 899906. ISBN 9780981738178.
 Rok: 2009
 Pracoviště: Katedra kybernetiky

Anotace:
We introduce an adversarial planning algorithm based on game tree search, which is applicable in largescale multiplayer domains. In order to tackle the scalability issues of game tree search, the algorithm utilizes procedural knowledge capturing how individual players tend to achieve their goals in the domain; the information is used to limit the search only to the part of the game tree that is consistent with pursuing players' goals. We impose no specific requirements on the format of the procedural knowledge; any programming language or agent specification paradigm can be employed. We evaluate the algorithm both theoretically and empirically, confirming that the proposed approach can lead to a substantial search reduction with only a minor negative impact on the quality of produced solutions.
Biosignals as an Advanced ManMachine Interface
 Autoři: van den Broek, E., doc. Mgr. Viliam Lisý, MSc., Ph.D., Westerink, J.H.D., Schut, M.H., Tuinenbreijer, K.
 Publikace: Proceedings of the International Conference on BioInspired Systems and Signal Processing. Setúbal: Institute for Systems and Technologies of Information, Control and Communication, 2009, pp. IS15IS24. ISBN 9789898111647.
 Rok: 2009
 Pracoviště: Katedra kybernetiky

Anotace:
As is known for centuries, humans exhibit an electrical profile. This profile is altered through various physiological processes, which can be measured through biosignals; e.g., electromyography (EMG) and electrodermal activity (EDA). These biosignals can reveal our emotions and, as such, can serve as an advanced manmachine interface (MMI) for empathic consumer products. However, such an MMI requires the correct classification of biosignals to emotion classes. This paper explores the use of EDA and three facial EMG signals to determine neutral, positive, negative, and mixed emotions, using recordings of 24 people. A range of techniques is tested, which resulted in a generic framework for automated emotion classification with up to 61.31% correct classification of the four emotion classes, without the need of personal profiles.
GoalBased Adversarial Search  Searching Game Trees in Complex Domains using Goalbased Heuristic
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., doc. Ing. Michal Jakob, Ph.D., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: First International Conference on Agents and Artificial Intelligence, Proceedings. Setúbal: Institute for Systems and Technologies of Information, Control and Communication, 2009. pp. 5360. ISBN 9789898111661.
 Rok: 2009
 Pracoviště: Katedra kybernetiky

Anotace:
We present a novel approach to reducing adversarial search space by using background knowledge represented in the form of higherlevel goals that players tend to pursue in the game. The algorithm is derived from a simultaneousmove modification of the maxn algorithm by only searching the branches of the game tree that are consistent with pursuing player's goals. The algorithm has been tested on a realworldbased scenario modelled as a largescale asymmetric game. The experimental results obtained indicate the ability of the goalbased heuristic to reduce the search space to a manageable level even in complex domains while maintaining the high quality of resulting strategies.
Towards Cooperative Predictive Data Mining in Competitive Environments.
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Ing. Michal Jakob, Ph.D., Ing. Petr Benda, Urban, Š., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Agents and Data Mining Interaction. Heidelberg: Springer, 2009. pp. 95108. ISSN 03029743. ISBN 9783642036026.
 Rok: 2009
 Pracoviště: Katedra kybernetiky

Anotace:
We study the problem of predictive data mining in a competitive multiagent setting, in which each agent is assumed to have some partial knowledge required for correctly classifying a set of unlabelled examples. The agents are selfinterested and therefore need to reason about the tradeoffs between increasing their classification accuracy by collaborating with other agents and disclosing their private classification knowledge to other agents through such collaboration. We analyze the problem and propose a set of components which can enable cooperation in this otherwise competitive task. These components include measures for quantifying private knowledge disclosure, datamining models suitable for multiagent predictive data mining, and a set of strategies by which agents can improve their classification accuracy through collaboration. The overall framework and its individual components are validated on a synthetic experimental domain.
Utilitybased Model for Classifying Adversarial Behaviour in MultiAgent Systems
 Autoři: doc. Mgr. Viliam Lisý, MSc., Ph.D., doc. Ing. Michal Jakob, Ph.D., Tožička, J., prof. Dr. Michal Pěchouček, MSc.,
 Publikace: Proceedings of the II International Multiconference on Computer Science and Information Technology. Piscataway: IEEE, 2008. pp. 4753. ISSN 18967094. ISBN 9788360810149.
 Rok: 2008
 DOI: 10.1109/IMCSIT.2008.4747216
 Odkaz: https://doi.org/10.1109/IMCSIT.2008.4747216
 Pracoviště: Katedra kybernetiky

Anotace:
Interactions and social relationships among agents are an important aspect of multiagent systems. In this paper, we explore how such relationships and their relation to agent's objectives influence agent's decisionmaking. Building on the framework of stochastic games, we propose a classification scheme, based on a formally defined concept of interaction stance, for categorizing agent's behaviour as selfinterested, altruistic, competitive, cooperative, or adversarial with respect to other agents in the system. We show how the scheme can be employed in defining behavioural norms, capturing social aspects of agent's behaviour and/or in representing social configurations of multiagent systems.