Search

In this study, we investigated whether the use of smartphone games while reading a text reduces learning performance or reading speed. We also examined whether this is affected by push notifications. Ninety-three students were randomly assigned to three learning conditions. In the gaming group (G), participants played a game app for 20 s at 2-min intervals while reading. In one subgroup, the game app sent push notifications (GN+); in the other subgroup, no notifications (GN−) were sent. In the control group (C), participants did not play a game. After the reading, participants took a multiple-choice quiz. We compared quiz scores and reading times of the groups (G) and (C) and within the gaming group (GN+, GN−) and observed no differences. Since the statistical non-significance of these tests does not entail the absence of an effect, we conducted equivalence tests, which did not demonstrate equivalence either. The experiment ensured high internal validity, yet remained inconclusive. Reasons for the similarity of performance in all groups could be non-specific exercise effects (all participants owned a smartphone), low similarity between the tasks, low variance of participants’ ability and motivation (high achieving, low ADHD scores) or low game complexity. Future research should address these questions.

In this chapter, we introduce a cyber deception defense approach and propose a scalable allocation algorithm to place honeypots over an attack graph. We formulate a two‐person zero‐sum strategic game between the network defender and an attacker. The developed game model captures the network topology and its characteristics. The game also counts for the cost associated with the defense action and the attack cost. Nash equilibrium defense strategies are analytically characterized and studied for a special game. The complexity of the general game is discussed and a scalable algorithm is proposed to overcome the game complexity. This chapter extends the model to a dynamic game formulation to better understand game evolution with players' actions. Finally, numerical results are presented to illustrate the effectiveness of the proposed cyber deception approach.

Trajectory Following Control (TFC) and lateral stability control are always significant for Autonomous Ground Vehicles (AGVs). However, sometimes it is quite a challenge to achieve excellent tracking performance with less stability loss. In this paper, a novel two-agent non-cooperative game framework is built to explore the coordination approach of the integrated TFC and Direct Yaw Control (DYC) issue. Then the game theory-based control strategies are proposed and two information patterns are investigated. In the open-loop case, the Nash equilibrium of each control cycle is determined by solving discrete-time Riccati equations. When it comes to the closed-loop pattern, the game complexity increases because each player can revise his own game strategy according to the other players’ strategy evolution, and thus the dynamic programming method based on the Bellman's principle is applied to derive the control strategies. Besides, a Linear Parameter-Varying (LPV) method is adopted to facilitate the process of discretizing the state-space model in every control cycle. Finally, simulation tests based on Carsim-Simulink joint platform and experimental tests are carried out to verify the effectiveness of the proposed approach.

For nearly three decades, spatial games have produced a wealth of insights to the study of behavior and its relation to population structure. However, as different rules and factors are added or altered, the dynamics of spatial models often become increasingly complicated to interpret. To tackle this problem, we introduce persistent homology as a rigorous framework that can be used to both define and compute higher-order features of data in a manner which is invariant to parameter choices, robust to noise, and independent of human observation. Our work demonstrates its relevance for spatial games by showing how topological features of simulation data that persist over different spatial scales reflect the stability of strategies in 2D lattice games. To do so, we analyze the persistent homology of scenarios from two games: a Prisoner's Dilemma and a SIRS epidemic model. The experimental results show how the method accurately detects features that correspond to real aspects of the game dynamics. Unlike other tools that study dynamics of spatial systems, persistent homology can tell us something meaningful about population structure while remaining neutral about the underlying structure itself. Regardless of game complexity, since strategies either succeed or fail to conform to shapes of a certain topology there is much potential for the method to provide novel insights for a wide variety of spatially extended systems in biology, social science, and physics., 13 pages, 11 figures

The AlphaZero algorithm has been shown to achieve superhuman levels of plays in chess, shogi, and Go. This paper presents analytic investigations of the algorithm on NoGo, a variant of Go that players cannot capture the opponents’ stones. More specifically, lookup tables are employed for learning instead of deep neural networks, referred to as tabular AlphaZero. One goal of this work is to investigate how the algorithm is influenced by hyper-parameters. Another goal is to investigate whether the optimal plays and theoretical values can be learned. One of the hyper-parameters is thoroughly analyzed in the experiments. The results show that the tabular AlphaZero can learn the theoretical values and optimal plays in many settings of the hyper-parameter. Also, NoGo on different board sizes is compared, and the learning difficulty is shown to relate to the game complexity., The 2020 Conference on Technologies and Applications of Artificial Intelligence (TAAI 2020), December 2020

