Perfect aggregation of information in two-person multistage games with fixed sequence of moves and aggregated information on partner’s choice

Two-person multistage game with fixed sequence of moves is considered, under perfect information on existing history of the game and aggregated information on the current move of player 2. Having this information at each stage i, player 1 is the first to choose his move x(in1)(.); moreover, in the beginning of the game player 1 announces his strategy x(.)=(a(in1)(.),..., x(in)(.)) for n future stages. Given information regarding the choice of player 1 and history of the game, player 2 strives to maximize his payoff function via the strategy v=(v(in1), v(in2),..., v(inn)). In this paper the sufficient conditions of perfect aggregation, involving certain results from the theory of Lie groups, are provided for the game in question.     

Exploration of Player Behaviours from Broadcast Badminton Videos

Understanding an opposing player's behaviours and weaknesses is often the key to winning a badminton game. This study presents a system to extract game data from broadcast badminton videos, and visualize the extracted data to help coaches and players develop effective tactics. Specifically, we apply state-of-the-art machine learning methods to partition a broadcast video into segments, in which each video segment shows a badminton rally. Next, we detect players' feet in each video frame and transform the player positions into the court coordinate system. Finally, we detect hit frames in each rally, in which the shuttle moves towards the opposite directions. By visualizing the extracted data, our system conveys when and where players hit the shuttle in historical games. Since players tend to smash or drop shuttles under a specific location, we provide users with interactive tools to filter data and focus on the distributions conditioned by player positions. This strategy also reduces visual clutter. Besides, our system plots the shuttle hitting distributions side-by-side, enabling visual comparison and analysis of player behaviours under different conditions. The results and the use cases demonstrate the feasibility of our system.     

Coevolution versus self-play temporal difference learning for acquiring position evaluation in small-board go

Two learning methods for acquiring position evaluation for small Go boards are studied and compared. In each case the function to be learned is a position-weighted piece counter and only the learning method differs. The methods studied are temporal difference learning (TDL) using the self-play gradient-descent method and coevolutionary learning, using an evolution strategy. The two approaches are compared with the hope of gaining a greater insight into the problem of searching for "optimal" zero-sum game strategies. Using tuned standard setups for each algorithm, it was found that the temporal-difference method learned faster, and in most cases also achieved a higher level of play than coevolution, providing that the gradient descent step size was chosen suitably. The performance of the coevolution method was found to be sensitive to the design of the evolutionary algorithm in several respects. Given the right configuration, however, coevolution achieved a higher level of play than TDL. Self-play results in optimal play against a copy of itself. A self-play player will prefer moves from which it is unlikely to lose even when it occasionally makes random exploratory moves. An evolutionary player forced to perform exploratory moves in the same way can achieve superior strategies to those acquired through self-play alone. The reason for this is that the evolutionary player is exposed to more varied game-play, because it plays against a diverse population of players.     

A review of: “HUMANIZED INPUT” Tom Gilb and Gerald M. Weinberg Winthrop Computer Series,Winthrop Publishing,Cambridge, Mass. 1977 383 pages $4.00 ISBN 0-87626-345-7

Kayles is a nonpartizan two-person game. In such games the moves available to both the players are the same and either the player on move wins or the previous player wins. In the “normal form” of the game, the last player who can make a move is declared the winner. In the “misere form” of the game, the player who makes the last move is declared the loser. The complete analysis of the normal form of the game of Kayles has been described by Berlekamp, Conway, and Guy. This paper completes their analysis of the misere form of Kayles. This is done on the basis of certain properties of what have been called “wild” positions of misere games.     

将选择题嵌入到飞行棋之中

将选择题嵌入到飞行棋游戏之中,玩家在掷骰子之后必须选择问题的答案才能移动棋子,如果答案选择正确则棋子正向移动,否则,棋子反向移动。因此,正确地选择答案就成了取胜的重要因素,这可以促使玩家主动记忆相关知识,从而提高了学习效率。     

关于Hex博弈最优获胜策略的一种新方法*

