2016/10/10

ちょっとづつ

ここ1,2年ほとんど作業が進んでいませんでしたが、最近になってちょっとづつ進めるようにしてます。
時間があるときにいっきにやろうとせずに、1分でもいいから毎日やるようにしたら多少は進むようになりました。

今進めているのは序盤の評価関数の修正。本当はこんなことよりも点数状況判断などを修正したほうが強くなるのかもしれませんが、技術的に興味がある箇所をツラツラとやっていくことにしました。

| | コメント (14)

2012/10/20

Windows 8で実行する際の警告メッセージについて

Windows 8で、まったり麻雀を最初に実行するときに、以下の画像のような警告が出る場合があります。
Photo

まったり麻雀には、マルウェア、スパイウェア、ウィルスなどのような疑いをもたれる機能は一切ありませんが、ダウンロード数が少ないから危険とみなされるようです。
上記画像の赤矢印の箇所をクリックすると、下記画像が表示されます。「継続」をクリックすれば実行できます。
2

なんか、最近こんなのばっかりで、ウンザリしてます。
インターネット利用者のセキュリティやプライバシーを保護する方向に進むことは仕方のないことだとは思うのですが、こんな疑いを掛けられるのは、不愉快で割り切れない気分になります。 

参考:ダウンロードの警告メッセージと対処方法

| | コメント (13) | トラックバック (0)

2012/08/11

ダウンロードの警告メッセージと対処方法

ダウンロードの警告メッセージと対処方法

ブラウザにChromeを使っていると、以下の画像のような警告が出る場合があります。

Photo

まったり麻雀には、マルウェア、スパイウェア、ウィルスなどのような疑いをもたれる機能は一切ありませんが、ダウンロード数が少ないから危険とみなされるようです。
上記画像の赤丸付近をクリックすると、下記画像のような、プルダウンメニューが表示されます。メニューから「継続」を選べばダウンロード出来ます。
2

「まったり麻雀には、マルウェア、スパイウェア、ウィルスなどのような疑いをもたれる機能は一切ありません」という私の言葉を、信用していただけるなら上記動作でダウンロードしてください。

#ダウンロード数と、リピート率をカウントする目的で、ダウンロード時に、cgiを使って通常のWEBサーバのアクセスログ程度の情報は採取していますが、当然第3者へのログの提供などはしていません。

まったり麻雀は一般的にダウンロードされていないか?
 いつものことながら、Googleの日本語は分かりにくいですが、メッセージの意味から推察するに、おそらくダウンロード数が少ないから信用度が低いと判断しているように思えます。
 しかし、まったり麻雀はChromeのメッセージにあるような、「一般的にダウンロードされていないもの」ではありません。cgiを利用してダウンロード数をカウントしだしたのは、2009年の途中からですが、2、3年でダウンロード数は数万を超えています。
 また、(冗談交じりの記事で読みにくくて申し訳ないですが)まったり麻雀に関する世間での評価についてはこちらの記事の後半部分にも書いています。比較的(Google以外からは)好意的にとらえれているのが、お分かりいただけると思います。もちろん、 公開から7年間まったり麻雀でウィルス騒動は起きていません。

おまえがいうな
 そもそも、どうやってChromeを配布してるGoogleはまったり麻雀のダウンロード数を知っているのでしょうか?むしろそちらの方が、不思議ですし不審です。人の行動を追跡するような不審なことをしてるのは私ではなくてGoogleの方ではないかとすら思えます。インターネット利用者のセキュリティやプライバシーを保護する方向に進むことは良いことだとは思うのですが、こんな疑いを掛けられるのは、不愉快で割り切れない気分になります。 
 

| | コメント (6) | トラックバック (0)

2012/03/11

言いたいこととか今後とか

将棋などと比較して麻雀ゲームの思考ルーチンの難しさを書いてますが、結構言い訳じみた部分が多い記事ではあります。一連の記事で言いたいことは、「麻雀ゲームの思考ルーチンは将棋や囲碁とは違った難しさがあって同じように考えても上手くいかない、しかしそれでも囲碁将棋のアルゴリズムを知るのは必要」ということです。

麻雀の思考ルーチンについて語ったものはほとんどないので、私は将棋などの論文を参考にすることが多いのですが、大半はそのままでは利用できないのです。ただ、発想を変えると使えない訳ではないことあり、そういった意味で、麻雀ゲームのアルゴリズムを考えるうえで、将棋や囲碁などのアルゴリズムを学ぶことは、遠回りではありますが、必要なプロセスだと思っています。

