麻雀プログラム 思った事

 

麻雀プログラム 思った事

戻る
UECda 2010 -UECコンピュータ大貧民大会- 大貧民AIの大会でモンテカルロ法のAIが圧勝2連覇したらしい。 アルゴリズムは 1.全ての合法手を列挙 2.相手の手を確率に基づき仮定 3.実際に終局までランダムに打たせる(これをプレイアウトと言う) 4.結果(順位)を得点とする 5.2~4を十分回こなした後、最も平均得点が高い合法手を選択する しかし本当にランダムに打つ「原子モンテカルロ」だと弱いAIになる事が知られているので、UCB1やUCTという方法を使い高精度化する。  (参考)「コンピュータ囲碁におけるモンテカルロ法」(理論編) 麻雀も大貧民と同じ多人数不完全情報ゲームだからこの手法が有効かもしれない。というか似た事を先にやった人がいる。 多人数不完全情報ゲームにおける. 最適行動決定に関する研究(PDF) 当たり前かもしれないが、単純にモンテカルロしてもうまくいかないようだ。おまけに、報酬をどうするかがまた問題らしい。 囲碁はランダムに打とうが勝ち負けが決まるが、麻雀は一般的に「最終順位」を競うゲームなので、局単位の点数増減を報酬にしても良い結果が得られない。 (追記)報酬にはとつげき東北氏のこれ(MJSIM-3)が使えるかも (ミラー) または科学する麻雀の点数状況判断理論など またこの論文の人の研究室で評価関数の機械学習も扱っているが、研究不足、適切な静的評価要素(囲碁よりは簡単だが)を作る事が難しいゲームなため、なかなか結果が出ないようだ。 UECdaのHPに知識をひたすら入力していくKIDSというシステムも紹介されていたが、 しかし職人芸で評価関数を長年手造りでしこしこ作ったGnuGoがモンテカルロ法にあっさり抜かれたのだから 大局観を再現するルールベースな方法は、やっぱ厳しいんだろうなあ。麻雀でも。
ゲームを解く事とはゲーム木を読み解くことに他ならない。つまり麻雀のゲーム木ができれば「最強の麻雀AI」ができる。 しかし多人数ゲームや不完全情報ゲームのゲーム木を作る事は非常に難しいし、ポンチーなどで順序が一定でない麻雀のゲーム木を作る事はさらに難しい。 麻雀には複数の評価関数が必要だが、麻雀そのものについて研究不足なため適切な評価要素がわかっていない。 そのためどこかの教授がニューラルネットで評価関数を作ったが結果がでなかった。 麻雀が研究されない理由に「麻雀は実力のゲームではない」という意識と麻雀の社会的地位の低さがある。 麻雀は実力のゲームというのはとつげき東北氏が明らかにしたし、プロの努力で社会的地位も少しずつあがってきてはいる。 しかし世間一般にはまだまだ浸透していない。 現状は統計データや経験則を根拠としたルールベースなAI(ああすればこうする、というルールを大量に記述する素朴な方法)が最も作りやすいと思うが 限界が有るのは明らか。人間が無意識に思考している事、大局観をコンピュータに落とし込む事は困難。 今は麻雀AIの黎明期だ。従来のAI開発方法がさして有効でなく"不必要に"複雑な麻雀において 初めて客観的に見て最強の麻雀AIを作った人物は「無駄な事に全力を尽くした天才」として、誇らしげに死んで良いと思う。残念ながら金にも名誉にもならないが。
(殴り書き) 麻雀AIを作るとき、モンテカルロ法や探索は局面の数が将棋の比ではない膨大な数になってしまうので無理かも。 現実的な速度で答えるなら、現状では1手読みの評価関数で評価するしかない? 評価関数は Σ(特徴要素×重み) であらわされる、有利さを表す数値。 現在、重みを自動で求めるためにSVMやニューラルネットという手法が使われているが 理想は特徴要素も自動で求めた方がよい。 オセロは単純な3×3パターンを大量に特徴要素としているAIもあるが、麻雀はそうもいかない? 勉強しよう。
発想を変えて、当たり牌の一点読みをする麻雀AIなんてどうだろう?(もちろんイカサマなしで) もし当たり牌がわかれば降りる必要がなくなるので放銃率もあがり率も格段にあがるだろう。 これとかモンテカルロ法で結構いい精度出してるようだ。 人と対戦するなら全く面白くないゲームになるが、強いか弱いかと聞かれたら間違いなく強いだろう。やってみようかな? あ、駄目だ原理的に一点読みなんてできないか。うーん・・・
強い麻雀AをI作りたくて実は一人でこっそり色々試しているが、 一人麻雀は完全情報に近いので既存の探索を応用したもので何とかなりそうだけど 四人麻雀で戦略的な打ち方とかフーロの技術とかをしたい場合はしっかりゲーム木を読まないとダメだけど、そう考えるとやっぱり現状で出来る合理的な方法はモンテカルロ的な方法しか思いつかないなあ。 しかし大きな問題がいくつもあって、例えば ・探索空間が大きすぎる 四人麻雀のゲーム木をまじめに作ろうとすると、見えてない牌の全組み合わせについて探索する事になり、探索数が囲碁どころの話ではない天文学的な数字になる。 ・プレイアウトの質 モンテカルロ法はつまり 「各ノードについてゲーム木を末端までランダムに下って報酬を受取り、最も良かったものを調べる」 という方法だけど、本当にランダムに下ると現実的はありえないノードも見る事になって実用的な評価値を得ることができない。 じゃあプレイアウトする時に評価関数を使えばいいよね、となると最初から評価関数だけでいいのでは?という議論も出てくる。 ・麻雀プログラミングの大変さ 麻雀はとても複雑なので「まともに動くもの」を作るだけでも一苦労である。 ちょっと実験をしたいと思っても、事前準備のプログラミングにかなり時間がさかれる。(まあこれは本質的な課題ではないけど・・・) しかし現状、他に良い案がないっぽいのでどうにかしてこの課題を解決したいなあ。出来るか知らないけど。  
麻雀にUCT(モンテカルロ)はだめだな多分。トランプと違って適当に打ってたら終わらないゲームだし。
・相手を全く考慮しない一人麻雀なら最適な一打を求めることは可能だな多分。まずそれを作って、それを4人に拡張みたいな流れで作ればいいのかも。 ・囲碁もUCT以前は機械学習で作ったAIあったけど、いまいちだったらしい。でもボナンザは成功している。 機械学習は、いかに特徴ベクトルをとるかってのが重要っぽい。自動化する方法とかないのかなあ?
・しぐま0に勝てない・・・何でや・・・ ・数百試合まうじゃんで対局させる方法は時間がかかって効率悪すぎる。 やっぱ自分でデュプリケート対戦できるシミュレータ作ってやった方がいい。 マッタリプログラミング日誌 デュプリケート麻雀実現の問題点 http://kmo2.cocolog-nifty.com/prog/2008/02/post_4ccf.html ・v0.2作ってるけどなかなかうまくいかないなあ。良い結果出たらレポート書きます。
http://totutohoku.b23.coreserver.jp/hp/mjcom.htm の「02/02/11」の文より ”驚くのは、「こういう判断を入れればより良くなるだろう」と思って導入する判断のかなり多くの部分が、和了率を逆に下げるという「無駄」に終わるということだ。” 実際にAI作ってみると本当これに悩まされる。例えば放銃率が高いからとりあえず放銃率を2倍にしてみると、前より劇的に弱くなったり。 さらに引用 ”麻雀にはたくさんの技術要素があるが、重要なのはそのうちごく一部であり、重要な技術の差が成績の差になるということだ。” 例えば残り枚数を考慮してもしなくても、成績にほぼ影響がなかったなど。 じゃあ残り枚数を考慮しなくてもいいのかというと、そういうわけではなく 「成績に大きく影響する、本当に改善すべき要素は他にある」という事。を、実際AI作りしてると実感する。 てか、このリンクの文はとつげきさんが大学生時代のものか。 やっぱみんな麻雀AIを作ってみたい → 一部のやる気ある人が実際作る → どうすれば強くなるかわからず頓挫 → フェードアウト っていうパターン、あるあるっぽいですね。 そして、未だにしぐま0に勝てない(笑)どうすれば強くなるのか。ワカンネー。ワカンネー。 ・システム時計ストップフリーソフト http://www.vector.co.jp/soft/win95/personal/se319372.html
ダメだな。全部作り直し。
牌効率だなー麻雀で一番大事なの牌効率だわ。技術要素で牌効率が占める割合がものすごく高い。もし他の技術がどんなに良くても牌効率がダメだと弱い。改めて気づいた。
牌譜を用いた対戦相手のモデル化とモンテカルロ法によるコンピュータ麻雀プレイヤの構築 https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=106497&item_no=1&page_id=13&block_id=8 R1681!
https://github.com/gimite/mjai-manue をc++に移植してまうじゃんで打たせてみた が、あんまり強くない・・・ 相手のテンパイ率とかを統計値をそのまま使って算出しているが、多分これがあまりよくない。 相手の捨てパイとかからちゃんと計算しないとだめっぽい。 しっかしこんなにできないもんかね・・・強いマージャンAI・・・
やっとアカギに勝てた