In the area of dementia care, Serious Games are seen as an opportunity to boost cognitive capabilities and to stabilize the ability to independently perform Activities of Daily Living (ADLs). We developed a Serious Game based on the popular boardgame chess to target the elderly and dementia patients through incorporating dementia relevant requirements. We analyzed multiple chess variants, which use a smaller board size with less pieces to reduce the game complexity. This results in a new chess version, that helps players to understand the core mechanics of the game and allows them to get into the flow of playing with chess figures. Included are different training scenarios as well as a virtual opponent, that adjusts towards the cognitive skill level of a dementia patient. The game’s visual appearance can be tailored to any person and preference by e.g. adjusting the board color theme to address color blindness or changing between 2D and 3D modes. Another core aspect of our game concept focuses on custom 3D printed chess pieces. They are made from conductive material and have a unique finish with additional accessories to distinguish individual pieces from each other. This results in a natural, tangible playing experience on a touchscreen device, a so-called Tangible User Interface. Besides connecting to the feeling of playing real chess, such an approach has the potential to reduce the fear towards modern devices, a well-known entry barrier for this target group. In a retirement home a small pilot study with dementia patients is performed. Furthermore, by utilizing a user-centered approach, we can identify additional insights into the concept of a supported boardgame with tangible game figures which can overcome fear towards modern technology.

Phantom Go is a derivative of Go with imperfect information. It is challenging in AI field due to its great uncertainty of the hidden information and high game complexity inherited from Go. To deal with this imperfect information game with large game tree complexity, a general search framework named belief-state Monte Carlo tree search (BS-MCTS) is put forward in this paper. BS-MCTS incorporates belief-states into Monte Carlo Tree Search, where belief-state is a notation derived from philosophy to represent the probability that speculation is in accordance with reality. In BS-MCTS, a belief-state tree, in which each node is a belief-state, is constructed and search proceeds in accordance with beliefs. Then, Opponent Guessing and Opponent Predicting are proposed to illuminate the learning mechanism of beliefs with heuristic information. The beliefs are learned by heuristic information during search by specific methods, and we propose Opponent Guessing and Opponent Predicting to illuminate the learning mechanism. Besides, some possible improvements of the framework are investigated, such as incremental updating and all moves as first (AMAF) heuristic. Technical details are demonstrated about applying BS-MCTS to Phantom Go, especially on inference strategy. We examine the playing strength of the BS-MCTS and AMAF-BS-MCTS in Phantom Go by varying search parameters, also testify the proposed improvements.

Since the community structure is able to reveal the potential law behind complex networks, mining hiding communities has gained particular attention from various applications. A variety of objective functions, such as Modularity, weighted clustering coefficient (WCC), etc., have been developed to characterize the cohesiveness of a community, and thus many community detection approaches are proposed by optimizing a predefined objective function. This paper offers a urgent study on how to integrate different objective functions into a generic framework, which aims to enhance the flexibility of expert systems that are designed to identify communities from complex networks. Specifically, we formulate the process of community detection as a strategic game and give a general form of utility function for each agent from the perspective of game theory. Furthermore, we prove that if the parameters in the generalized utility function can be specified carefully, the strategic game could well match a potential game and be able to converge to a pure Nash equilibrium. In addition, we choose some commonly used objective functions to match the generalized utility function and design a synchronous learning model to test the performance of different global models. Compared with existing approaches, experimental results on synthetic and real-world data sets demonstrate that the proposed model achieve higher accuracy and efficiency.

Game semantics was initially defined and used to characterize pcf functionals. We use this approach to propose a definition of complexity for such higher-order functions, as well as a class of polynomial time computable higher-order functions. We define a notion of size and complexity for strategies in sequential games.This defines a notion of complexity for PCF functions.The corresponding higher-order polynomial time complexity class contains BFF.

