Using formal tools in computer science to describe games is an interesting problem. We give games, exactly two person games, an axiomatical foundation based on the process algebra ACP (Algebra of Communicating Process). A fresh operator called opponent's alternative composition operator (OA) is introduced into ACP to describe game trees and game strategies, called GameACP. And its sound and complete axiomatical system is naturally established. To model the outcomes of games (the co-action of the player and the opponent), correspondingly in GameACP, the execution of GameACP processes, another operator called playing operator (PO) is extended into GameACP. We also establish a sound and complete axiomatical system for PO. Finally, we give the correctness theorem between the outcomes of games and the deductions of GameACP processes.
Game-CTR @cite_0 introduces games into CTR (Concurrent Transaction Logic) to model and reason about runtime properties of workflows that are composed of non-cooperative services -- such as Web Services. Game-CTR includes a model and proof theory which can be used to specify executions under some temporal and causality constraints, and also a game solver algorithm to convert such constraints into other equivalent Game-CTR formulas to be executed more efficiently. @cite_20 develop a game semantics for a certain kind of process calculus with two interacting agents. Games and strategies on this process calculus are defined, and strategies of the two agents determine the execution of the process. And also, a certain class of strategies correspond to the so-called syntactic schedulers of Chatzikokolakis and Palamidessi. In these works, the games used are not dialogue games, and there are no interactions such as questions and answers and also no wining concept.
@cite_0 @cite_20
2886584225 2013667259 1995251574 2337798556
We present automatic verification techniques for concurrent stochastic multi-player games (CSGs) with rewards. To express properties of such models, we adapt the temporal logic rPATL (probabilistic alternating-time temporal logic with rewards), originally introduced for the simpler model of turn-based games, which enables quantitative reasoning about the ability of coalitions of players to achieve goals related to the probability of an event or reward measures. We propose and implement a modelling approach and model checking algorithms for property verification and strategy synthesis of CSGs, as an extension of PRISM-games. We evaluate the performance, scalability and applicability of our techniques on case studies from domains such as security, networks and finance, showing that we can analyse systems with probabilistic, cooperative and competitive behaviour between concurrent components, including many scenarios that cannot be analysed with turn-based models. We develop a game semantics for process algebra with two interacting agents. The purpose of our semantics is to make manifest the role of knowledge and information flow in the interactions between agents and to control the information available to interacting agents. We define games and strategies on process algebras, so that two agents interacting according to their strategies determine the execution of the process, replacing the traditional scheduler. We show that different restrictions on strategies represent different amounts of information being available to a scheduler. We also show that a certain class of strategies corresponds to the syntactic schedulers of Chatzikokolakis and Palamidessi, which were developed to overcome problems with traditional schedulers modelling interaction. The restrictions on these strategies have an explicit epistemic flavour. In game semantics, the higher-order value passing mechanisms of the λ-calculus are decomposed as sequences of atomic actions exchanged by a Player and its Opponent. Seen from this angle, game semantics is reminiscent of trace semantics in concurrency theory, where a process is identified to the sequences of requests it generates in the course of time. Asynchronous game semantics is an attempt to bridge the gap between the two subjects, and to see mainstream game semantics as a refined and interactive form of trace semantics. Asynchronous games are positional games played on Mazurkiewicz traces, which reformulate (and generalize) the familiar notion of arena game. The interleaving semantics of λ-terms, expressed as innocent strategies, may be analysed in this framework, in the perspective of true concurrency. The analysis reveals that innocent strategies are positional strategies regulated by forward and backward confluence properties. This captures, we believe, the essence of innocence. We conclude the article by defining a non-uniform variant of the λ-calculus, in which the game semantics of a λ-term is formulated directly as a trace semantics, performing the syntactic exploration or parsing of that λ-term. We propose a hybrid model for automatically acquiring a policy for a complex game, which combines online learning with mining knowledge from a corpus of human game play. Our hypothesis is that a player that learns its policies by combining (online) exploration with biases towards human behaviour that's attested in a corpus of humans playing the game will outperform any agent that uses only one of the knowledge sources. During game play, the agent extracts similar moves made by players in the corpus in similar situations, and approximates their utility alongside other possible options by performing simulations from its current state. We implement and assess our model in an agent playing the complex win-lose board game Settlers of Catan, which lacks an implementation that would challenge a human expert. The results from the preliminary set of experiments illustrate the potential of such a joint model.