Vol.55 No (Nov. 2014) 1 Fig. 1 Proposed method [5] 4 [6] [7]

Transcription

1 Vol.55 No (Nov. 2014) 1,a) 1,b) 1,1,c) 2,2,d) 1,e) 1,f) , Realizing a Four-Player Computer Mahjong Program by Supervised Learning with Isolated Multi-Player Aspects Naoki Mizukami 1,a) Ryotaro Nakahari 1,b) Akira Ura 1,1,c) Makoto Miwa 2,2,d) Yoshimasa Tsuruoka 1,e) Takashi Chikayama 1,f) Received: November 4, 2011, Accepted: December 1, 2011 Abstract: This paper describes a supervised machine learning approach for building a mahjong program. We start with building a one-player mahjong program by Perceptron learning with game records of expert human players,and adapt it to four-player mahjong. The adaptation is achieved by incorporating the folding and calling functionalities that are separately learned from game records. We have evaluated the playing strength of the resulting program on a large online mahjong site Tenhou. The program has achieved a rating of 1651, which is considerably higher than that of the average human player. Keywords: Multi-player game, Mahjong, Supervised learning The University of Tokyo 2 The University of Manchester 1 Presently with Fujitsu Laboratories Ltd 2 Presently with Toyota Technological Institute a) mizukami@logos.t.u-tokyo.ac.jp b) nakahari@logos.t.u-tokyo.ac.jp c) ura@logos.t.u-tokyo.ac.jp d) makoto-miwa@toyota-ti.ac.jp e) tsuruoka@logos.t.u-tokyo.ac.jp f) chikayama@logos.t.u-tokyo.ac.jp [1], [2], [3] [4], [5], [6], [7] Texas Hold em 2 [8] 2 3 [4] c 2014 Information Processing Society of Japan 1

2 Vol.55 No (Nov. 2014) 1 Fig. 1 Proposed method [5] 4 [6] [7] c 2014 Information Processing Society of Japan 2

3 Vol.55 No (Nov. 2014) [4], [5] 2 [8] 2 3 [4] [5] 3 [6] 3 [7] [9] [10] 13% [1] TD [11] [12] 4.2 [13] x w n x i i w i i 1 n f (x, w) = x i w i (1) i= t ˆt t x t ˆt xˆt w 2 w = w + x t xˆt (2) [6] 1 37, [14] *1 * c 2014 Information Processing Society of Japan 3

4 Vol.55 No (Nov. 2014) = 36 4 n n=1 3 0 n 3 16 = = , = = = n n= = Table 1 Features for the one-player Mahjong player 0.1% [7] Plain UCT [14] 50% [14] 0.1% 2 [15] % Plain UCT Table 2 Winning rates in one-player Mahjong % [15] Table 3 Winning rates and average socres in 10,000 games *2 52% 48% * c 2014 Information Processing Society of Japan 4

5 Vol.55 No (Nov. 2014) Rank 1 Rank 2 Rank Table 4 Concordance rate 3 3 n Rank n [14] 27 1,342 1,342 4 Rank 1 62% 53% Rank 1 56% Rank 3 15% % 4 6% 6. 2 Fig. 2 Classification of errors 3 Fig. 3 A position in which the player folded ,716 A B 5,716 1,053 [14] 10% *2 c 2014 Information Processing Society of Japan 5