In this work, we study Static and Dynamic Games on Large Networks of interacting agents, assuming that the players have some statistical description of the interaction graph, as well as some local information. Inspired by Statistical Physics, we consider statistical ensembles of games and define a Probabilistic Approximate equilibrium notion for such ensembles. A Necessary Information Complexity notion is introduced to quantify the minimum amount of information needed for the existence of a Probabilistic Approximate equilibrium. We then focus on some special classes of games for which it is possible to derive upper and/or lower bounds for the complexity. At first, static and dynamic games on random graphs are studied and their complexity is determined as a function of the graph connectivity. In the low complexity case, we compute Probabilistic Approximate equilibrium strategies. We then consider static games on lattices and derive upper and lower bounds for the complexity, using contraction mapping ideas. A LQ game on a large ring is also studied numerically. Using a reduction technique, approximate equilibrium strategies are computed and it turns out that the complexity is relatively low.

This paper presents a model-based approach for computing real-time optimal decision strategies in the pursuit-evasion game of Ms. Pac-Man. The game of Ms. Pac-Man is an excellent benchmark problem of pursuit-evasion game with multiple, active adversaries that adapt their pursuit policies based on Ms. Pac-Man's state and decisions. In addition to evading the adversaries, the agent must pursue multiple fixed and moving targets in an obstacle-populated environment. This paper presents a novel approach by which a decision-tree representation of all possible strategies is derived from the maze geometry and the dynamic equations of the adversaries or ghosts. The proposed models of ghost dynamics and decisions are validated through extensive numerical simulations. During the game, the decision tree is updated and used to determine optimal strategies in real time based on state estimates and game predictions obtained iteratively over time. The results show that the artificial player obtained by this approach is able to achieve high game scores, and to handle high game levels in which the characters speeds and maze complexity become challenging even for human players.

In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among c colors and a number between 1 and n . The aim is to make, for each color, a pile of cards of that color with all increasing numbers from 1 to n . At each time during the game, each player holds h cards in hand. Cards are drawn sequentially from a deck and the players should decide whether to play, discard or store them for future use. One of the features of the game is that the players can see their partners' cards but not their own and information must be shared through hints. We introduce a single-player, perfect-information model and show that the game is intractable even for this simplified version where we forego both the hidden information and the multiplayer aspect of the game, even when the player can only hold two cards in her hand. On the positive side, we show that the decision version of the problem—to decide whether or not numbers from 1 through n can be played for every color—can be solved in (almost) linear time for some restricted cases.

Restricted (s, t)-Wythoff’s game, introduced by Liu et al. in 2014, is an impartial combinatorial game. We define and solve a class of games obtained from Restricted (s, t)-Wythoff’s game by adjoining to it some subsets of its P-positions as additional moves. The results show that under certain conditions they are equivalent to one case in which only one P-position is adjoined as an additional move. Furthermore, two winning strategies of exponential and polynomial are provided for the games.

We consider the methodology for proving lower bounds on the query complexity of property testing via communication complexity, which was put forward by Blais, Brody, and Matulef (Computational Complexity, 2012). They provided a restricted formulation of their methodology (via “simple combining operators”) and also hinted towards a more general formulation, which we spell out in this paper.

Cyber deception techniques are crucial to protect networks in battlefield settings and combat malicious cyber attacks. Cyber deception can effectively disrupt the surveillance process outcome of an adversary. In this paper, we propose a novel approach for cyber deception to protect important nodes and trap the adversary. We present a sequential approach of honeypot placement to defend and protect the network vital nodes. We formulate a stochastic game to study the dynamic interactions between the network administrator and the attacker. The defender makes strategic decisions about where to place honeypots to introduce new vulnerabilities to the network. The attacker's goal is to develop an attack strategy to compromise the nodes of the network by exploiting a set of known vulnerabilities. To consider a practical threat model, we assume that the attacker can only observe a noisy version of the network state. To this end, both players solve a partially observable stochastic game (POSG). Finally, we present a discussion on existing techniques to solve the formulated game and possible approaches to reduce the game complexity as part of our ongoing and future research.

