Computing the Winner of 2-Player TANHINMIN

Hironori KIYA  Katsuki OHTO  Hirotaka ONO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E104-A    No.9    pp.1134-1141
Publication Date: 2021/09/01
Publicized: 2021/02/10
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2020DMP0026
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Algorithms and Data Structures
Keyword: 
combinatorial game,  winning strategy,  bipartite matching,  

Full Text: PDF(1.7MB)>>
Buy this Article



Summary: 
DAIHINMIN, which means Grand Pauper, is a popular playing-card game in Japan. TANHINMIN is a simplified variant of DAIHINMIN, which was proposed by Nishino in 2007 in order to investigate the mathematical properties of DAIHINMIN. In this paper, we consider a 2-player generalized TANHINMIN, where the deck size is arbitrary n. We present a linear-time algorithm that determines which player has a winning strategy after all cards are distributed to the players.