6 情報処理学会論文誌 Vol.55 No (Nov. 2014) 図 5 uti is difficult Fig. 4 A position in which the player Mawashi uti A/B 降り そうでない 表 5 降り そうでない タグ付一致数 降りか回し打ちか判断に困る局面 Fig. 5 A position in which judging whether to fold or Mawashi 図 4 回し打ちした局面 922 Table 5 Number of correct answers プレイヤによってさらに幅が大きく困難である また一度降りと判断した場合 定義により次からすべて 降りと判断するため 降りと回し打ちで判断が食い違った 場合 その次のツモ牌が安全牌であるとき片方は降り 片 方は降りてないと判断される このように一度判断を間違 えるとさらに間違いが引き起こされ一致率が低下する 両者のタグ付けの一致率を表 5 に示す 判断にはプレイ ヤの主観的な考え方が大きく作用するため 困難な問題で 6.2 降りるべき局面の認識 ある しかしながら一致率は一定の水準に達している 偶 本節では 降りる局面の認識を機械学習によって行う手 然によらない一致率の指標であるカッパ係数 [16] は 0.75 法を説明する まず局面からどのような特徴量を取り出し であり おおむね降りた局面とそうでない局面を当てられ たのか説明し 認識精度を評価する ているといえる 一致しなかった 48 の局面を見ると 回 本節の問題設定は 6.1 節での設定とは少し異なっている し打ち の局面が 47 あり 残りの 1 つは牌譜が明らかな 6.1 節で行ったのは牌譜で何を選んだかを見てその手が降 悪手を指した手であった りかどうかを判断した しかし実際には切る牌を選ぶ前に 回し打ちの具体的な例を図 4 に示す 他のプレイヤのこ 降りるかどうかを判断して その判断に基づいた手を選択 とを気にしなければ最善手は 8 索であるが 右のプレイヤ する必要がある したがって 6.1 節で行った問題とは異な のリーチに対応して現物である 1 索を切ったというような り 局面についての降りるかどうかを判断する分類問題と 局面である した また最善手ではないと判断できても それが降りなのか 降りかどうかを判断する局面の特徴量としては表 6 に示 回し打ちなのか判断するのが困難な局面もあった 図 5 は すものを取り出した 自分の状態と 3 人分の相手の状態と 二人の判断が分かれた局面である ここで牌譜では 2 萬を 場の状況を考慮する必要があるため 特徴ベクトルの要素 切った これをどう見るかであるが メンツを崩している 次元は である という点で A は降りと判断した しかし 見方を変えると この研究では問題を単純にするため 降り判断は以下の 2 萬や 6 萬は右のプレイヤのリーチに現物であり 4 萬は ようなモデルで行われていると考える 人間は降りるべき 筋で通りそうである これらを切っている間に残りの形が 局面かどうかを決定したときに周りを気にしないときの最 メンツになることや危険な牌がリーチ者が切るかもしれな 善手を選ぶ そしてこの牌が周りのプレイヤに対して安全 いため このプレイヤはまだ加点することを諦めていない かどうかを考慮して 降りるかどうかを判断している そ だろうという点で B は回し打ちと判断した のためこのモデルに必要な切りたい牌の周りのプレイヤに このように手が和了や流局時の聴牌を狙えるかどうか判 断するのはそのプレイヤの主観的な考え方が大きく作用す る とくに七対子で和了できる可能性をどの程度見るかは c 2014 Information Processing Society of Japan 対しての安全度を考える 安全度はヒューリスティクスにより決定した 安全度の 高い順に以下のようになっている 6

7 Vol.55 No (Nov. 2014) Table Table 6 Features for folding decisions F Result of classification of folding positions Gaussian Support Vector Machine SVM 5 SVM LIBSVM [17] cg ,185 7 F c = 2 8 g = 2 7 F 6 Fig. 6 Learning Curves , , c 2014 Information Processing Society of Japan 7

8 Vol.55 No (Nov. 2014) n = = = = = = = = = = = = 40 8 Table 8 Additional features about calling for the one-player Mahjong player 6,230 3,755 1, ,164 19,392 N\A Table 9 Accuracy rates of calling 1 [6] 21% [14] 5 10 c 2014 Information Processing Society of Japan 8

9 Vol.55 No (Nov. 2014) Table 10 Rank distribution 7 Fig. 7 Flowchart on the player s turn 8 Fig. 8 Flowchart on opponents turn [14] 4 R 3 R = R + (50 Rank 20 + AveR R ) 0.2 (3) 40 Rank AveR R R t 2 1% [12] c 2014 Information Processing Society of Japan 9

10 Vol.55 No (Nov. 2014) Table 11 Winning and Hoju rates % 1.7% [12] 9. [14] [1] Buro, M.: Logistello: A strong learning othello program, 19th Annual Conference Gesellschaft für Klassifikation ev, pp. 1 3 (1995). [2] Campbell, M., Hoane Jr, A. J. and Hsu, F.-h.: Deep blue, Artificial Intelligence, Vol. 134, No. 1, pp (2002). [3] 4 : GPS ( ) Vol. 51, No. 8, pp (2010). [4] Risk, N. A. and Szafron, D.: Using counterfactual regret minimization to create competitive multiplayer poker agents, Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, International Foundation for Autonomous Agents and Multiagent Systems, pp (2010). [5] Proceedings of the 17th Game Programming Workshop (2013). [6] Proceedings of the 12th Game Programming Workshop (2007). [7] (2010). [8] Bowling, M., Risk, N. A., Bard, N., Billings, D., Burch, N., Davidson, J., Hawkin, J., Holte, R., Johanson, M., Kan, M. et al.: A demonstration of the Polaris poker system, Proceedings of 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, pp (2009). [9] Kocsis, L. and Szepesvári, C.: Bandit based monte-carlo planning, Proceedings of the 17th European Conference c 2014 Information Processing Society of Japan 10

11 Vol.55 No (Nov. 2014) on Machine Learning, pp (2006). [10] mjman: [11] Sutton, R. S.: Learning to predict by the methods of temporal differences, Machine learning, Vol. 3, No. 1, pp (1988). [12]! (2009). [13] Collins, M.: Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms, Proceedings of the ACL-02 conference on Empirical methods in natural language processing- Volume 10, Association for Computational Linguistics, pp. 1 8 (2002). [14] (2014). [15]. GI,[] Vol. 2012, No. 8, pp. 1 8 (2012). [16] Series, S. C.: Measurement of observer agreement, Radiology, Vol. 228, pp (2003). [17] Chang, C.-C. and Lin, C.-J.: Libsvm, csie.ntu.edu.tw/~cjlin/libsvm/ (2001) AI ( ) ACL AI c 2014 Information Processing Society of Japan 11