A Fast Algorithm for Computing the Deficiency Number of a Mahjong Hand

• URL: http://arxiv.org/abs/2108.06832v1
• Date: Sun, 15 Aug 2021 22:44:14 GMT
• Title: A Fast Algorithm for Computing the Deficiency Number of a Mahjong Hand
• Abstract summary: 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.
• Score: 13.48957726008272
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The tile-based multiplayer game Mahjong is widely played in Asia and has also become increasingly popular worldwide. Face-to-face or online, each player begins with a hand of 13 tiles and players draw and discard tiles in turn until they complete a winning hand. 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. The deficiency number plays an essential role in major decision-making tasks such as selecting a tile to discard. This paper proposes a fast algorithm for computing the deficiency number of a Mahjong hand. Compared with the baseline algorithm, the new algorithm is usually 100 times faster and, more importantly, respects the agent's knowledge about available tiles. The algorithm can be used as a basic procedure in all Mahjong variants by both rule-based and machine learning-based Mahjong AI.

Related papers

• Mahjax: A GPU-Accelerated Mahjong Simulator for Reinforcement Learning in JAX [38.43966132249977]
  Riichi Mahjong is a multi-player, imperfect-information game characterized by byity and high-dimensional state spaces.<n>We introduce textbfMahjax, a fully vectorized Riichi Mahjong environment implemented in JAX to enable large-scale rollout parallelization.<n>We show that Mahjax achieves throughputs of up to textbf2 million and textbf1 million steps per second.
  arXiv  Detail & Related papers  (2026-05-20T00:33:28Z)
• Adapting Rules of Official International Mahjong for Online Players [3.9039720954900243]
  We employ a world champion AI to engage in self-play competitions and conduct statistical data analysis.<n>Based on our findings, we propose rule adaptations to make the game more suitable for the online environment.<n>This work is an initial attempt to use data from AI systems to evaluate Official Internatinoal Mahjong's game balance.
  arXiv  Detail & Related papers  (2026-01-13T04:36:05Z)
• General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chess [68.20244032271847]
  We present Obscuro, the first superhuman AI for Fog of War chess.<n>It introduces advances to search in imperfect-information games, enabling strong, scalable reasoning.<n>Experiments against the prior state-of-the-art AI and human players show that Obscuro is significantly stronger.
  arXiv  Detail & Related papers  (2025-06-02T01:41:27Z)
• CFR-p: Counterfactual Regret Minimization with Hierarchical Policy Abstraction, and its Application to Two-player Mahjong [2.741266294612776]
  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.
  arXiv  Detail & Related papers  (2023-07-22T14:38:47Z)
• The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
  We introduce an alternative framework for decision-time planning that is not based on solving subgames, but rather on update equivalence. We derive a provably sound search algorithm for fully cooperative games based on mirror descent and a search algorithm for adversarial games based on magnetic mirror descent.
  arXiv  Detail & Related papers  (2023-04-25T20:28:55Z)
• 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 Strategy Card Game (Hearthstone) with Improved Techniques [8.399453146308502]
  Strategy card game is demanding on the intelligent game-play and can be an ideal test-bench for AI. Previous work combines an end-to-end policy function and an optimistic smooth fictitious play. In this work, we apply such algorithms to Hearthstone, a famous commercial game that is more complicated in game rules and mechanisms.
  arXiv  Detail & Related papers  (2023-03-09T11:52:52Z)
• DanZero: Mastering GuanDan Game with Reinforcement Learning [121.93690719186412]
  Card game AI has always been a hot topic in the research of artificial intelligence. In this paper, we are devoted to developing an AI program for a more complex card game, GuanDan. We propose the first AI program DanZero for GuanDan using reinforcement learning technique.
  arXiv  Detail & Related papers  (2022-10-31T06:29:08Z)
• Building a 3-Player Mahjong AI using Deep Reinforcement Learning [9.603486077267693]
  We present Meowjong, an AI for Sanma using deep reinforcement learning. Meowjong's models achieve test accuracies comparable with AIs for 4-player Mahjong. Being the first ever AI in Sanma, we claim that Meowjong stands as a state-of-the-art in this game.
  arXiv  Detail & Related papers  (2022-02-25T17:41:43Z)
• On the complexity of Dark Chinese Chess [5.019685897194575]
  Dark Chinese chess combines some of the most complicated aspects of board and card games. This paper provides a complexity analysis for the game of dark Chinese chess.
  arXiv  Detail & Related papers  (2021-12-06T13:08:53Z)
• 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)
• TotalBotWar: A New Pseudo Real-time Multi-action Game Challenge and Competition for AI [62.997667081978825]
  TotalBotWar is a new pseudo real-time multi-action challenge for game AI. The game is based on the popular TotalWar games series where players manage an army to defeat the opponent's one.
  arXiv  Detail & Related papers  (2020-09-18T09:13:56Z)
• 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)

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.