現時点では、まだ、麻雀界のトップに君臨するレベルの雀士と比較すれば見劣りすると思いますが、私程度の実力では結構苦戦するレベルになっていますし、今後、どうしても、麻雀強いアルゴリズムが作れないかというとそんなことはないだろうと思ってます。

先読みの精度の問題にしても、αβのような枝刈りが存在しないことについても、ゲームの時空を切り取る面を変えてみたり、物事を分けて考える粒度を変えたり、逆転の発想をしてみたりすると、実は利用できる面はあります。

実際まったり麻雀では将棋とも囲碁とも全く違う切り口で局面を評価したり、精度を落とさないような工夫をしたうえで先読みを実現してますし、次のメジャーアップデートでは、αβ法のような枝刈りの考え方と、それを生かすための(パスのような)技術を参考にした、逆枝刈り(?)を実装するなどして、今とは段違いな強さを持つものに仕上げたいと思っています。

| | コメント (8) | トラックバック (0)

2012/03/10

麻雀ゲームが弱い理由(と羽生2冠が強い理由)~読みと見切り編~

先日の記事が割と評判が良かったようなので、続きを書いてみたいと思います。
前回は、局面の数に着目して麻雀の難しさについて書きましたが、今回は読みと見切り(探索と枝刈り)について紹介したいと思います。


将棋の場合:MIN-MAX法

将棋やオセロのようなゲームは、情報科学的には2人零和完全情報確定交互ゲームに分類されますが、このタイプのゲームではmin-max探索という先読みとαβ法という見切り(枝刈り)が有効であることが分かっています。

次の図のような感じです。
Minmax_2

今、Aという局面で先手の順番です。このとき先手にはB,Cという2つの手が考えられます。
先手がBを指すと後手はDとEの2つの手が考えられ、先手がCを指すと後手にはFとGという手が考えられます。

D~Gに書いてある数字はその局面で先手番からみた局面の有利さ(形勢判断)を数字化したものです。先手は出来るだけ数字が大きい局面に誘導したいですし、後手はできるだけ数字が小さい局面に誘導しようとします。

もし先手がBを選ぶと、後手はまずDの形勢判断をし(+3)次にEの形勢判断をして(+5)小さい方を選びます。その結果Bの局面の形成判断は先手から見ると+3点となります。

先手がCを選ぶと、後手はFの局面の形勢判断(-12)をし、次にGの局面の形勢判断をします。(+10)点、その結果Cの形成判断は先手から見て-12点となります。

Bが+3点、Cは-12点ですから、先手はBを選んだ方が得ということになり、Aの局面の形勢判断は先手から観て+3点ということになります。


いまの説明を式にすると
Aの評価値 = MAX(MIN(3,5), MIN(-12,10)) = MAX(3, -12) = 3
となります。

MIN(x,y)はxとyの小さい方の値を返す関数
MAX(x,y)はxとyの大きい方の値を返す関数

こういった方法をmin-max法と呼んでます。

将棋の場合:αβ法

実は上記の手順の中で省略できる箇所があります。
それはGの形勢判断です。
D,Eの評価からBが+3点だとわかりました。次にFの評価が-12点だとわかりました.
この時点でCの局面の評価値は-12以下であることが確定しています。(もしGの評価が-12より大きかったら後手はGを選ばずにF選びます)先手はBとCの打ち評価が高い方を選びますから、この段階でCを選ばずBを選ぶことが確定しますのでもうGの形勢判断をする必要はないのです。

つまり、
Aの評価値 = MAX(MIN(3,5),MIN(-12,?))という式は?の値が分からなくても
MAX(MIN(3,5),MIN(-12,?)) = MAX(3, -12以下) = 3
と答えが計算できます。
?の箇所がいくつであってもA=3であることに変わりないので、?にどんな値が入るかかはどうでもいいのです。

こういった処理の省略をαβ法といいます。この例はパターンが少ないのでありがたみが感じられないかもしれませんが、実際の将棋では選択肢は2通りだけでなく80通り近くありますので、そのうちの1つを読んだ段階でほかの79の局面を読まなくなるのは意味がありますし、2手先ではなくもっとずっと先まで読みますのでさらに効果が高まります。

