Solving Pasur Using GPU-Accelerated Counterfactual Regret Minimization

• URL: http://arxiv.org/abs/2508.06559v1
• Date: Wed, 06 Aug 2025 15:15:11 GMT
• Title: Solving Pasur Using GPU-Accelerated Counterfactual Regret Minimization
• Abstract summary: Pasur is a fishing card game played over six rounds.<n>We use our framework to compute near-Nash equilibria via Counterfactual Regret Minimization.<n>We decompose the game tree into two key components: actual game states and scores from previous rounds.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Pasur is a fishing card game played over six rounds and is played similarly to games such as Cassino and Scopa, and Bastra. This paper introduces a CUDA-accelerated computational framework for simulating Pasur, emphasizing efficient memory management. We use our framework to compute near-Nash equilibria via Counterfactual Regret Minimization (CFR), a well-known algorithm for solving large imperfect-information games. Solving Pasur presents unique challenges due to its intricate rules and the large size of its game tree. We handle rule complexity using PyTorch CUDA tensors and to address the memory-intensive nature of the game, we decompose the game tree into two key components: (1) actual game states, and (2) inherited scores from previous rounds. We construct the Full Game Tree by pairing card states with accumulated scores in the Unfolding Process. This design reduces memory overhead by storing only essential strategy values and node connections. To further manage computational complexity, we apply a round-by-round backward training strategy, starting from the final round and recursively propagating average utilities to earlier stages. Our approach constructs the complete game tree, which on average consists of over $10^9$ nodes. We provide detailed implementation snippets. After computing a near-Nash equilibrium strategy, we train a tree-based model to predict these strategies for use during gameplay. We then estimate the fair value of each deck through large-scale self-play between equilibrium strategies by simulating, for instance, 10,000 games per matchup, executed in parallel using GPU acceleration. Similar frameworks can be extended to other reinforcement learning algorithms where the action tree naturally decomposes into multiple rounds such as turn-based strategy games or sequential trading decisions in financial markets.

Related papers

• Projected Exploitability Descent for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games [0.0]
  We introduce a new algorithm called projected exploitability descent (PED)<n>PED works by running a subgradient descent minimizing a generalized exploitability function.<n>We find that PED obtains a consistent near-monotonic improvement throughout all runs.<n>This inspires a hybrid FP-PED that runs FP for an initial burn-in period before switching to PED for stable long-run refinement.
  arXiv  Detail & Related papers  (2026-06-28T03:25:15Z)
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  We show that for a large family of games, there exists a simple black-box reduction that transforms the average iterates of an uncoupled learning dynamics into the last iterates of a new uncoupled learning dynamics.<n>Our reduction applies to games where each player's utility is linear in both their own strategy and the joint strategy of all opponents.
  arXiv  Detail & Related papers  (2025-06-04T00:24:14Z)
• Dominated Actions in Imperfect-Information Games [0.4895118383237099]
  We define and study the concept of dominated actions in imperfect-information games.<n>Our main result is a empirically-time algorithm for determining whether an action is dominated by any mixed strategy.<n>We explore the role of dominated actions in the "All In or Fold" No-Limit Texas Hold'em poker variant.
  arXiv  Detail & Related papers  (2025-04-13T20:48:44Z)
• Optimistic Online Learning in Symmetric Cone Games [5.4831302830611195]
  symmetric cone games (SCGs)<n>Online learning algorithm: Optimistic Symmetric Cone Multiplicative Weights Updates (OSCMWU)<n>We prove that the symmetric cone negative entropy is strongly convex with respect to the trace-one norm.
  arXiv  Detail & Related papers  (2025-04-04T16:59:19Z)
• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium.<n>We also give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium.<n>Our algorithm for approximately optimal EFCE is, to our knowledge, the first that achieves 3 desiderata simultaneously.
  arXiv  Detail & Related papers  (2024-12-22T09:12:05Z)
• A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games [1.104960878651584]
  Coevolutionary algorithms (CoEAs) train game playing agents using self-play.<n>In this paper, we push the scope of runtime analysis for CoEAs to games, proving a general upper bound for the number of simulated games needed.<n>After proving the main result, we provide several applications to simple well-known games: Nim, Chomp, Silver Dollar, and Turning Turtles.
  arXiv  Detail & Related papers  (2024-09-06T10:39:17Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  We study multi-agent general-sum Markov games with nonlinear function approximation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation.
  arXiv  Detail & Related papers  (2022-10-30T22:58:22Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  We show that regret can be obtained for general convex and compact strategy sets. Our dynamics are on an instantiation of optimistic follow-the-regularized-bounds over an appropriately emphlifted space. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret.
  arXiv  Detail & Related papers  (2022-06-17T12:58:58Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  We show that the state-wise average policy of this algorithm converges to an approximate Nash equilibrium (NE) of the game. We extend this algorithm to multi-player general Markov Games and show a $mathcalwidetildeO(T-1/2)$ convergence rate to Correlated Equilibria (CCE)
  arXiv  Detail & Related papers  (2022-06-06T14:23:13Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games. We introduce a new algorithm for computing optimal equilibria in all three notions.
  arXiv  Detail & Related papers  (2022-03-14T15:21:18Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.