Inclusive education deals with the participation of vulnerable and marginalised - especially disabled - people in learning and with reducing exclusive aspects within and from education. Communication skills under an inclusive perspective are to be understood as more than spoken or written word. Levels of languages used and alternative modes of communication are to be explored and harnessed. However, game complexity and technical constraints hamper the seamless integration in real world environments, especially when addressing groups aside from the mainstream. Building on four design challenges, we aim to develop an independently usable, user-friendly and user-oriented, technically low-threshold game called Cologon that fosters communication skills and takes into account the players diverse (dis)abilities, needs, and preferences - in simple terms: an inclusive game. In this paper we present our iterative participatory design process and the conceptual prototype. The results of an evaluation of this prototype in a participatory game design workshop point to unique insights: participants prioritised visual and audible cues above any use of language and one-device-per-player combined with the choice of roles was a challenge for all participants and created a creative communication experience.

Combinatorial game theory has many ways of measuring game complexity. In this paper, several measures of complexity for the card game Daihinmin are presented to obtain some of its characteristics. Furthermore, we show the difference in playing styles of Daihinmin between humans and computers.

This paper proposes a methodology based on system connections to calculate its complexity. Two study cases are proposed: the dining Chinese philosophers’ problem and the distribution center. Both studies are modeled using the theory of Discrete Event Systems and simulations in different contexts were performed in order to measure their complexities. The obtained results present i) the static complexity as a limiting factor for the dynamic complexity, ii) the lowest cost in terms of complexity for each unit of measure of the system performance and iii) the output sensitivity to the input parameters. The associated complexity and performance measures aggregate knowledge about the system.

The nonzero sum $n$-person game has been considered. It is well known that the game can be reduced to a global optimization problem [5; 7; 14]. By extending Mills’ result [5], we derive global optimality conditions for a Nash equilibrium. In order to solve the problem numerically, we apply the Curvilinear Multistart Algorithm [2; 3] developed for finding global solutions in nonconvex optimization problems. The proposed algorithm was tested on three and four person games. Also, for the test purpose, we have considered competitions of 3 companies at the bread market of Ulaanbaatar as the three person game and solved numerically.

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n . Our main result states that for n -player binary-action games and for constant ε, the query complexity of an ε-well-supported Nash equilibrium is exponential in n . As a consequence of this result, we get an exponential lower bound on the rate of convergence of adaptive dynamics to approximate Nash equilibria.

We consider an environment-protection hierarchical differential game between enterprise and state with the state acting as the leader. An algorithm for approximate solution of the game is proposed.

We define a benchmark for definitions of complexity in systems with spatio-temporal dynamics and employ it in the study of Collective Motion. We show that LMC’s complexity displays interesting properties in such systems, while a statistical complexity model (SCM) based on autocorrelation reasonably meets our perception of complexity. However this SCM is not as general as desirable, as it does not merely depend on the system’s Probability Distribution Function. Inspired by the notion of Fisher information, we develop a SCM candidate, which we call the Fisher-gradient complexity, which exhibits nice properties from the viewpoint of our benchmark.

This paper presents and discusses the research framework of complexity in simulation gaming. The complexity of a simulation game has three dimensions: game systematic complexity, game social complexity, and complex dynamics of gameplay. The author presents two perspectives on the complexity of a simulation game. The first perspective is a designer perspective and game-scoring model proposed by the author to solve the internal model dilemma of interdependence. The second perspective is the player’s perspective and, in this paper, the research model and procedure are described for discussion.

Gomoku is an ancient board game. The traditional approach to solving the Gomoku is to apply tree search on a Gomoku game tree. Although the rules of Gomoku are straightforward, the game tree complexity is enormous. Unlike other board games such as chess and Shogun, the Gomoku board state is more intuitive. This feature is similar to another famous board game, the game of Go. The success of AlphaGo [5, 6] inspired us to apply a supervised learning method and deep neural network in solving the Gomoku game. We designed a deep convolutional neural network model to help the machine learn from the training data. In our experiment, we got 69% accuracy on the training data and 38% accuracy on the testing data. Finally, we combined the trained deep neural network model with a hard-coded convolution-based Gomoku evaluation function to form a hybrid Gomoku artificial intelligence (AI) which further improved performance.

