http://swrc.ontoware.org/ontology#Article
Modeling Imperfect Information TANHINMIN with Structural Oracle
en
[オリジナル論文] imperfect information game, oracle based algorithm, TANHINMIN, winning strategy
Faculty of Economics, Kyushu University
Department of Mathematical Informatics, Nagoya University
Hironori Kiya
Katsuki Ohto
Hirotaka Ono
TANHINMIN is a simplified and perfect information variant of DAIHINMIN, which is major playing card game in Japan. It can be decided in linear time which player has a winning strategy in 2-player TANHINMIN. This paper is concerned with how we obtain a winning strategy for the imperfect information variant of TANHINMIN. If any information about the opponent player's hand is not given at all, it is obviously difficult or impossible to find a winning strategy, though such a hard situation does not likely happen in real game plays; players usually receive some little information about the opponent player's hand through a game such as the number of cards. To handle the situation that a player can receive some information about the opponent player's hand, we introduce an oracle model in which the oracle provides partial information about the opponent's hand. Interestingly, when players can get partial information of the opponents' hands via oracle, the winning player can find a winning strategy as if it is the (perfect information) TANHINMIN. Furthermore, we show various results about other relationships between the power of oracles and the existence of a computable winning strategy.
TANHINMIN is a simplified and perfect information variant of DAIHINMIN, which is major playing card game in Japan. It can be decided in linear time which player has a winning strategy in 2-player TANHINMIN. This paper is concerned with how we obtain a winning strategy for the imperfect information variant of TANHINMIN. If any information about the opponent player's hand is not given at all, it is obviously difficult or impossible to find a winning strategy, though such a hard situation does not likely happen in real game plays; players usually receive some little information about the opponent player's hand through a game such as the number of cards. To handle the situation that a player can receive some information about the opponent player's hand, we introduce an oracle model in which the oracle provides partial information about the opponent's hand. Interestingly, when players can get partial information of the opponents' hands via oracle, the winning player can find a winning strategy as if it is the (perfect information) TANHINMIN. Furthermore, we show various results about other relationships between the power of oracles and the existence of a computable winning strategy.
AA11464803
情報処理学会論文誌数理モデル化と応用（TOM）
15
1
10-17
2022-01-31
1882-7780