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

YAN Xueqing; LI Yongming; LI Sanjiang

doi:10.23919/cje.2022.00.259

Article Contents

Article Navigation > Chinese Journal of Electronics > 2024 > Uncorrected proof

Xueqing YAN, Yongming LI, and Sanjiang LI, “A Fast Algorithm for Computing the Deficiency Number of a Mahjong Hand,” Chinese Journal of Electronics, vol. 33, no. 6, pp. 1–16, 2024 doi: 10.23919/cje.2022.00.259

Citation:

Xueqing YAN, Yongming LI, and Sanjiang LI, “A Fast Algorithm for Computing the Deficiency Number of a Mahjong Hand,” Chinese Journal of Electronics, vol. 33, no. 6, pp. 1–16, 2024 doi: 10.23919/cje.2022.00.259

Citation:

PDF( 7279 KB)

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

doi: 10.23919/cje.2022.00.259

YAN Xueqing^{1
,
,},
LI Yongming^2
,,
LI Sanjiang^3
,

1.
School of Computer Science, Shaanxi Normal University, Xi'an, Shaanxi 710062, China
2.
School of Mathematics and Statistics, Shaanxi Normal University, Xi'an, Shaanxi 710062, China
3.
Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, University of Technology Sydney, NSW 2007, Australia

More Information

Author Bio:
Xueqing YAN received the B.S. degree in Mathematics and Applied Mathematics from Datong University, Shanxi, China in 2010, and the M.S. degree in Operations Research and cybernetics from Shaanxi Normal University, Shaanxi, China, in 2017. She is currently pursuing the Ph.D. degree in Quantum Information with Shaanxi Normal University, Shaanxi, China. Her current research interests include intelligent computing, AI Mahjong system, and intelligent optimization. (Email: xueqingyan@snnu.edu.cn.)

Yongming LI received the Ph.D. degree in Mathematics from Sichuan University, Chengdu, China, in 1996. He is currently with Shaanxi Normal University, Xi'an, China, as a Professor of mathematics and computer science. His research interests include model checking, fuzzy control theory, fuzzy automata theory, spatial reasoning, quantum logic and quantum computation, and topology over lattices. (Email: liyongm@snnu.edu.cn.)

Sanjiang LI received his B.S. and Ph.D. degrees in Mathematics from Shaanxi Normal University, in 1996, and Sichuan University, in 2001, respectively. He is a professor in Centre for Quantum Software and Information, University of Technology Sydney (UTS). Before joining UTS, he worked in the Department of Computer Science and Technology, Tsinghua University from 2001 to 2008. His research interests are mainly in knowledge representation and artificial intelligence. (Email: Sanjiang.Li@uts.edu.au)
Corresponding author: Email: xueqingyan@snnu.edu.cn
Received Date: 2022-08-02
Accepted Date: 2024-01-03

Available Online: 2024-04-04

Abstract

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.
- Mahjong,
- Deficiency number,
- Knowledge

https://botzone.org.cn/static/gamecontest2020a.html

2There are possibly other kinds of winning hands in different Mahjong variants, but this is the most typical one.
3For ease of presentation, we don’t regard a hand with seven pairs as complete.
4It is possible that $ R $ contains a pair $ (t,t) $, we don’t regard the cost to create the eye as 0. This is because the deficiency is determined by considering all ${{\sf{qDCMP}}} $s and $ (t,t) $ appears in some other ${{\sf{qDCMP}}} $ $ \pi' $ that is finer than $ \pi $ and has a smaller cost.
5Here a statement '$ B $ if $ A $' is equivalent to saying '$ A\Rightarrow B $' or '(not $ A $) or $ B $'.

FullText(HTML)

References(23)

References