In 2015, the President of Indonesia established Bekraf—stands for Badan Ekonomi Kreatif (Creative Economy Association of Indonesia)—through Presidential Regulation (Perpres) number 6. The purpose of establishing Bekraf is to enable creative business actors to collaborate with government in developing this nation’s entertainment industries. Nowadays, the game is accepted as an alternative form of education. Therefore, the researchers aim to assist the business of digital creative field to estimate computer game development effort. This research is based on Function Points (FP) method, which is better known as cost calculation of software application development project. The result of this study shows the need to modify the definition of computer games’ parameters, including input, output, inquiry, internal file logic, and external file logic. Besides that, the complexity factors should be redefined and synchronized with 8 items of LeBlanc Taxonomy. Then, its collaboration is named Game Complexity Factors (GCF), consists of 22 items of complexity factors—8 items from LeBlanc Taxonomy and the rest from technical complexity.

The red-blue pebble game was formulated in the 1980s~\citeHK81 to model the I/O complexity of algorithms on a two-level memory hierarchy. Given a directed acyclic graph representing computations (vertices) and their dependencies (edges), the red-blue pebble game allows sequentially adding, removing, and recoloring red or blue pebbles according to a few rules, where red pebbles represent data in cache (fast memory) and blue pebbles represent data on disk (slow, external memory). Specifically, a vertex can be newly pebbled red if and only if all of its predecessors currently have a red pebble; pebbles can always be removed; and pebbles can be recolored between red and blue (corresponding to reading or writing data between disk and cache, also called I/Os or memory transfers). Given an upper bound on the number of red pebbles at any time (the cache size), the goal is to compute a game execution with the fewest pebble recolorings (memory transfers) that finish with pebbles on a specified subset of nodes (outputs get computed). In this paper, we investigate the complexity of computing this trade-off between red-pebble limit (cache size) and number of recolorings (memory transfers) in general DAGs. First we prove this problem PSPACE-complete through an extension of the proof PSPACE-hardness of black pebbling complexity~\citeGLT80. Second, we consider a natural restriction on the red-blue pebble game to forbid pebble deletions, or equivalently, forbid discarding data from cache without first writing it to disk. This assumption both simplifies the model and immediately places the trade-off computation problem within NP. Unfortunately, we show that even this restricted version is NP-complete. Finally, we show that the trade-off problem parameterized by the number of transitions is W[1]-hard, meaning that there is likely no algorithm running in a fixed polynomial for constant number of transitions.

This paper studies the complexity of solving the class G of all N -player non-cooperative games with continuous action spaces that admit at least one Nash equilibrium (NE). We consider a distributed Nash seeking setting where agents communicate with a set of system nodes (SNs), over noisy communication channels, to obtain the required information for updating their actions. The complexity of solving games in the class G is defined as the minimum number of iterations required to find a NE of any game in G with e accuracy. Using information-theoretic inequalities, we derive a lower bound on the complexity of solving the game class G that depends on the Kolmogorov 2e-capacity of the constraint set and the total capacity of the communication channels. We also derive a lower bound on the complexity of solving games in G which depends on the volume and surface area of the constraint set.