なんか面倒くさいと感じされるかもしれませんが、プログラムにするとたったの数行の簡単な処理です。しかも、全く将棋の知識を必要とせず、処理を短縮してもそのことで誤差が生じるリスクが無く、処理時間短縮の効果が高いという、簡単安全高速な手法なのです。


αβ法の問題点とパスと羽生2冠

ただ、αβ法にも問題があります。図の左側から評価した場合はうまくいきましたが、この図を右側から評価してみるとうまくαβ法が働きません。
「GとFを評価してCが-12と判りました。次にEを評価して+5と判りました、Dの値がまだ判りません。」という時点では、BとCどちらを選べばいいか判断ができません。
式にするとこんな感じです。
A=MAX(MIN(10,-12), MIN(5, ?))
この式は?が-12より小さいかどうかで結果が変わってきます。

なのでαβ法はどの着手を先に読むかが大事なわけですが、理論上は、先手も後手も最善手を先に読むとαβ法の枝刈り効果が最も高いことが分かってます。

けれど、どの手が最善手かを調べようとしてるのに、「最善手を先に選択すれば処理が削減可能」といわれても困ります。それが分かるならそもそも調べる必要自体が無いわけです。

せめて、一番良い手が分からないとしてもそれなりに良い手が分かれば、αβ法は最善ではないにしろそれなりに効果を発揮するので、何とかして割といい手を探そうとするわけですが、そこで用いられる手法の一つが「パス」です。

認知科学の特別講演でプロ棋士の羽生2冠が面白いことを言っています。

「将棋というゲームの本質的な部分だとは思うのですが、可能性のある手はたくさんありますが、指したとしてもプラスになる手は限られています。というか、指さないほうが良いぐらいのマイナスになる手がたくさんあるんです。だから殆どの手は、消去法的に選ばないという感じです。」

将棋には一局面で80手前後のルール上許される着手があるのですが、そのほとんどはパスをするより酷い手ばかりだということです。なのでルール上は許されないパスを便宜的に許して、先にパスした場合を探索するとそれが割といい手を先に選択したことと同じことになり、αβ法の効果を上げる事が出来るのです。

激指などで読み筋を表示させているとパスが表示されることが割と頻繁にありますが、それはそういった手法を用いているためのようです。

Photo


探索速度と羽生2冠
もう一つ、麻雀と比較する意味において、min-maxとαβ法を用いた手法で気にしてほしい点があります。それは、形勢判断が必要なのは(原理的には)終端の局面だけだということです。途中の局面BやCでは単にルール上打てる着手を列挙して片っ端から局面を進めていけば良く、玉の固さだとか駒得だとか、駒の連携だとかの形勢判断をする必要は一切ないのです。ですから、コンピュータ将棋は1秒間にものすごい数の局面が読めるわけです。

ちなみに羽生2冠はどうしているかというと、これもまた認知科学の特別講演ですごいことを言ってます。

司会「羽生さんは将棋の盤面は頭の中でどのように描いているのでしょう?」
羽生「実際は局面が将棋版として頭の中にあるとすると、そこから符号で局面が進んでいきます。読みが進んでいるときには盤面は浮かんでいない状態です。」


羽生さんは、途中の局面をイメージ化する作業を省いて、形勢判断するべき十数手先の局面のイメージ映像がいきなり脳内に見えるようなのです。

小学生が最初は5×3を5+5+5と一つずつ計算しているけれど、慣れると「さんごじゅうご」と一気に答えを出せるようなりますが、それと似たような感じのようです。

羽生さんの話は、聞いているとコンピュータのロジックにつながる点が色々とあってとても面白いです。講演を聞きに行く機会がある人はぜひ聞きに行かれるとよいでしょう。また、ぜひ質問を用意していくべきです。羽生さんの講演の真価はむしろ質疑応答にあるといってもいいくらいです。この人は1対1で対峙して相手のアクションにリアクションを返す時にこそ、とてつもない魅力を発揮する人だと感じることでしょう。


麻雀の場合、min-max法もαβも使えない

前置きが長くなりましたが、麻雀の場合について紹介します。

麻雀の場合、確率に左右されるゲームですし、4人でやるゲームですので対局相手は、必ずしも自分の評価値を下げる着手を選ぶわけではありません。よってmin-max法の探索手法は使えません。

