JISE


  [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]


Journal of Information Science and Engineering, Vol. 38 No. 4, pp. 775-790


Monte-Carlo Simulation for Mahjong


JR-CHANG CHEN1,+, SHIH-CHIEH TANG2 AND I-CHEN WU2,3
1Department of Computer Science and Information Engineering
National Taipei University
New Taipei City, 23741 Taiwan

2Department of Computer Science
National Yang Ming Chiao Tung University
Hsinchu, 30050 Taiwan

3Research Center for IT Innovation
Academia Sinica
Taipei, 11529 Taiwan
E-mail: jcchen@mail.ntpu.edu.tw; fight5566jay@gmail.com; icwu@cs.nctu.edu.tw


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.


Keywords: Monte-Carlo simulation, discard-twice method, imperfect information game, Mahjong, progressive pruning

  Retrieve PDF document (JISE_202204_05.pdf)