« 迷走中 | トップページ | バク修正中 »

2012/02/19

麻雀ゲームが弱い理由(書きかけ放置版)

先日、将棋界では、米長永世棋聖vsボンクラーズの対局が行われ、ボンクラーズの勝利でおわりました。このことは、各メディアでニュースとして取り上げられ、ネット上の電子掲示板などでも話題になっていたようです。その話題のなかで、他のゲームはどうなんだ、麻雀はどうなんだ、という話がでてきます。そういった場でよくでてくる話は大体こんな感じです。「麻雀は、イカサマが可能なのであまり真剣に思考ルーチンの研究開発がなされていない。金にならないから誰もやらない。だから弱い」のだと。まあこれも確かにその通りなのですが、麻雀は将棋とは違った難しさがあるのです。

まったり麻雀は、他のコンピュータ麻雀ソフトよりは頑張ってる方だと自負していますが、人間のトップクラスの人から見ればまだまだな部分も多いでしょう。

コンピュータ将棋は、全幅探索、後方枝刈り、棋譜をベースにした教師あり機械学習をセットとしたいわゆるボナンザメソッドで飛躍的に強くなりました。また囲碁ではモンテカルロ木探索の手法がパラダイムシフトを起こしていますが、これらの手法は麻雀ではうまくいかないのです。その理由を紹介したいと思います。

全幅探索では1巡先すら読めない

将棋は一般に1局面の合法手は平均80手程度とされています。将棋の場合、対局相手は1人ですので、自分が着手してから次に自分の手番が回ってくるまでの局面変化のパターンは80通りしかありません。これが、麻雀の場合、そうはいきません。麻雀は、ツモ(34通り)と打(最大14とおり)の2アクションがあり、相手は3人います。
手牌に同じ牌があったり、鳴いていて手牌が短くなったりしているので打の変化数を平均10として計算すると、自分が着手してからもう一度自分の番が回ってくるまでに鳴きを考慮に入れないとしても、(34*10)*(34*10)*(34*10)=39304000通りの局面変化があるわけです。米長永世棋聖と対局したボンクラーズは一秒間に1800万局面読むそうですが、そのマシンでも2秒以上かかってしまいます。
麻雀ゲームでは1秒考えたら遅くて使ってもらえないので、将棋と同じような全幅探索を麻雀ゲームでやろうとしたら、今のマシンでは、1巡先すら読むことが出来ないわけです。

もちろん、1巡先が1秒で読めるようになっても、2巡先が2秒で読めるわけではありません。2順目を読むのには、39304000秒かかるわけです

将棋で確立されているような簡単・正確・高速な後方枝狩り手法が無い

情報科学的には将棋や囲碁は2人零和完全情報確定交互ゲームに分類されますが、こういったゲームにはmin-max法が有効であることが分かっていますが、麻雀では……

と、途中まで書いたんですが、あまりにもいろいろある上に言い訳ばかり書いていても生産的でない気がしてきました。言い訳考えてブログ書いてる暇あるなら少しでもコード改良したほうがよいでしょう。開発作業に戻ります。ほかに書きたかった項目だけ列挙しときます。


囲碁で有効だとされているモンテカルロ木探索が使えない
=>囲碁は侵略ゲーム、麻雀は創造のゲーム。

評価関数や機械学習の問題
=> S/N比が悪くて、機械学習しにくい
=> 評価関数がおそらく線形では上手くいかない
=> そもそも評価値がスカラーではないかもしれない.
=> 攻防の妙手は存在しない

ヒューリスティックの問題
=>玉飛接近すべからずvs南白付き物のクオリティの差

人間との相対的な問題
=> 原理的には麻雀は難しいが、人間的には将棋の方が難しい


追記:麻雀でガチのアルゴリズムをつくっていて、その難しさについて、囲碁や将棋と比較して語る人がいないようなので、続き読みたい人いれば、書くかも。

|

« 迷走中 | トップページ | バク修正中 »

コメント

すごく興味があります。是非続けてくださると嬉しいです。
あとプログラム試してみますね

投稿: 通りすがり | 2012/02/19 17:04

上手い事いけば春から情報系の学科なんで聞きたいです(*´ω`*)

投稿: レバニラ | 2012/02/19 19:15

是非続編をお願いします。

投稿: ph | 2012/02/20 00:09

非常に興味深く、目からウロコです。続編希望です。

投稿: | 2012/02/20 13:09

是非続きを読んでみたいです。

投稿: SST | 2012/02/20 21:14

麻雀でボナンザメソッドの試みはやった人もいるみたいですね。
ここのブログが参考文献にあがっている。

麻雀の牌譜からの打ち手評価関数の学習
http://www.logos.ic.i.u-tokyo.ac.jp/~kitagawa/papers/gpw07.pdf

投稿: gai | 2012/02/20 21:57

割と読みたい人が多そうなので、書いてみます。期待に添える内容になるか、いつ書くかは全く不明ですが。

投稿: kmo2 | 2012/02/20 22:04

>麻雀でボナンザメソッドの試みはやった人もいるみたいですね
その文献はしってます。そしてそのやり方ではなぜダメなのかもできれば書いてみたいですね。

投稿: kmo2 | 2012/02/20 22:05

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/61182/54020688

この記事へのトラックバック一覧です: 麻雀ゲームが弱い理由(書きかけ放置版) :

» 麻雀ゲームが弱い理由(と羽生2冠が強い理由)~読みと見切り編~ [マッタリプログラミング日誌]
先日の記事が割と評判が良かったようなので、続きを書いてみたいと思います。 前回は [続きを読む]

受信: 2012/03/10 10:43

« 迷走中 | トップページ | バク修正中 »