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.
We introduce the external choice into process algebra ACP in a game theory flavor. As a result of axiomatization, GameACP has not only an equational logic, but also a bisimulation semantics. The conclusions of GameACP are without any assumption or restriction, such as epistemic restrictions on strategies in @cite_20 . Though the discussions of GameACP are aimed at two person games, GameACP can be naturally used in multi-person games. GameACP provides a new viewpoint to model interactions between one autonomous agent and other autonomous agents, and can be used to reason about the behaviors of parallel and distributed systems with game theory supported.
@cite_20
2337798556 2013667259 19984411 1807884544
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. 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. A comprehensive examination of the interfaces of logic, computer science, and game theory, drawing on twenty years of research on logic and games.This book draws on ideas from philosophical logic, computational logic, multi-agent systems, and game theory to offer a comprehensive account of logic and games viewed in two complementary ways. It examines the logic of games: the development of sophisticated modern dynamic logics that model information flow, communication, and interactive structures in games. It also examines logic as games: the idea that logical activities of reasoning and many related tasks can be viewed in the form of games.In doing so, the book takes up the ?intelligent interaction? of agents engaging in competitive or cooperative activities and examines the patterns of strategic behavior that arise. It develops modern logical systems that can analyze information-driven changes in players' knowledge and beliefs, and introduces the ?Theory of Play? that emerges from the combination of logic and game theory. This results in a new view of logic itself as an interactive rational activity based on reasoning, perception, and communication that has particular relevance for games.Logic in Games, based on a course taught by the author at Stanford University, the University of Amsterdam, and elsewhere, can be used in advanced seminars and as a resource for researchers. Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, we provide a single reduction that 1) demonstrates NP-hardness of determining whether Nash equilibria with certain natural properties exist, and 2) demonstrates the NP-hardness of counting Nash equilibria (or connected sets of Nash equilibria). We also show that 3) determining whether a purestrategy Bayes-Nash equilibrium exists is NP-hard, and that 4) determining whether a pure-strategy Nash equilibrium exists in a stochastic (Markov) game is PSP ACE-hard even if the game is invisible (this remains NP-hard if the game is finite). All of our hardness results hold even if there are only two players and the game is symmetric.