タブーサーチを用いた麻雀における最適行動の探索

• Item type: Symposium(1)
• 公開日: 2016-10-28
• タイトル: タブーサーチを用いた麻雀における最適行動の探索
• タイトル / 言語: en
• タイトル: Searching Optimal Movements in Mahjong Using Tabu Search
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 京都工芸繊維大学大学院情報工学専攻
• 著者所属: 京都工芸繊維大学情報工学・人間科学系
• 著者所属: 京都工芸繊維大学情報工学・人間科学系
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Kyoto Institute of Technology
• 著者所属(英): en
• 著者所属(英): Information and Human Sciences, Kyoto Institute of Technology
• 著者所属(英): en
• 著者所属(英): Information and Human Sciences, Kyoto Institute of Technology
• 著者名: 吉村, 健志; 宝珍, 輝尚; 野宮, 浩揮
• 著者名(英): Kenshi, Yoshimura; Teruhisa, Hochin; Hiroki, Nomiya
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，将棋やオセロといった2人零和確定完全情報ゲームにおいて，トップ層の人間と同等の実力を持つプレイヤが実現されている．しかし，ポーカーや麻雀といった不確定不完全情報ゲームでは，そのようなプレイヤを実現することは難しい．本論文は4人零和不確定不完全情報ゲームである麻雀を取り上げる．そこで，本論文では，トップ層の人間に勝る麻雀プレイヤを実現するために，多人数不完全情報ゲームにおける最適行動の探索を検討する．ここでは，トップ層の人間の牌譜の知識を用いず，シミュレーションによって最適解の探索を行うタブーサーチを用いる手法を提案する．タブーサーチを適用するのは，打牌選択の局面と鳴きの局面である．提案手法を実現し，一致率実験とベンチマークプレイヤとの対局実験を行った．一致率実験によって，序盤の局面に対して，有効な和了形を最大$85\%$で見つけることができ，さらに，対局実験によって，提案手法がベンチマークプレイヤよりも優れているという結果が得られた．これらの結果から，タブーサーチによる最適解の探索が有効である可能性を示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a search method of optimal movements in multi-player games with imperfect information in order to implement a Mahjong player exceeding human top players. The proposed method uses tabu search. It does not use the record of a game. Tabu search is applied to the states of discarding tiles and using the tile that other players discarded. The experiments were carried out in order to evaluate the proposed method. In the experiment of evaluating the rate of concordance of the usage of tiles, the maximum rate of concordance reached to 85\%. This means effective winning hands could be found in the initial states. In the experiment of playing a game with benchmark players, it is shown that the proposed method is better than benchmark players. From these results, the possibility of the effective search of optimal solution by using tabu search was indicated.
• 書誌情報: ゲームプログラミングワークショップ2016論文集; 巻 2016, p. 73-80, 発行日 2016-10-28
• 出版者 / 言語: ja
• 出版者: 情報処理学会