We study [Lee, J. D., Riet, A. F - Saturation Games , submitted to Discrete Mathematics, arXiv:1406.1500 [math.CO] ; Lee, J. D., Riet, A. New F - Saturation Games on Directed Graphs , submitted to Discrete Mathematics, arXiv:1409.0565 [math.CO] ] F - saturation games , first introduced by Furedi, Reimer and Seress [Furedi, Z., Reimer, D. and Seress, A., Hajnal's Triangle-Free Game and Extremal Graph Problems , Congr. Numer. 82 (1991), 123–128] in 1991, and named as such by West [West, D., The F - Saturation Game (2009) and Game Saturation Number (2011) , http://www.math.uiuc.edu/~west/regs/fsatgame.html (last visited March 6, 2015)]. The main question is to determine the length of the game whilst avoiding various classes of graphs, playing on a large complete graph. We show lower bounds on the length of path-avoiding games, and more precise results for short paths. We show sharp results for the tree avoiding game and the star avoiding game. We also study directed analogues of these games. We show tight results on the walk-avoiding game. We also examine an intermediate game played on undirected graphs, such that there exists an orientation avoiding a given family of directed graphs, and show bounds on the score. This last game is known to be equivalent to a recent game studied in [Hefetz, D., Krivelevich, M., Naor, A., Stojakovic, M., On Saturation Games , preprint, arXiv:1406.2111v2 [math.CO] ], and we give new bounds for biased versions of this game.

For a conflict-controlled dynamical system whose motion is described by neutraltype functional differential equations in Hale’s form and for a quality index that evaluates the motion history realized up to the terminal instant of time, we consider a differential game in the class of control-with-guide strategies. We construct an approximating differential game in the class of pure positional strategies in which the motion of a conflict-controlled system is described by ordinary differential equations and the quality index is terminal. We show that the value of the approximating game gives the value of the original game in the limit, and that the optimal strategies in the original game can be constructed by using the optimal motions of the approximating game as guides.

The state complexity of basic operations on regular languages considering complete deterministic finite automata (DFA) has been extensively studied in the literature. But, if incomplete DFAs are considered, transition complexity is also a significant measure. In this paper we study the incomplete (deterministic) state and transition complexity of some operations for regular and finite languages. For regular languages we give a new tight upper bound for the transition complexity of the union, which refutes the conjecture presented by Y. Gao et al. For finite languages, we correct the published state complexity of concatenation for complete DFAs and provide a tight upper bound for the case when the right operand is larger than the left one. We also present some experimental results to test the behavior of those operations on the average case, and we conjecture that for many operations and in practical applications the worst-case complexity is seldom reached.

Game tree search is a classical problem in the field of game theory and artificial intelligence. Fast game tree search algorithm is critical for computer games asking for real-time responses. In this paper, we focus on how to leverage massive parallelism capabilities of GPU to accelerate the speed of game tree search algorithms and propose a concise and general parallel game tree search algorithm on GPU. The performance model of our algorithm is presented and analyzed theoretically. We implement the algorithm for two real computer games called Connect6 and Chess. We also use these two games to verify the effectiveness and efficiency of our algorithm. Experiments support our theoretical results and show good performance of our approach. Compared to classical CPU-based game tree search algorithms, our algorithm can achieve speedups of 89.95x for Connect6 and 11.43x for Chess, in case of no pruning. When pruning is considered, which means the practical performance of our algorithm, the speedup can reach about 10.58x for Connect6 and 7.26x for Chess. The insight of our work is that using GPU is a feasible way to improve the performance of game tree search algorithms.

This paper considers the computational complexity of the design of voting rules, which is formulated by simple games. We prove that it is an NP-complete problem to decide whether a given simple game is stable, or not.

The computational complexity of a variety of problems from algorithmic game theory is investigated. These are variations on the question whether a strategy in a normal form game survives iterated elimination of dominated strategies. The difficulty of the computational task depends on the notion of dominance involved, on the number of distinct payoffs and whether the game is constant-sum. Most of the open cases are fully classified, and the remaining cases are shown to be equivalent to certain questions regarding elimination orders on graphs. The classifications may serve as the basis for a discussion to what extent iterated dominance could be useful to restrict rationality for computationally bounded agents.

In this paper, we formulate a sum-rate maximization problem for device-to-device (D2D) communications underlaying downlink multiple-input multiple-output heterogenous cellular networks subject to the quality of service constraints and the interference temperature constraint. Since it is difficult to obtain the optimal solution due to the high complexity, game theory is used to study the resource allocation in such networks. The proposed game is a potential game where the existence of Nash equilibrium (NE) is guaranteed. A practical resource allocation algorithm based on better response dynamic is proposed. We prove that the proposed algorithm can converge to a feasible NE. Numerical results show that the proposed algorithm can achieve near optimal sum rate performance with low complexity.

Algorithmic specified complexity (ASC) measures the degree to which an object is meaningful. Neither fundamental Shannon nor Kolmogorov information models are equipped to do so. ASC uses performance context in an information theoretic framework to measure the degree of specified complexity in bits. To illustrate, we apply ASC to Conway’s Game of Life to differentiate patterns designed by programmers from those originating by chance. A variety of machines created by Game of Life hobbyists, as expected, exhibit high ASC thereby corroborating ASC’s efficacy.

The game of Amazons is a modern board game with simple rules and nice mathematical properties. It has a high computational complexity. In 2001, the starting position on a 5 $\,\times\,$ 5 board was proven to be a first player win. The enhanced Amazons solver presented here extends previous work in the following five ways: by building more powerful endgame databases, including a new type of databases for so-called blocker territories, by improving the rules for computing bounds on complex game positions, by local search to find tighter local bounds, by using ideas from combinatorial game theory to find wins earlier, and by using a df-pn based solver. Using the improved solver, the starting positions for Amazons on the 4 $\,\times\,$ 5, 5 $\,\times\,$ 4, 4 $\,\times\,$ 6, 5 $\,\times\,$ 6, and 4 $\,\times\,$ 7 boards were shown to be first player wins, while 6 $\,\times\,$ 4 is a second player win. The largest proof, for the 5 $\,\times\,$ 6 board, is presented in detail.

Parikh’s game logic is a PDL-like fixpoint logic interpreted on monotone neighbourhood frames that represent the strategic power of players in determined two-player games. Game logic translates into a fragment of the monotone \(\mu \)-calculus, which in turn is expressively equivalent to monotone modal automata. Parity games and automata are important tools for dealing with the combinatorial complexity of nested fixpoints in modal fixpoint logics, such as the modal \(\mu \)-calculus. In this paper, we (1) discuss the semantics a of game logic over neighbourhood structures in terms of parity games, and (2) use these games to obtain an automata-theoretic characterisation of the fragment of the monotone \(\mu \)-calculus that corresponds to game logic. Our proof makes extensive use of structures that we call syntax graphs that combine the ease-of-use of syntax trees of formulas with the flexibility and succinctness of automata. They are essentially a graph-based view of the alternating tree automata that were introduced by Wilke in the study of modal \(\mu \)-calculus.

Game theoretic reasoning about multi-agent systems has been made more tractable by algorithms that exploit various types of independence in agents' utilities. However, previous work has assumed that a game's precise independence structure is given in advance. This paper addresses the problem of finding independence structure in a general form game when it is not known ahead of time, or of finding an approximation when full independence does not exist. We give an expected polynomial time algorithm to divide a bounded-payout normal form game into factor games that isolate independent strategic interactions. We also show that the best approximate factoring can be found in polynomial time for a specific interaction that is not fully independent. Once known, factors aide computation of game theoretic solution concepts, including Nash equilibria (or e-equilibria for approximate factors), in some cases guaranteeing polynomial complexity where previous bounds were exponential.

Multi-agent cooperation problems are becoming more and more attractive in both civilian and military applications. In multi-agent cooperation problems, different network topologies will decide different manners of cooperation between agents. A centralized system will directly control the operation of each agent with information flow from a single centre, while in a distributed system, agents operate separately under certain communication protocols. In this paper, a systematic distributed optimization approach will be established based on a learning game algorithm. The convergence of the algorithm will be proven under the game theory framework. Two typical consensus problems will be analyzed with the proposed algorithm. The contributions of this work are threefold. First, the designed algorithm inherits the properties in learning game theory for problem simplification and proof of convergence. Second, the behaviour of learning endows the algorithm with robustness and autonomy. Third, with the proposed algorithm, the consensus problems will be analyzed from a novel perspective.

This paper introduces an algorithm to learn the strategy updating rule for a two- person Boolean game using the records of the history strategies and game results. The two-person game in this paper is introduced as a zero-sum game along with a Boolean strategy set, and the strategies are governed by fixed Boolean functions whose arguments are the history strategies and game results with additive binary noise, which can be modeled as a stochastic Boolean dynamic system. However, for this easy-to-play game, there is no effective convenient methods to win more often. To achieve this goal, a learning algorithm based on Boolean regression and maximum-likelihood estimation is put forward to learn the strategy updating rule and the noise property using the records of the history strategies and game results. In addition, extensive simulations via actual examples have illustrated the effectiveness of the proposed learning algorithm.