As a contribution to the challenge of building game-playing AI systems, we develop and analyse a formal language for representing and reasoning about strategies. Our logical language builds on the existing general Game Description Language (GDL) and extends it by a standard modality for linear time along with two dual connectives to express preferences when combining strategies. The semantics of the language is provided by a standard state-transition model. As such, problems that require reasoning about games can be solved by the standard methods for reasoning about actions and change. We also endow the language with a specific semantics by which strategy formulas are understood as move recommendations for a player. To illustrate how our formalism supports automated reasoning about strategies, we demonstrate two example methods of implementation : first, we formalise the semantic interpretation of our language in conjunction with game rules and strategy rules in the Situation Calculus; second, we show how the reasoning problem can be solved with Answer Set Programming.
Another approach to strategy representation and reasoning is to treat a strategy as a program so that PDL-style program connectives can be used to combine strategies @cite_13 @cite_2 @cite_8 . van Benthem proposed a logical framework, named Temporal Forcing Logic (TFL), with a modality @math , meaning that player @math applies strategy @math , against any play of the others, to force the game to a state in which @math holds'', where a strategy can be defined as any PDL program. Similar proposal can also be found in @cite_2 . Such an intuitive analogue to strategies'' provides a close approximation to strategy representation; nevertheless, a strategy has essential differences from a program, which requires specific ways of composition and reasoning as we have shown in the previous sections.
@cite_8 @cite_13 @cite_2
197077171 2083346314 2094685149 2170245723
We consider a prepositional dynamic logic whose programs are regular expressions over game - strategy pairs. At the atomic level, these are finite extensive form game trees with structured strategy specifications, whereby a player's strategy may depend on properties of the opponent's strategy. The advantage of imposing structure not merely on games or on strategies but on game - strategy pairs, is that we can speak of a composite game g followed by g′ whereby if the opponent played a strategy s in g, the player responds with s′ in g′ to ensure a certain outcome. In the presence of iteration, a player has significant ability to strategise taking into account the explicit structure of games. We present a complete axiomatization of the logic and prove its decidability. The tools used combine techniques from PDL, CTL and game logics. Reasoning about capabilities, strategies and knowledge is important in the analysis of multiagent systems. Alternating-time Temporal Epistemic Logic (ATEL) was designed with this aim. Nevertheless, the original interpretation of the language suffered from some counterintuitive properties. These are due to the fact that the strategies the agent applies in worlds that he cannot distinguish may not be uniform, in the sense that the same action is applied in all indistinguishable worlds. Several refinements of the original ATEL semantics were proposed since then. In this paper we argue that the STIT framework can easily account for uniform strategies. STIT is a logic of agency that has been proposed in the 90ies in the domain of philosophy of action. It is the logic of constructions of the form "agent a sees to it that φ". To support our claim, we first present a straightforward solution in STIT logic augmented by a modal operator of knowledge. Then we offer a simplification, by introducing a modal logic of knowledge-based uniform agency, for one-step strategies, alias choices. We present a game semantics for Linear Logic, in which formulas denote games and proofs denote winning strategies. We show that our semantics yields a categorical model of Linear Logic and prove full completeness for Multiplicative Linear Logic with the MIX rule: every winning strategy is the denotation of a unique cut-free proof net. A key role is played by the notion of history-free strategy: strong connections are made between history-free strategies and the Geometry of Interaction. Our semantics incorporates a natural notion of polarity, leading to a refined treatment of the additives. We make comparisons with related work by Joyal, Blass, et al In this paper, we describe a method to represent and discover adversarial group behavior in a continuous domain. In comparison to other types of behavior, adversarial behavior is heavily structured as the location of a player (or agent) is dependent both on their teammates and adversaries, in addition to the tactics or strategies of the team. We present a method which can exploit this relationship through the use of a spatiotemporal basis model. As players constantly change roles during a match, we show that employing a "role-based" representation instead of one based on player "identity" can best exploit the playing structure. As vision-based systems currently do not provide perfect detection tracking (e.g. missed or false detections), we show that our compact representation can effectively "denoise" erroneous detections as well as enabling temporal analysis, which was previously prohibitive due to the dimensionality of the signal. To evaluate our approach, we used a fully instrumented field-hockey pitch with 8 fixed high-definition (HD) cameras and evaluated our approach on approximately 200,000 frames of data from a state-of-the-art real-time player detector and compare it to manually labelled data.