CFR-p: Counterfactual Regret Minimization with Hierarchical Policy Abstraction, and its Application to Two-player Mahjong

• URL: http://arxiv.org/abs/2307.12087v1
• Date: Sat, 22 Jul 2023 14:38:47 GMT
• Title: CFR-p: Counterfactual Regret Minimization with Hierarchical Policy Abstraction, and its Application to Two-player Mahjong
• Abstract summary: We study two-player Mahjong by conducting game theoretical analysis and making a hierarchical abstraction to CFR based on winning policies. This framework can be generalized to other imperfect information games.
• Score: 2.741266294612776
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Counterfactual Regret Minimization(CFR) has shown its success in Texas Hold'em poker. We apply this algorithm to another popular incomplete information game, Mahjong. Compared to the poker game, Mahjong is much more complex with many variants. We study two-player Mahjong by conducting game theoretical analysis and making a hierarchical abstraction to CFR based on winning policies. This framework can be generalized to other imperfect information games.

Related papers

• Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret [64.73231630190121]
  Learning to play zero-sum games is a fundamental problem in game theory and machine learning.<n>We investigate adversarial learning in zero-sum games under bandit feedback, aiming to minimize the deficit against the maximin pure strategy.<n>We show that the Tsallis-INF algorithm achieves $O(c log T)$ instance-dependent regret with a game-dependent parameter $c$.
  arXiv  Detail & Related papers  (2026-02-06T03:26:01Z)
• A Survey on Game Theory Optimal Poker [0.0]
  No non-trivial imperfect information game has been solved to date. This makes poker a great test bed for Artificial Intelligence research. We discuss the intricacies of abstraction techniques, betting models, and specific strategies employed by successful poker bots.
  arXiv  Detail & Related papers  (2024-01-02T04:19:25Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  We consider the problem of decentralized multi-agent reinforcement learning in Markov games. We show that no algorithm attains no-regret in general-sum games when executed independently by all players. We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
  arXiv  Detail & Related papers  (2023-03-22T03:28:12Z)
• Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning [95.78031053296513]
  No-press Diplomacy is a complex strategy game involving both cooperation and competition. We introduce a planning algorithm we call DiL-piKL that regularizes a reward-maximizing policy toward a human imitation-learned policy. We show that DiL-piKL can be extended into a self-play reinforcement learning algorithm we call RL-DiL-piKL.
  arXiv  Detail & Related papers  (2022-10-11T14:47:35Z)
• Principal Trade-off Analysis [79.16635054977068]
  We show "Principal Trade-off Analysis" (PTA), a decomposition method that embeds games into a low-dimensional feature space. PTA represents an arbitrary two-player zero-sum game as the weighted sum of pairs of 2D feature planes. We demonstrate the validity of PTA on a quartet of games (Kuhn poker, RPS+2, Blotto, and Pokemon)
  arXiv  Detail & Related papers  (2022-06-09T18:16:28Z)
• A Fast Algorithm for Computing the Deficiency Number of a Mahjong Hand [13.48957726008272]
  The tile-based multiplayer game Mahjong is widely played in Asia and has also become increasingly popular worldwide. An important notion in Mahjong is the deficiency number (a.k.a. shanten number in Japanese Mahjong) of a hand, which estimates how many tile changes are necessary to complete the hand into a winning hand. This paper proposes a fast algorithm for computing the deficiency number of a Mahjong hand.
  arXiv  Detail & Related papers  (2021-08-15T22:44:14Z)
• Discovering Multi-Agent Auto-Curricula in Two-Player Zero-Sum Games [31.97631243571394]
  We introduce a framework, LMAC, that automates the discovery of the update rule without explicit human design. Surprisingly, even without human design, the discovered MARL algorithms achieve competitive or even better performance. We show that LMAC is able to generalise from small games to large games, for example training on Kuhn Poker and outperforming PSRO.
  arXiv  Detail & Related papers  (2021-06-04T22:30:25Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
  arXiv  Detail & Related papers  (2021-04-17T20:33:24Z)
• Mastering Terra Mystica: Applying Self-Play to Multi-agent Cooperative Board Games [0.0]
  In this paper, we explore and compare multiple algorithms for solving the complex strategy game of Terra Mystica. We apply these breakthroughs to a novel state-representation of TM with the goal of creating an AI that will rival human players. In the end, we discuss the success and shortcomings of this method by comparing against multiple baselines and typical human scores.
  arXiv  Detail & Related papers  (2021-02-21T07:53:34Z)
• Suphx: Mastering Mahjong with Deep Reinforcement Learning [114.68233321904623]
  We design an AI for Mahjong, named Suphx, based on deep reinforcement learning with some newly introduced techniques. Suphx has demonstrated stronger performance than most top human players in terms of stable rank. This is the first time that a computer program outperforms most top human players in Mahjong.
  arXiv  Detail & Related papers  (2020-03-30T16:18:16Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

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.