Let's Play Mahjong!

Mahjong is a very popular tile-based game commonly played by four players. Each player begins with a hand of 13 tiles and, in turn, players draw and discard (i.e., change) tiles until they complete a legal hand using a 14th tile. In this paper, we initiate a mathematical and AI study of the Mahjong game and try to answer two fundamental questions: how bad is a hand of 14 tiles? and which tile should I discard? We define and characterise the notion of deficiency and present an optimal policy to discard a tile in order to increase the chance of completing a legal hand within $k$ tile changes for each $k\geq 1$.