« 2012年1月 | トップページ | 2012年3月 »

2012/02/21

バク修正中

迷走していた新アルゴリズムですが問題の原因は判明しました。いつものごとく単純ミスでした。性能が出ない問題についてもほぼ解決し、自分としてはおおむね合格点が出せる水準まで処理速度が出るようになりました。

あとは地道に作業を続けるだけですがなかなかやる気か起きずに進んでないのが現状です。

昨日の記事は予想以上に反響がよかったのでいずれ何らかの形で続きを書きたいと思いますが、いつ頃になるかは、私もよくわかりません。

| | コメント (0) | トラックバック (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)

2012/02/18

迷走中

新しい探索アリゴリズムを作成していますが、色々バグがあるうえに速度も出ておらず迷走しています。
今は何が原因なのかよくわかっておらず、心がもやもやしてるままです。
ただ、解決できないはずはないのでもう少し粘ってみるつもりです。

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

2012/02/15

まったり麻雀Ver0.9.5公開します

まったり麻雀Ver0.9.5を公開します。
修正点は鳴き判断のアルゴリズムです。2012/02/07の記事のコメントで指摘いただいた問題を修正しています。

新アルゴリズム1人(?)vs旧アルゴリズム3人で38119試合対戦させてみたところ、平均順位2.4822と東風荘のRateで+20程度強くなっているようです。

またおかしな点あればコメントください。

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

2012/02/12

6段復帰

天鳳、6段復帰しました。
5段->6段は99戦かかりました。5段になってから一時期原点を割っていたこともあったのですが、上昇に転じてからは一気に6段まで到達した感じです。

ただ、私の場合、問題はここからです。万年6段を脱却するために打ち方の変更を行っていて、4段に落ちてからの成績では、7段に到達できるだけの成績をのこしていますが、運に味方された感があります。

7段到達できたら、どのように打ち方を修正したのかブログ記事にしたいと思いますが、簡単には7段になれないかもしれません。

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

2012/02/07

探索部分作成中

最近寒くて、やる気が出なくて、ちょっと、いやかなり、開発速度が落ちてますが、マルチコアCPUに対応させるための新探索ルーチンをのろのろと作成中しています。だいぶ形が出来てきていてそれなりに動いていますが、まだ、色々細々とした面倒くさい処理がまだ残っているし、まだちゃんとマルチコア用の排他などもしていない状況です。

ある程度形になったら、次は本格的にマルチスレッド化するか、それとも、まずは、速度度外視で、探査範囲を広げた処理を組み込んでどれほど強さが変わってくるか試すかどちらかの作業をするつもりですが、どちらを先にするべきかまだ決めかねています。

アンケートはおかげさまでそこそこ数が集まっています。まだ十分な数とは言えませんが、このブログのアクセス数の少なさのわりには、かなり驚異的な数の回答が集まってる感じです。

ほんと、好意的で協力的な利用者に恵まれてフリーソフト開発者としてはとても幸せだと思ってます。ありがとうございます。アンケートは当面継続して募集していますので、よろしく願します。

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

2012/02/04

利用者アンケートへの協力のお願い

まったり麻雀を利用されている方にアンケートをご協力をお願いします。

アンケートサイトはこちらです


アンケートの集計結果は、次の次の次あたりのメジャーバージョンアップのとき、参考にさせてもらいます。

追記:2012/2/6 10:99~20:00位の間、アンケートサーバがダウンしてましたすいません。

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

« 2012年1月 | トップページ | 2012年3月 »