Résultats de recherche pour « Zero-sum Imperfect Information Games »

We present FootsiesGym, an open-source environment for learning in a non-trivial two-player, zero-sum, imperfect-information game. Built on HiFight's minimalist 2D fighting game Footsies, it isolates the cyclic, non-transitive strategic interactions of fighting game neutral play while remaining simple enough for efficient analysis. We provide a vectorized simulator that enables high-throughput training on standard hardware, making the environment accessible and reproducible. We describe the design of the environment, benchmark several reinforcement learning algorithms, and discuss open research directions it enables. The code is available at https://github.com/como-research/FootsiesGym.

A general model for zero-sum stochastic games with asymmetric information is considered. In this model, each player's information at each time can be divided into a common information part and a private information part. Under certain conditions on the evolution of the common and private information, a dynamic programming characterization of the value of the game (if it exists) is presented. If the value of the zero-sum game does not exist, then the dynamic program provides bounds on the upper and lower values of the game. This dynamic program is then used for a class of zero-sum stochastic games with complete information on one side and partial information on the other, that is, games where one player has complete information about state, actions and observation history while the other player may only have partial information about the state and action history. For such games, it is shown that the value exists and can be characterized using the dynamic program. It is further shown that for this class of games, the dynamic program can be used to compute an equilibrium strategy for the more informed player in which the player selects its action using its private information and the common information belief.

We analyze a zero-sum stochastic differential game between two competing players who can choose unbounded controls. The payoffs of the game are defined through backward stochastic differential equations. We prove that each player's priority value satisfies a weak dynamic programming principle and thus solves the associated fully non-linear partial differential equation in the viscosity sense.

We generalize the results of Fleming and Souganidis (1989) on zero sum stochastic differential games to the case when the controls are unbounded. We do this by proving a dynamic programming principle using a covering argument instead of relying on a discrete approximation (which is used along with a comparison principle by Fleming and Souganidis). Also, in contrast with Fleming and Souganidis, we define our pay-off through a doubly reflected backward stochastic differential equation. The value function (in the degenerate case of a single controller) is closely related to the second order doubly reflected BSDEs.

Sequentialdecision-making under imperfect information is naturally modeled as an extensive-form game, where the Nash equilibrium serves as the predominant solution concept for two-player zero-sum settings. Counterfactual regret minimization (CFR) is a widely used framework for this purpose, iteratively reducing regret through regret matching so that the average strategy approaches a Nash equilibrium. However, the convergence efficiency of CFR remains a practical challenge. In this work, we refine and reformulate an advantage-based exponential weighting scheme, Exponential CFR (ExpCFR), which accelerates convergence by allocating greater attention to highly profitable actions during the regret-accumulation process. Building on this heuristic, we further introduce Pob-CFR, a framework that integrates population-based evolutionary training with CFR. Pob-CFR maintains a diverse population of heterogeneous CFR variants, periodically evaluating them by exploitability and replacing underperforming individuals with the elite to synchronize strategy exploration. Systematic evaluations across five benchmark games demonstrate that these methods accelerate early-to-mid convergence compared to standard CFR baselines. Furthermore, within the evaluated benchmarks, the relative advantage of the population-based architecture appears more evident in the games with larger strategic complexity.

We compare four different `game-spaces' in terms of their usefulness in characterising multi-player tabletop games, with a particular interest in any underlying change to a game's characteristics as the number of players changes. In each case we take a 16-dimensional feature space, and reduce it to a 2-dimensional visualizable landscape. We find that a space obtained from optimization of parameters in Monte Carlo Tree Search (MCTS) is the most directly interpretable to characterise our set of games in terms of the relative importance of imperfect information, adversarial opponents and reward sparsity. These results do not correlate with a space defined using attributes of the game-tree. This dimensionality reduction does not show any general effect as the number of players. We therefore consider the question using the original features to classify the games into two sets; those for which the characteristics of the game changes significantly as the number of players changes, and those for which there is no such effect.