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.

In the past decades, we have seen AI programs that can beat best human players in perfect information games including checker, chess and Go, where players know everything occurred in the game before making a decision. Imperfect information games are more challenging. Very recently, important progress has been made in solving the two-player heads-up limit Texas hold'em poker [2] and its no-limit version [3], which are the smallest variants of poker played competitively by humans. In this paper, we initiate a mathematical and AI study of the more popular and more complicated Mahjong game. Mahjong is a very popular tile-based multiplayer game played worldwide.