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

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

扫码查看
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.

MahjongDeficiency numberKnowledge

Xueqing YAN、Yongming LI、Sanjiang LI

展开 >

School of Computer Science,Shaanxi Normal University,Xi'an 710062,China

School of Mathematics and Statistics,Shaanxi Normal University,Xi'an 710062,China

Centre for Quantum Software and Information,Faculty of Engineering and Information Technology,University of Technology Sydney,NSW 2007,Australia

2024

电子学报(英文)

电子学报(英文)

CSTPCDEI
ISSN:1022-4653
年,卷(期):2024.33(6)