Monte-Carlo Simulation for Mahjong

被引：4

作者：

Chen, Jr-Chang ^{[1
]}

Tang, Shih-Chieh ^{[2
]}

Wu, I-Chen ^{[2
,3
]}

机构：

[1] Natl Taipei Univ, Dept Comp Sci & Informat Engn, New Taipei 23741, Taiwan

[2] Natl Yang Ming Chiao Tung Univ, Dept Comp Sci, Hsinchu 30050, Taiwan

[3] Acad Sinica, Res Ctr IT Innovat, Taipei 11529, Taiwan

来源：

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING | 2022年 / 38卷 / 04期

关键词：

Monte-Carlo simulation; discard-twice method; imperfect information game; Mahjong; progressive pruning;

D O I：

10.6688/JISE.202207_38(4).0005

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Mahjong is a four-player, stochastic, imperfect information game. This paper focuses on the Taiwanese variant of Mahjong, whose complexity is higher than that of Go. We design a strong anytime Monte-Carlo-based Taiwanese Mahjong program. First, we adopt the flat Monte Carlo to calculate the win rates of all afterstates/actions such as discarding each tile. Then, we propose a heuristic method, which we incorporate into flat Monte Carlo to obtain the accurate tile to be discarded. As an anytime algorithm, we can stop simulations and return the current best move at any time. In addition, we prune bad actions to increase accuracy and efficiency. Our program, SIMCAT, won the championship in the Mahjong tournaments in Computer Olympiad 2020 and TAAI 2019/2020.

引用

页码：775 / 790

页数：16

共 25 条

[1]

[Anonymous], MATH MAHJONG

[2]

[Anonymous], JAPAN MAHJONG PROFES

[3]

[Anonymous], MAHJONG TIME ONLINE

[4]

Bouzy B, 2004, INT FED INFO PROC, V135, P159

[5]

Bouzy B, 2006, LECT NOTES COMPUT SC, V4250, P104

[6] A Survey of Monte Carlo Tree Search Methods [J].

Browne, Cameron B. ;

Powley, Edward ;

Whitehouse, Daniel ;

Lucas, Simon M. ;

Cowling, Peter I. ;

Rohlfshagen, Philipp ;

Tavener, Stephen ;

Perez, Diego ;

Samothrakis, Spyridon ;

Colton, Simon .

IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, 2012, 4 (01) :1-43

[7]

Chaslot Guillaume, 2006, P 18 BENELUX C ART I, P83

[8]

Chuang L. -K., 2015, Master's thesis

[9]

Coulom R, 2007, LECT NOTES COMPUT SC, V4630, P72

[10]

Edwards D. J., 1963, ALPHA BETA HEURISTI

← 1 2 3 →