理論的にどういった探索が良いかは不明ですが、「まったり麻雀」に関していえば、私が勝手にprob-max法と呼んでる方法で探索をしています。

(ちなみに、処理速度やゲーム内で表示される評価値、文献などを見る限り、市販の麻雀ゲームは全く先を読んでいないと思います)

イメージとしてはこんな感じです。
Probmax


将棋と同様自分は、評価値が高い方を選ぶのですが、違いは、相手の着手は統計データから着手する確率を推測する点です。

式にするとこんな感じになります。
Aの評価値 = MAX((0.2 * 3)+(0.8 + 5), (0.7 * (-12)) + (0.3 * 10))

相手の着手の確率とその時の評価値を掛け算して期待値を出しそれを足していく感じになります。
式が上記のような形ですから、式のどこかに値が分からない個所があれば評価値が分からなくなってしまいますので、αβ法のようなゲームのノウハウがなくても実装できる安全簡単高速な処理削減方法(後方枝刈り)は原理上ありえません。

よって、厳格な先読みをしようとすると、指数関数的な計算量の爆発をもろに受けることになります。

また、終端の局面の評価だけでなく、途中の局面での確率の推定も非常に重要な意味があるため、将棋と違い読みの途中の局面でも形勢判断が求められる点も麻雀の難しさです。
(将棋にも実現確率探索というものがありますが、あれと麻雀のアルゴリズムでは求められる精度がまったく違います)

そもそも、「読み」という言葉が指すものが将棋と麻雀では違います。
将棋の読みは詰将棋などのように何手か先の局面をイメージすることであり、情報科学用語では「探索」に近いものですが、麻雀の読みは先の局面を読むというよりも、見えていない情報を推理するという意味合いで使いますので、どちらかというと情報科学用語としては、探索ではなくて「推定」に近い感じがあります。その言葉の違いだけでも、途中の局面の確率推移の必要性が重要であることが表れているといえるでしょう。


麻雀の場合先読みすれば強くなるわけではない

将棋の場合、先が読めることはそのまま強さに直結しますが、麻雀の場合はそうはいかないのも麻雀ゲームの難しさの一つです。
麻雀の局面の計算式は、一巡先を読むごとに、評価値に確率的予測の掛け算がかかってくるため、先を読むとそれだけ精度が下がってしまうのです。


つまり、例えば、1巡先を90%の精度で読めたとしても、2巡先は81%(0.9*0.9)、3順目は72.9%とドンドンと精度が落ちて行ってしまい5,6巡先には当たるかどうか五分五分まで精度が落ちてしまうのです。

なので麻雀の場合、どうしても評価値の誤差が大きくなってしまい、そのため強いコンピュータを作ることが困難になります。


参考文献

羽生2冠の思考について認知科学やAIの視点で語られた本に「先を読む頭脳」があります。
とても面白い書物です。値段の安くなった文庫版も出版されてますので、ぜひ読むことをお勧めします。

コンピュータ将棋について教養レベルで知りたければ以下の本がお勧めです。渡辺竜王とボナンザの対局、あからと清水女流との対局、8bit時代からのコンピュータ将棋の歴史をユーモアを交えて書かれています。将棋ソフト開発者や棋士へのリスペクトも強く感じます。


情報系の大学生かそれに近いレベルの人で実際に思考ゲームを作りたいならば以下の本がお勧めです。
この手の本としては、比較的最近出版されたもので結構新しいノウハウも書かれています。
各章の主題なテーマだけでなく、文章の中にもさらっとわりと重要なことが書かれていたりします。
この本に書かれているものの猿真似では、麻雀ゲームには使えませんが、なぜ使えないかを考える過程で、自分なりの答えを見つけていくことはできるだろうと思います。というか、頼りになる麻雀の文献はないので、そうするしかありません。


次回:評価関数と最適制御理論とモンテカルロ探索編につづくかもしれないし面倒くさいので書かないかもしれません。

| | コメント (2) | トラックバック (0)

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南白付き物のクオリティの差

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


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

| | コメント (8) | トラックバック (1)

2011/10/01

統計的手法の問題点

「○○のときに立直すべきかどうか」を調べたいときがあります。

○○の箇所にはたとえば、「七対子でドラ待ち単騎になったとき」とか、「東1局で子で平和のみで聴牌したとき」などが入ります。

