A Fast Algorithm for Computing the Deficiency Number of a Mahjong Hand
This provides a faster and more accurate tool for decision-making in Mahjong AI, applicable across variants and AI methods, but it is incremental as it builds on existing deficiency number computation.
The paper tackles the problem of efficiently computing the deficiency number (shanten number) for Mahjong hands, which estimates tile changes needed to win, and results in an algorithm that is typically 100 times faster than the baseline while incorporating knowledge of available tiles.
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.