Hex博奕Hex(n)是一种在六边形拼接的n×n棋盘上进行的二人博奕,博奕中二人轮流下红色和蓝色棋子,先构造出一条从一边连到对边的单色路者为胜者。Hex博奕中先手有必胜策略。设δ(n)为Hex(n)中先手能保证获胜所需的最少步数,Garikai Campbell通过研究其他对象间接地证明了δ(n)>n对任意n≥4成立。利用新的方法来分析对称性,给出了δ(n)>n一个直接而简单的证明,并在此基础上利用计算证明了δ(5)=7。     

The complexity of constraint satisfaction games and QCSP

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain to the variables, in a specified order. The first player tries to satisfy all constraints, while the other tries to break at least one constraint; the goal is to decide whether the first player has a winning strategy. We show that such games can be conveniently represented by a logical form of quantified constraint satisfaction, where an instance is given by a first-order sentence in which quantifiers alternate and the quantifier-free part is a conjunction of (positive) atomic formulas; the goal is to decide whether the sentence is true.While the problem of deciding such a game is PSPACE-complete in general, by restricting the set of allowed constraint predicates, one can obtain infinite classes of constraint satisfaction games of lower complexity. We use the quantified constraint satisfaction framework to study how the complexity of deciding such a game depends on the parameter set of allowed predicates. With every predicate, one can associate certain predicate-preserving operations, called polymorphisms. We show that the complexity of our games is determined by the surjective polymorphisms of the constraint predicates. We illustrate how this result can be used by identifying the complexity of a wide variety of constraint satisfaction games.     

Concurrent reachability games

We consider concurrent two-player games with reachability objectives. In such games, at each round, player 1 and player 2 independently and simultaneously choose moves, and the two choices determine the next state of the game. The objective of player 1 is to reach a set of target states; the objective of player 2 is to prevent this. These are zero-sum games, and the reachability objective is one of the most basic objectives: determining the set of states from which player 1 can win the game is a fundamental problem in control theory and system verification. There are three types of winning states, according to the degree of certainty with which player 1 can reach the target. From type-1 states, player 1 has a deterministic strategy to always reach the target. From type-2 states, player 1 has a randomized strategy to reach the target with probability 1. From type-3 states, player 1 has for every real ε>0$\epsilon >0$ a randomized strategy to reach the target with probability greater than 1−ε$1-\epsilon$. We show that for finite state spaces, all three sets of winning states can be computed in polynomial time: type-1 states in linear time, and type-2 and type-3 states in quadratic time. The algorithms to compute the three sets of winning states also enable the construction of the winning and spoiling strategies.     

The Complexity of Flood Filling Games

We study the complexity of the popular one player combinatorial game known as Flood-It. In this game the player is given an n×n board of tiles where each tile is allocated one of c colours. The goal is to make the colours of all tiles equal via the shortest possible sequence of flooding operations. In the standard version, a flooding operation consists of the player choosing a colour k, which then changes the colour of all the tiles in the monochromatic region connected to the top left tile to k. After this operation has been performed, neighbouring regions which are already of the chosen colour k will then also become connected, thereby extending the monochromatic region of the board. We show that finding the minimum number of flooding operations is NP-hard for c≥3 and that this even holds when the player can perform flooding operations from any position on the board. However, we show that this ‘free’ variant is in P for c=2. We also prove that for an unbounded number of colours, Flood-It remains NP-hard for boards of height at least 3, but is in P for boards of height 2. Next we show how a (c−1) approximation and a randomised 2c/3 approximation algorithm can be derived, and that no polynomial time constant factor, independent of c, approximation algorithm exists unless P=NP. We then investigate how many moves are required for the ‘most demanding’ n×n boards (those requiring the most moves) and show that the number grows as fast as Q(?c n)\Theta(\sqrt{c}\, n). Finally, we consider boards where the colours of the tiles are chosen at random and show that for c≥2, the number of moves required to flood the whole board is Ω(n) with high probability.     

Fixed-Point Logics and Solitaire Games