こういった問題を解決するときに、、鳳凰卓のデータから○○の条件にあてはまるデータを集め、立直したときとリーチしなかったときの結果を比較して、答えを出そうとする方法がありますが、これは相当に誤差があるように思えます。

そもそも、鳳凰民というのは相当にレベルの高い集団であり、立直して不利ならば、立直なんてしないわけです。実際に立直したデータには、それだけ立直した方が有利である状況のデータばかりがそろっているわけです。

単純にいってしまうと、鳳凰民が的確な立直判断をしているならば、「○○のときに立直すべきかどうか」を牌譜から実際に立直したときと、立直しなかったときの結果で比較したら、○○の箇所にどんなテーマが入っても、立直した方が不利という結果は絶対に出ないということです。


なので、牌譜データを参照してコンピュータの思考ルーチンのデータとするときは、その点を考慮する必要があるのですが、これがなかなか難しくて、麻雀を統計的に解析するというのは悩みが多いです。


| | コメント (8) | トラックバック (0)

2010/06/05

槓のルール考えたやつ出て来い

槓がらみのGUI操作部分とゲーム進行役部分を作成中

毎度思うんだが、麻雀ゲーム作ってると槓のルール考えたやつに文句を言いたくなる。
槓こそが、麻雀を面倒なものにしてる諸悪の根源に思えてならない。

チャンカンとかリンシャンとか作るの本当に面倒くさいし、明カンのときのカンドラ後めくりのルールなんて、明カンしたあと暗カンしたらどうやってドラをめくるのかとか本当にちゃんと考えてるかといいたくなるし、一発とかハイテイとかとの複合のルールもローカルルール満載だし。
それに、三槓子とか四槓子とか、役の難易度と点数設定のバランスに無理がある。

チャンカンをロンせずにスルーするとフリテンになるのに、つも上がりできるときに上がらずにカカンしても、フリテン扱いにならないのもなんだか納得いかないし、プログラム作るのが無駄に面倒になる。

そもそも何で、カンした後の補充牌を王牌からとるんだろう。どうせ王牌を14枚残すなら普通に次のツモ位置から取ればいいじゃないかと思う。

どうせカンしてもシャンテン数は上がらないんだし、カンが無ければ点数計算の覚えやすさもずいぶん楽になるんだから、カンなんて存在自体を抹殺してしまえばいいのにと思う。

| | コメント (8) | トラックバック (0)

2010/03/26

ギアチェンジしよう

死ぬほど忙しかった表向きの仕事もひと段落したことだし、そろそろ、作業に本腰を入れたい。

とりあえず、ゲーム進行部の作り変えをやっていく。

| | コメント (0) | トラックバック (0)

2010/02/02

天鳳の牌譜形式変更

また、天鳳の牌譜が解析できなくなってる。ネットでしらべても話題になってないところを見ると私のPCの問題なのか。


追記:原因わかった。牌譜の形式がまた変わってる。AGARIタグのowari属性の値が
小数点第1位まで書かれるように変わってる。

<AGARI ba="0,0" hai="6,10,15,25,26,41,44,48,77,80,85" m="38923" machi="41" ten="30,3000,0" yaku="25,1,8,1" doraHai="17" who="0" fromWho="0" sc="285,30,283,-10,215,-10,217,-10" owari="315,41.0,273,7.0,205,-29.0,207,-19.0" />

天鳳のログは、gzip形式で圧縮されているので、解凍して、上記の「.0」を取り除き、もう一度、gzで圧縮して、拡張子を変更すれば、解析できるようになる。

まったく……なんでこんな余計な修正を入れるかな。雀荘モードに必要なら、雀荘モードのログだけ変えればいいじゃないか。ツール作る側としては、どうせ過去の形式にも対応しなければいけないので、2通りのフォーマットがあっても手間は一緒なんだから。

それと、前にも書いたかもしれないが、ファイル形式を変えておきながらバージョン表記を上げないのはどうかと思う。<mjloggm ver="2.3">

単純な修正なので、前みたいにコンバータ作るのは難しくはないけど、まずは、天鳳牌譜解析ツールの作者の対応待ちたい。連絡方法があれば伝えたいんだけど、天鳳牌譜解析ツールの作者はメールアドレスも掲示板も開設していないので伝えようがないし……

| | コメント (4) | トラックバック (0)