Searching Optimal Movements in Mahjong Using Tabu Search

IPSJ

Bibliographic Information

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

Description

近年，将棋やオセロといった2人零和確定完全情報ゲームにおいて，トップ層の人間と同等の実力を持つプレイヤが実現されている．しかし，ポーカーや麻雀といった不確定不完全情報ゲームでは，そのようなプレイヤを実現することは難しい．本論文は4人零和不確定不完全情報ゲームである麻雀を取り上げる．そこで，本論文では，トップ層の人間に勝る麻雀プレイヤを実現するために，多人数不完全情報ゲームにおける最適行動の探索を検討する．ここでは，トップ層の人間の牌譜の知識を用いず，シミュレーションによって最適解の探索を行うタブーサーチを用いる手法を提案する．タブーサーチを適用するのは，打牌選択の局面と鳴きの局面である．提案手法を実現し，一致率実験とベンチマークプレイヤとの対局実験を行った．一致率実験によって，序盤の局面に対して，有効な和了形を最大$85\%$で見つけることができ，さらに，対局実験によって，提案手法がベンチマークプレイヤよりも優れているという結果が得られた．これらの結果から，タブーサーチによる最適解の探索が有効である可能性を示した．

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.

Journal

Details 詳細情報について

Report a problem

Back to top