The model-checking games associated with fixed-point logics are parity games, and it is currently not known whether the strategy problem for parity games can be solved in polynomial time. We study Solitaire-LFP, a fragment of least fixed-point logic, whose evaluation games are nested soltaire games. This means that on each strongly connected component of the game, only one player can make nontrivial moves. Winning sets of nested solitaire games can be computed efficiently. The model-checking problem for Solitaire-LFP is Pspace-complete in general and Ptime-complete for formulae of bounded width. On finite structures (but not on infinite ones), Solitaire-LFP is equivalent to transitive closure logic. We also consider the solitaire fragment of guarded fixed-point logics. Due to the restricted quantification pattern of these logics, the associated games are small and therefore admit more efficient model-checking algorithms.     

Equilibria problems on games: Complexity versus succinctness

We study the computational complexity of problems involving equilibria in strategic games and in perfect information extensive games when the number of players is large. We consider, among others, the problems of deciding the existence of a pure Nash equilibrium in strategic games or deciding the existence of a pure Nash or a subgame perfect Nash equilibrium with a given payoff in finite perfect information extensive games. We address the fundamental question of how can we represent a game with a large number of players? We propose three ways of representing a game with different degrees of succinctness for the components of the game. For perfect information extensive games we show that when the number of moves of each player is large and the input game is represented succinctly these problems are PSPACE-complete. In contraposition, when the game is described explicitly by means of its associated tree all these problems are decidable in polynomial time. For strategic games we show that the complexity of deciding the existence of a pure Nash equilibrium depends on the succinctness of the game representation and then on the size of the action sets. In particular we show that it is NP-complete, when the number of players is large and the number of actions for each player is constant, and that the problem is -complete when the number of players is a constant and the size of the action sets is exponential in the size of the game representation. Again when the game is described explicitly the problem is decidable in polynomial time.     

An inquiry dialogue system

The majority of existing work on agent dialogues considers negotiation, persuasion or deliberation dialogues; we focus on inquiry dialogues, which allow agents to collaborate in order to find new knowledge. We present a general framework for representing dialogues and give the details necessary to generate two subtypes of inquiry dialogue that we define: argument inquiry dialogues allow two agents to share knowledge to jointly construct arguments; warrant inquiry dialogues allow two agents to share knowledge to jointly construct dialectical trees (essentially a tree with an argument at each node in which a child node is a counter argument to its parent). Existing inquiry dialogue systems only model dialogues, meaning they provide a protocol which dictates what the possible legal next moves are but not which of these moves to make. Our system not only includes a dialogue-game style protocol for each subtype of inquiry dialogue that we present, but also a strategy that selects exactly one of the legal moves to make. We propose a benchmark against which we compare our dialogues, being the arguments that can be constructed from the union of the agents’ beliefs, and use this to define soundness and completeness properties that we show hold for all inquiry dialogues generated by our system.     

Adjusting for scorekeeper bias in NBA box scores

Box score statistics in the National Basketball Association are used to measure and evaluate player performance. Some of these statistics are subjective in nature and since box score statistics are recorded by scorekeepers hired by the home team for each game, there exists potential for inconsistency and bias. These inconsistencies can have far reaching consequences, particularly with the rise in popularity of daily fantasy sports. Using box score data, we estimate models able to quantify both the bias and the generosity of each scorekeeper for two of the most subjective statistics: assists and blocks. We then use optical player tracking data for the 2015–2016 season to improve the assist model by including other contextual spatio-temporal variables such as time of possession, player locations, and distance traveled. From this model, we present results measuring the impact of the scorekeeper and of the other contextual variables on the probability of a pass being recorded as an assist. Results for adjusting season assist totals to remove scorekeeper influence are also presented.     

Towards solving 2-TBSG efficiently

Two-player turn-based stochastic game (2-TBSG) is a two-player game model which aims to find Nash equilibriums and is widely utilized in reinforcement learning and AI. Inspired by the fact that the simplex method for solving the deterministic discounted Markov decision processes is strongly polynomial independent of the discount factor, we are trying to answer an open problem whether there is a similar algorithm for 2-TBSG. We develop a simplex strategy iteration where one player updates its strategy with a simplex step while the other player finds an optimal counterstrategy in turn, and a modified simplex strategy iteration. Both of them belong to a class of geometrically converging algorithms. We establish the strongly polynomial property of these algorithms by considering a strategy combined from the current strategy and the equilibrium strategy. Moreover, we present a method to transform general 2-TBSGs into special 2-TBSGs where each state has exactly two actions.     

