不完全情報二人単貧民分析のためのオラクルモデル

• Item type: Symposium(1)
• 公開日: 2019-11-01
• タイトル: 不完全情報二人単貧民分析のためのオラクルモデル
• タイトル / 言語: en
• タイトル: Oracle Models for analyzing imperfect information two-player TANHINMIN
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 名古屋大学大学院情報学研究科 数理情報学専攻
• 著者所属(英): en
• 著者所属(英): Department of athematical Informatics, Graduate School of Informatics, Nagoya University
• 著者名: 木谷, 裕紀; 大渡 勝己; 小野 廣隆
• 著者名(英): Kiya, Hironori; Ohto, Katsuki; Ono, Hirotaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 単貧民とは，不完全情報多人数ゲームである大貧民を完全情報ゲームとして簡易化したものである．これまでの研究により，二人単貧民に関しては配られた手札からどちらが必勝プレイヤであるかどうかを線形時間で判定できることがわかっている．本研究では手札非公開で行う不完全情報単貧民において如何に「必勝戦略」を得るかについて考える．手札に関する情報が全くない場合，確定的な意味で「必勝戦略」を得ることは難しい．このため，本研究では相手の手札に関する部分的な情報を提供するオラクルの存在を許したモデルを定義し，そのオラクル存在下で必勝戦略が得られるかどうかについて考察する．相手がどの札を持っているかなどの情報がない状況でも，マッチング数と呼ばれるゲームの構造パラメータを得るオラクルさえあれば完全情報単貧民と同様の必勝戦略をとることができるなど，オラクルの強さと必勝戦略発見可能性に関する様々な結果が得られることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: TANHINMIN is a simplified and perfect information variant of DAIHINMIN game, which is ma-jor playing card game in Japan. We know that it can be decided in linear time which player has a winning strategy in 2-player TANHINMIN game. This study is concerned with how we obtain a “winning strategy” for imperfect information variant of TANHINMIN game. If any information about the opponent player’s hand is not given at all, it is obviously difficult 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, e.g., 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 infor-mation about the opponent’s hand. Interestingly, if the oracle provides only some structural information about the game with no information about opponent player’s cards themselves, 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.
• 書誌情報: ゲームプログラミングワークショップ2019論文集; 巻 2019, p. 258-265, 発行日 2019-11-01
• 出版者 / 言語: ja
• 出版者: 情報処理学会