早く収束させるため一発、裏ドラ無しルール 内容はmanueクローン+ヒューリスティック 長かった(笑) いちろん、しぐま1.02、アカギ、Occamで東風戦させてみる

試合数少ないけど、アカギには勝ってる模様。 なるうらとさん作のACORNSを使って「しぐまv1.02」と対戦させてみる(詳しくは「じどうでまーじゃん」で検索)

※クリックで拡大
しぐまには勝っていない模様。 次はネットで打たせるか。でも東風荘はもう人が少なすぎるし、けど天鳳とのIF作るの大変だな、、、


※クリックで拡大
(東風戦) チートイ狙いを結構抑えたら少し強くなった

※クリックで拡大
東南戦 東南戦だと弱くなる謎現象
・うーんどれだけパラメータとか変えてもしぐま0に勝てないっすねえ、、もうよくわかんないっすねえ、、 中身はgimite氏作のmanueをC++で書きなおして手動でマズイとこ直した版 みたいな感じの奴なんだけどダメっぽいっすねえ、、、 勝手に使って貰わせておいて何だけど、manueは相手テンパイ率とかのパラメータを鳳凰卓牌譜からとってるんだけど、ちゃんと卓の状況を入力にして推定しないとあかんって事すかねえ、、 んで結局没 Occam0.3→manueクローン→没 Occam0.2→ヒューリスティックその2→没 Occam0.1→ヒューリスティックその1→没 Oh・・・ ・もし麻雀AI作る人いたら、まうじゃんは正直おすすめ出来ない。牌譜無いし。DLLだからデバッグしづらいし。 あと何より自動打ちができちゃうので、適当にパラメータ変えて放置→ダメみたいなループに陥る可能性があります(俺みたいに)。 超面倒くさいのは分かるが、ちゃんと牌譜見れる環境作って、打ち方見てログ出してどこが変化みないと強くならないですね(ねえ俺)。 ・テスト大事。統計的検定超大事。麻雀AI作るなら、強さの評価をちゃんと統計的な方法でサボらずしっかりしないと絶対強くならない(ねえ俺)。 ・爆打は神。マジで神。2015/10/15時点でR1950くらい? これ前代未聞ですよ、事件ですよ奥さん。 ぜひどこかのゲームメーカーとかは爆打っていうか神打を大金出して買う位の価値ありますよ。作者の神上神紀氏を超高待遇で招いたほうがいい。 だって民間企業にこんなに強い麻雀AI作れる人なんて皆無に等しいんだから。こんな人材超超超レアですよ。SSSSSSSR位のレア。 とりあえずGPW2015を楽しみに待とう。そんでパクろう(嘘です嘘です) ・ちなみに強いと言われていたまったり麻雀のレートは1600後半くらいっぽい。 http://www.logos.ic.i.u-tokyo.ac.jp/~mizukami/slide/cig_slide2015.pdf ←これは爆打がR1700位の時のスライドで、有意差は無いけどまったり麻雀に勝ち越している。 0.02位の勝ちだから、0.1位がR100なら1680位になるのか。 で、ちょっとまったり麻雀と対戦するIFを作ってみて100戦位してみたんだけど、まったり麻雀よりOccamは全然弱そう。0.1位くらいの差がある。だからOccamは1500台しかなさそう。 ・こういうの作れちゃう人かっこいい http://critter.sakura.ne.jp/jun_keisan.html 麻雀AIやるなら、エンジニアの素養(プログラム能力)よりも研究者の素養(数学とか)のほうがいるっぽいなあ。敷居Highやなあ。 でもこの論文きっかけでロジスティック回帰勉強になりました、ありがとうございませた。 ・ボナンザ作った保木さんが書いた論文(2015年3月頃) http://entcog.c.ooco.jp/entcog/contents/symposium/date/2015/3-3-p.pdf まあいま話題の深層学習的な発想ですよね。特徴ベクトルすら人手で設計しない、究極のAI。 ただやっぱ難しそうですね。深層学習て、結局Googleの猫画像認識以外は大した成果出てないようですし。 でも究極的にはこんな感じが理想なんだろうな。超理想。素敵。でも最高にむずそう。取り組んだらそれだけで人生終わっちゃいそう。でも素敵。 ・てか天鳳はAI用のAPI作ってえ、、自前でIF作るのは超絶だるい、、
manueにひとりまーじゃん打たせたら上がり率19%もないですやーんて事はそもそもモンテカルロ法だめですやーん ↓ いやちょっと待ってちょっとプログラムいじったら上がり率21%超えた。やっぱmanueて神だわ(テノヒラクルッ) でもmanueはプログラム的な完成度高いよなあ。プログラム的に凄いと思う。
クソザコAIオッカム君v0.3.dll(まうじゃんdll) まうじゃんdll「アカギ」より強いですがアカギより10倍遅いです しぐま0より0.5位程弱いです クソザコAIオッカム君v0.31.dll(まうじゃんdll) しぐま0とほぼ同等ですが多分弱いです。10000試合やっても有意差ついてない・・・ 相手予想テンパイ率が閾値を超えていない限りノーテンとみなすみたいな事やったら強くなった
クソザコAIオッカム君v0.33.dll(まうじゃんdll) ACORNS成績(xlsm) まったり麻雀と149試合デュプリケートで比較牌譜(zip) バグ修正したやつ。ちょっとましになった? 0.32はかなり変えて死ぬほど弱くなっちったので非公開。 しぐま0とと9000試合やっても有意差ついてないとかどんだけ。でもしぐまより少しだけ弱い。 まったり麻雀と149試合だけ比較してみたけど0.1位以上差がある。でもさすがに放銃率高すぎなのでインターフェイス(自作)にバグがある可能性があるのでなんとも、、だけど弱いのは確か。 まったり麻雀に勝ち越してないなら天鳳で打たせてもR1700以下だから、参戦してもなあ・・・て感じ。 てかオッカムくんのプログラム、完成度低過ぎィ!
もしかして牌譜統計データって4人打ち麻雀AIに使えないんじゃ? 場の捨て牌、手出し牌、フーロ牌の組み合わせとかその場の瞬間的な情報を入力に判断しないとちゃんと出せないような気がしてならない。てかそうじゃね?
Visual Doom AI Competition @ CIG 2016
時代は強化学習かー
inserted by FC2 system