Guessing Bank PINs by Winning a Mastermind Game

In this paper we formally prove that the problem of cracking, i.e., correctly guessing, bank PINs used for accessing Automated Teller Machines and the problem of solving the Generalized Mastermind Game are strictly related. The Generalized Mastermind Game with N colors and k pegs is an extension of the well known Mastermind game, played with 6 colors and 4 pegs. The rules are the same, one player has to conceal a sequence of k colored pegs behind a screen and another player has to guess the exact position and colors of the pegs using the minimal number of moves. We first introduce a general game, called the Extended Mastermind Game (EMG), and we then formally prove it includes both the Generalized Mastermind Game and the PIN cracking Problem. We then present some experimental results that we have devised using a computer program that optimizes a well known technique presented by Knuth in 1976 for the standard Mastermind game. We finally show that the program improves the as state-of-the-art Mastermind solvers as it is able to compute strategies for cases which were not yet covered. More interestingly, the same solving strategy is adapted also for the solution of the PIN cracking problem.     

Non-clairvoyant Scheduling Games

In a scheduling game, each player owns a job and chooses a machine to execute it. While the social cost is the maximal load over all machines (makespan), the cost (disutility) of each player is the completion time of its own job. In the game, players may follow selfish strategies to optimize their cost and therefore their behaviors do not necessarily lead the game to an equilibrium. Even in the case there is an equilibrium, its makespan might be much larger than the social optimum, and this inefficiency is measured by the price of anarchy—the worst ratio between the makespan of an equilibrium and the optimum. Coordination mechanisms aim to reduce the price of anarchy by designing scheduling policies that specify how jobs assigned to a same machine are to be scheduled. Typically these policies define the schedule according to the processing times as announced by the jobs. One could wonder if there are policies that do not require this knowledge, and still provide a good price of anarchy. This would make the processing times be private information and avoid the problem of truthfulness. In this paper we study these so-called non-clairvoyant policies. In particular, we study the RANDOM policy that schedules the jobs in a random order without preemption, and the EQUI policy that schedules the jobs in parallel using time-multiplexing, assigning each job an equal fraction of CPU time.     

Existence of a feedback equilibrium for two-stage Stackelberg games

In this paper we consider a two-stage feedback game in which two players solve a Stackelberg problem at each stage and each player knows the state of the game at every level of play. In this kind of game, the leader does not have the ability to announce his strategy at all levels of play prior to the start of the game. Without assuming that at each stage the Stackelberg problem has a unique solution, we define a concept of “feedback Stackelberg solution” and give sufficient conditions to get existence of such a solution     

Effect of Network Quality on Player Departure Behavior in Online Games

Understanding the impact of network conditions on player satisfaction, which is one of the major concerns of network game designers, is a popular research topic. Of the various ways to gauge user satisfaction, in this paper, we focus on how network quality affects a player's decision to leave a game prematurely. To answer this question, we analyze a 1,356-million-packet trace from a large commercial massively multiplayer online role-playing game (MMORPG) called ShenZhou Online. We show that both network delay and network loss significantly affect a player's decision to leave a game prematurely. It is feasible to predict whether players will quit prematurely based on the network conditions they experience. The proposed model can determine the relative impact of different types of network impairment. For our traces, the degrees of player intolerance to network delay, delay jitter, client packet loss, and server packet loss are in the proportion of 1:2:4:3 approximately. The model can also be used to make system design decisions. Through simulations, we show that by prioritizing server processing according to the goodness of network conditions, employing dejitter buffers, or replacing TCP with a more lightweight transport protocol, the probability of premature departure can be significantly reduced. In this way, we demonstrate how our model of players' network experience provides feedback for the design of online games.