[1]	A. L. Samuel, “Some studies in machine learning using the game of checkers,” IBM Journal of Research and Development, vol. 3, no. 3 pp. 210–229, 1959. doi: 10.1147/rd.33.0210
[2]	C. E. Shannon, “Programming a computer for playing chess,” in Computer Chess Compendium, D. Levy, Ed. Springer, New York, NY, USA, 1988.
[3]	D. Silver, A. Huang, C. J. Maddison, et al., “Mastering the game of Go with deep neural networks and tree search,” Nature, vol. 529, no. 7587 pp. 484–489, 2016. doi: 10.1038/nature16961
[4]	M. Bowling, N. Burch, M. Johanson, et al., “Heads-up limit hold’em poker is solved,” Science, vol. 347, no. 6218 pp. 145–149, 2015. doi: 10.1126/science.1259433
[5]	N. Brown and T. Sandholm, “Safe and nested subgame solving for imperfect-information games,” in Proceedings of the 31st International Conference on Neural Information Processing Systems, Long Beach, CA, USA, pp. 689–699, 2017.
[6]	Q. Q. Jiang, K. Z. Li, B. Y. Du, et al., “DeltaDou: Expert-level doudizhu AI through self-play,” in Proceedings of the 28th International Joint Conference on Artificial Intelligence, Macao, China, pp. 1265–1271, 2019.
[7]	J. J. Li, S. Koyamada, Q. W. Ye, et al., “Suphx: Mastering mahjong with deep reinforcement learning,” arXiv preprint, arXiv: 2003.13590, 2020.
[8]	Wikipedia, “Mahjong,” Available at: https://en.wikipedia. org/wiki/Mahjong, 2021-12-12.
[9]	N. Mizukami and Y. Tsuruoka, “Building a computer mahjong player based on Monte Carlo simulation and opponent models,” in Proceedings of 2015 IEEE Conference on Computational Intelligence and Games, Tainan, China, pp. 275–283, 2015.
[10]	K. Yoshimura, T. Hochin, and H. Nomiya, “Searching optimal movements in multi-player games with imperfect information,” in Proceedings of the IEEE/ACIS 15th International Conference on Computer and Information Science, Okayama, Japan, pp. 1–6, 2016.
[11]	M. Kurita and K. Hoki, “Method for constructing artificial intelligence player with abstractions to Markov decision processes in multiplayer game of mahjong,” IEEE Transactions on Games, vol. 13, no. 1 pp. 99–110, 2021. doi: 10.1109/TG.2020.3036471
[12]	M. Y. Wang, T. W. Yan, M. Y. Luo, et al., “A novel deep residual network-based incomplete information competition strategy for four-players mahjong games,” Multimedia Tools and Applications, vol. 78, no. 16 pp. 23443–23467, 2019. doi: 10.1007/s11042-019-7682-5
[13]	S. J. Gao and S. Q. Li, “Bloody mahjong playing strategy based on the integration of deep learning and XGBoost,” CAAI Transactions on Intelligence Technology, vol. 7, no. 1 pp. 95–106, 2022. doi: 10.1049/cit2.12031
[14]	Y. J. Zheng, S. Q. Li, and L. Z. Zheng, “Design and implementation of a deep learning-based decision system for Xuezhan mahjong,” in Proceedings of the 34th Chinese Control and Decision Conference, Hefei, China, pp. 3505–3511, 2022.
[15]	H. H. Chen and K. C. Huang, “An empirical evaluation of applying deep reinforcement learning to Taiwanese mahjong programs,” in Proceedings of the 9th International Conference on Applied System Innovation, Chiba, Japan, pp. 142–144, 2023.
[16]	X. L. Li, Z. Q. Wang, and L. Wu, “A survey of researches on mahjong AI,” CAAI Transactions on Intelligent Systems, in press, 2023. (查阅网上资料, 未找到本条文献信息, 请确认) .
[17]	S. J. Li and X. Q. Yan, “Let’s play mahjong!, ” arXiv preprint, arXiv: 1903.03294, 2019.
[18]	Stack Overflow, “How do I calculate the shanten number in mahjong?”, Available at: https://stackoverflow.com/questions/4239028/how-do-i-calculate-the-shanten-number-in-mahjong, 2022-04-23.
[19]	Wikipedia, “Shanten,” Available at: https://riichi.wiki/Shanten, 2021-12-15. (查阅网上资料, 请核对作者信息) .
[20]	Q. C. Wang, Y. M. Li, and X. Y. Chen, “A mahjong-strategy based on weighted restarting automata,” in Proceedings of the 2020 3rd International Conference on Machine Learning and Machine Intelligence, Hangzhou, China, pp. 117–121, 2020.
[21]	Q. C. Wang, Y. Zhou, D. Y. Zhu, et al., “A new approach to compute deficiency number of Mahjong configurations,” Entertainment Computing, vol. 43, article no. 100509, 2022. doi: 10.1016/j.entcom.2022.100509
[22]	X. Q. Yan and Y. M. Li, “A novel discrete differential evolution with varying variables for the deficiency number of mahjong hand,” Mathematics, vol. 11, no. 9, article no. 2135, 2023. doi: 10.3390/math11092135
[23]	X. C. Zhang, L. Liu, C. Y. Gan, et al., “Research on mahjong game strategy combining hand tiles optimization and situation search,” in Proceedings of the 34th Chinese Control and Decision Conference, Hefei, China, pp. 4236–4240, 2022.