まったり麻雀と科学する麻雀の押し引き判定の違い

　先日のブログエントリに、LUFFYさんから以下の質問がありましたので、お答えします。

　 　まったり麻雀の押し引き判断は「科学する麻雀」に書かれている基準よりかなり押しに寄っていると思ったのですが、あれは一体どのような計算式で出しているのですか？「科学する麻雀」ではベタオリが100%成功するものとして押し引きを計算していますが、オリウチの可能性を考慮するとあのような判断になるという事でしょうか？

　押し引き判定の基本的な考え方は科学する麻雀と同じです。しかし、以下の点に違いがあります。

放銃点数と確率の違い
　科学する麻雀の押し引き判断で利用している振り込んだときの点数は、ツモ和了もロン和了も一発もすべて入った点数になっていますので、実際の放銃点数より高く見積られています。まったり麻雀では、そういった点を考慮して放銃点数を算出しています。
　また、ゼンツしたときに放銃する確率の想定もまったり麻雀と科学する麻雀では違っていて、まったり麻雀の方が低い値になっています。

第3者の挙動の計算の有無
　科学する麻雀は警戒している立直の相手と自分以外の第3者挙動に関する計算がありませんが、まったり麻雀は計算に入れています。

不聴罰符を考慮の有無
　不聴罰符の点数を科学する麻雀では考慮していませんが、まったり麻雀は考慮に入れています。旧バージャンのまったり麻雀では、不聴罰符を考慮に入れてなったのですが、途中のバージョンから考慮に入れるようになりました。これを考慮に入れるか入れないかの違いだけで、押し引き判定にかなりの差が出ます。

オリ打ちの考慮の有無
　科学する麻雀は降り打ち率を0%と計算していますが、まったり麻雀ではオリ打ちを考慮に入れています。

回し打ちの考慮(押し引き判定の表示方式の問題)
　まったり麻雀のメニューの「コンピュータ判断」－＞「押し引き判定」では、回し打ちを考慮しており、回し打ちをした方が良いと判断したときは「押し」と判定表示しています。
　また、ゼンツした場合に切る牌と降りた場合に切る牌が一致した時も「押し」と判定しています。「引き」と判定されるのは、完全に和了に向かうのを諦める方が良い時だけです。

　当初のまったり麻雀の押し引き判定はもっと引きに傾いていて、科学する麻雀に似た感じでした。しかし、バージョンを上げるにつれ、色々考慮する要素を増やしたところ、徐々に押せるケースが増えています。新旧アルゴリズムの対戦させてみると新しい方が強くなっています。局収支をベースに考えるのであれば、科学する麻雀の押し引き判定が引きに偏っているのは理屈から考えても、間違いがないでしょう。まして、世間で言われているシャンテン押しはダメというのは、その言葉を文字通りに受け取るのは明らかに間違いであると言えると思います。実際、公開前のある段階で、まったり麻雀は対立直に対して１向聴はすべて降りているようにプログラムしていた時期がありましたが、あの当時のまったり麻雀はかなり弱いものでした。

　けれど、私自身も今のまったり麻雀は押しすぎている気がしています。まったり麻雀は愚形テンパイが多いので新旧アルゴリズムの対戦結果をどこまで信じてよいかは微妙だという問題もありますので、自信をもって現行のまったり麻雀の判断が正解であるともいえないのが実情です。
　
　なお、今後、押し引き判定の表示は廃止するかもしれません。次のメジャーバージョンアップでは、思考アルゴリズムを刷新する予定で現在開発を進めていますが、その新しいアルゴリズムではベタオリモードやツッパモードなどをコンピュータが意識しないようになるためです。

　最後に、基本的にまったり麻雀のアルゴリズムはまだ、ヒ・ミ・ツです。今後こういったまったり麻雀の思考ルーチンに関する質問には答えないケースもあることはご承知おきください。

手牌構造の作成終了と次の作業

色々苦労していた手牌構造クラスのテスト＆バグ取りが完了しました。
新しい手牌構造は、一色分の全ての門前手牌パターンを丸ごとメモリに持つようにして、向聴数チェックや有力な捨て牌候補や受け入れ候補の列挙、手替わりや向聴戻しを含めた局面の変化を高速に処理できるようにしました。

手牌構造の作成がひと段落ついたので、次は、探索処理(局面の先読み）を作成していくつもりです。

既存の探索処理は再帰呼出しを使って実装していますが、新しい探索処理は、再帰呼出しを使わずに、スタックを使ったループで処理するように修正します。Ｃ＋＋言語などの処理では、機械語レベルで見ると、関数を呼んだときにパラメタをスタックに積んで、サブルーチンにジャンプするような処理をしているわけですが、それを自分でスタックにデータを積むプログラムにする感じです。

なぜこのような修正をするかというと、スタックに積んだり、スタックに積まれたデータを取り出して処理する箇所をマルチスレッド化することで、マルチコアＣＰＵの性能を無駄なくフルに引き出して、より深く広く局面を読めるようにするためです。基本的なアルゴリズムはオライリーの並列コンピューティング技法に載っているサンプルを参考に作成していくつもりです。

まったり麻雀Ver0.9のクラス構造

まったり麻雀Ver0.9のクラス構造は現在以下の図のようになっている。

ナントカViewクラスの親クラスとしてコンポーネントクラスを持たせた方がよかったとか、インターフェイスじゃなくて抽象クラスである程度実装を共通化できたんじゃないかとか、いろいろ反省点はある。

またＡＩ部分はまだ手が入っていないのでこれから変わる可能性はまだまだありそう。

棒テン即リーアルゴリズムと向聴数計算方法

手牌を探索するとき、受け入れ牌、捨て牌候補のリストアップをする必要があるけれど、そのために、まずは向聴数をベースにリストアップするのがひとつの現実解となる。

１３枚状態の手牌と１４枚状態の手牌の向聴数が調査できるアルゴリズムが作れれば、１４枚状態から向聴数を落とさずに１３枚状態にできる牌をリストアップすることも簡単にできる。
そして、打牌をして１３枚状態になった手牌で、個別に牌を追加して１４状態にしたとき向聴数が向上する牌の種類と枚数をカウントし、最も多くなるような、打牌を選択すれば、棒テン即リーのアルゴリズムは出来る。
　東風荘でR1400以下程度のあまり真剣に麻雀に取り組んでない人相手なら、単純にこれだけのアルゴリズムでもそこそこ相手になる麻雀プログラムになる。

向聴数を調査するアルゴリズムには、おおむね２通りのやり方がある。ひとつは手牌をバックトラック法で、面子、塔子、対子、孤立牌に分割する全パターンをリストアップし、そこから、面子数、塔子数、対子数から向聴数を計算する方法。

もうひとつは、あらさんのホームページに載ってるような１スーツ分のハッシュテーブルを持つ方法。
１スーツ分（例えば、萬子）の考えうる全てのパターンと、
手牌を面子数×１０＋（塔子＋対子）の数が最大となる面子の数と（塔子＋対子）の数と、
、面子数×２＋（塔子＋対子）が最大となる、面子の数と（塔子＋対子）の数を
構造体メンバとしてもつハッシュテーブルを作ってそこから向聴数を計算する。

　単純に向聴数をカウントするだけだと、ハッシュ方式の方が５０倍近く早い。
あらさんの一人麻雀練習機はこちらを採用している模様。

　ただ、ハッシュ方式だと、死に塔子の判定がしにくい。死に塔子とは、例えば１－３のカンチャン塔子を持ってるとき、他者に２を槓されて面子に変化しなくなってしまった塔子のこと。このときは実質向聴数が＋１になるけれど、ハッシュ方式だとこういった死に塔子をバックトラックで探索していかないと見つけられない。
それに、アルゴリズムによっては打牌せず、ツモだけして、多牌状態にしてから評価したりする場合もあり、そういった方式に応用しにくいし、事前に無駄だと分かる打牌を前方枝刈りするのも難しい。
　また、単純に速度面から言っても、向聴数の計算は速いものの受け入れ牌のカウントや、打牌候補の選定は手牌分割方式より遅いという欠点もある。（これはそれ専用のテーブルを作れば解決できるが）

　鳴きなし、相手なしの一人麻雀だとハッシュ方式でなんら問題ないんだけれど、点数状況による和了点の制限や鳴き、他家の捨て牌等がからむ４人麻雀ではたとえ５０倍遅くても手牌分割方式のメリットは捨てがたい。

なので、私は今まで手牌を面子塔子対子孤立と分割状態にした状態のままコンテナに入れておく手牌クラスをつくり、、探索中は、分割状態を持ちまわって手牌のツモ＆打牌が出来るようにしている。
そのことで、速度的に遅い手牌分割を最初の１回だけしかやらずに済ましている。

　今回Ver0.9用に作り直すにあたり、両方の方式を実装してみたけれど、トータル的に、手牌分割方式のほうが便利そう。
　ただ、Ver0.9用につくっている最中に発見したんだけど、Ver0.8では同じ手牌を何度も評価する無駄な処理があり、結構時間がかかってしまっている。私がVer0.8で採用しているアルゴリズムはあらさんのものより遅いのだが、どうもここの無駄な処理が原因だったようだ。てっきりハッシュ方式の向聴数チェックをしていないためだと思い込んでいた。

　ちなみに、麻雀ゲーム作ってるときはパターンが多くてテストが大変なんで、確実に動くが遅いバージョンと高速化バージョンの２パターン（以上）を実装してアウトプットが同じになるか比較して検証している。
そのため、オブジェクト指向型の言語で個々のパーツの入れ替えが簡単に効くように作ったほうが何かと便利だと思う。

エンターテイメントと認知科学研究ステーション第5回講演会

エンターテイメントと認知科学研究ステーション第5回講演会が電通大であったので、行ってきました。

内容はUCTの囲碁への応用の理論編と実践編と５五将棋の自己対戦による学習。

UCTはまあある程度理解できたのですが、５五将棋のほうがいまいち理解できず。
５五将棋ってのは以下の局面から始める将棋のようで、成れるのが１列目だけだという以外は、ほぼ将棋と同じルール（持将棋と千日手は違う？）とのこと。

本将棋のようにプロの棋譜が利用できないので、自己対戦での数手先の評価関数を元に評価の重みを調整しているってことがミソらしいだけど……なんかそこがいまいち具体的にイメージできず。正直よく理解できなかった。

例えば、後手1一玉のときの２三銀の価値を学習させるのは、
その数手先までをmax-minで探索して、駒の位置関係だけではなくて、駒割とか玉の安全度とか、すべての要因を使って評価した評価値を使って目先の銀の価値の重み付けを変えているってことなのかな？

要するに、ここで銀をこう動かしておくと、数手先には駒得する（あるいは玉の安全度が高くなる）から、
この銀の位置は評価が高いってこと？?

いまいち分からないのは、自分自身で自分を評価してるんだから、
俺様ワールド全開な自己チューな価値観の世界に落ち込まないのか？

そもそもこの評価方法でうまくいくのは学習する前の評価関数が既にある程度強いからだというニュアンスに聞こえた。それに学習前と学習後で強さも比較してないんだから、これが正しいのかどうかさっぱり？？

それと１一に後手玉が居るときの先手銀の評価価値の学習結果をスライドで紹介していて、
２四や４４の地点の評価が高く、３四の地点の評価が低かったけど、これは、
相手玉との位置関係で評価しているというより、
初期局面から３四銀に上がると、（銀が戻れない＆角が動けないので）着手可能数が少なくなってしまうことが影響しているのであって、相手玉との位置関係を評価しているわけではないのでは？

同様に、４四銀もどちらかというと相手玉との位置関係の評価というよりも、
自分の王を守っているということで、ポイントが高くついているだけのような気がするんだけど。

なんだか中盤戦が長く続く大混戦になったら無意味な評価値になるそうな気がしたんだけどどうなんだろう。
（成りゴマができ難いため、盤面が狭い割には意外と長く中盤戦が続くのでは？）

でも、結果を出しているんだからきっと正しいのだろうな。

UCTを利用したモンテカルロ法とミスに着目したゲームの特性

コンピュータ将棋協会のブログで知ったのですが、ゲームプログラミングの学会GPW2007の話題の中心はボナンザタイプの機械学習による評価関数のデザインと、UCTらしい。

機械学習については、以前調べて、大体のどんな感じのものかおぼろげに理解したけれど、UCTってなんなのか、まったく言葉すら知らなかったのでちょっと調べてみた。

ついでにプログラムを組んでみた。

UCTって何か？

これは、モンテカルロ囲碁で最近流行の手法で、UCB1を使ってゲームの木のノードを下ってからモンテカルロシミュレーションする手法のことらしい。

UCB1ってなにか？

ぶっちゃた言い方をすると、パチンコの台選びを想像するのが理解しやすいかも。
釘が読めない前提でパチンコで台を選ぶとき、それぞれの台を試し打ちして、スタートチャッカーへの入賞率が高い台（いわゆる良く回る台）を探す。

そのとき、「そこそこ回るパチンコ台を見つけたけど、まだもっと回る台があるかもしれない。まだ試してない台を打ってみるか？」とか、「この台は異常に良く回るけどまだ試し打ちの回数が少ないので回転ムラで回ってるだけかもしれない、さっき打ったあっちの台はたくさん試し打ちしてそこそこ良く回ったのであっちのほうが本当は良い台なのかも？」とか案外迷うことがある。すべての台を十分な回数試し打ち出来れば良いけれど、そんなことしていたらけっこう金を損してしまう。UCB1ってのはそこらへんの立ち回りをゲーム理論的に数式化したものと思っていいらしい。

UCTやUCB1については以下の日本語訳してくれた論文を読むのがわかりやすそう。
http://www.geocities.jp/hideki_katoh/RR-6062-v3-jp.pdf

論文読んでみたけれど、数式の導出過程など理論的に深いところまで追求しないで、単純にアルゴリズムを使うだけなら割りと簡単っぽい感じ。

実際最強を目指して強くするためには色々工夫が必要だろうけれど、そこそこ遊べればで良いのであれば、単純に、
１）この局面から次にさせる手をリストアップする
２）ゲームの終了を認識して勝ち負けを判定する。

この２つさえ書けばあとは、あとは、定型的な処理でいろんなゲームの思考ＡＩが出来るみたい。

ほんとにこんなお手軽な方法で強くなるのか！？と思って試しに作ってみた。

選んだゲームは私の地方では「753」って呼んでいた線消しゲーム。

紙に以下のような３本，５本，７本の線を描いて2人で交互に線を消して行き、最後に残った線を消したほうが負け。

こんな風に連続した線を消すのはありだけれど、

このように、消した線をまたいだり、斜めに消すのはダメというルール。

ソースコードはこちらからどうぞ。
(Ｃに限りなく近いC++。Visual Studio2005でコンパイルして動作確認している)
(ゲームの局面数が少ないんで考えうる局面は全部配列に持ってるし、ノードの下り方なども、もっと工夫がいると思う。)

初手の最善手を100万回の試験数で試してみた結果が以下。

どうやら、このゲームは先手必勝で、初手は5本の線の端１本を消すことがベストの模様。

しかし、これ、あまり、このＵＣＴの効用を示すのには良くなかった。
というのは、７５３ゲームの場合、１００万回のシミュレートってのは結局のところ、全数探索をしてしまっていてることになっているから。

これが、全数探索するまでには至らない0万回程度のシミュレート結果だと、どの選択でもほぼ５割に近い数字になってしまって差がつかなかった。

どうしてこうなってしまうのか、ちょっと考えてみた。

＊　＊　＊　＊　＊

これは、７５３というゲームの特性がＵＣＴに向いていないために起きてしまうのだろう。
ここでいうゲームの特性とは、ミスと勝敗の関係についてのこと。
ゲームにはミスが付き物で、ミスが勝敗を分ける要因になるのだけど、実はこれには3つのタイプがあると私は思う。

タイプＡ）ミスした回数が多いほうが負けるゲーム
ゲーム中に着実にポイントを稼いでいったほうが勝つタイプのゲーム。
例：囲碁、はさみ将棋、タクティカルウォーゲーム

タイプＢ）最初にミスしたほうが負けるゲーム
タイプＢ－１）
最初にリードしたほうが小さなミスをしても逆転されにくいタイプ
タイプＢ－２）
最初に築いたアドバンテージにより、その後お互いが無難に
行動していてもドンドン差がついていってしまうタイプ
例：　競艇などのレース（Ｂ－１）、ポーカーの大会（Ｂ－２）、格差社会

タイプＣ）最後にミスしたほうが負けるゲーム
いくら途中まで有利に局面を進めていても一度の小さなミスで形勢が逆転してしまうタイプ。
例：７５３ゲーム、石取りゲーム、将棋（プロレベル）

もちろん、完全に３つに区別できるわけではない。
はさみ将棋などはタイプＢの要素もあるし、素人レベルの将棋は、ＡＢＣのどれにも当てはまる。
マージャンは基本的にはタイプＡだけれど、タイプＢの要素も含んでいる。
ただ、７５３は典型的なタイプＣ。

そして、ＵＣＴは以下のように、ゲームの木を途中まではまじめに下っていくが、そこから先はモンテカルロでシミュレートする。（図は先ほど紹介した論文から引用）

だから、途中で築いた形勢有利な局面が、モンテカルロのランダムさで無意味になってしまうので、タイプＣのゲームとはすこぶる相性が悪いということなのだろう。

ほかにもUCT+モンテカルロとの相性に関連するゲームの特性があると思う。

合うタイプは以下のようなタイプではないかな。

１）　ランダムに打っていても一定の手数でゲームの決着が付くタイプ
○囲碁、オセロ　×将棋、マージャン

２）　途中の局面での静的な評価関数を作るのが困難なタイプ
○囲碁、△マージャン、オセロ、将棋

３）　（仮に前方枝狩りをしたとしても）着手数が多くて探索が困難なタイプ
○囲碁　△将棋　×マージャン、オセロ

こう見てみると、囲碁は実に相性が良い感じがするけれど、将棋は相性が悪いのではないかと思う。
マージャンの場合は、前方枝狩りを入れれば使えないことは無いけれど、枝狩り前提ならそもそも着手数が少ないのと、マージャンでは、許される思考時間が短いため、どちらかといえば相性が悪い部類になるだろうと思う。

追記：
似て非なる将棋と囲碁のゲームの特性の違いについては、毎日コミュニケーションの週間将棋のコラムが結構面白いです。おすすめ。

ゲームの木と、鳴きへの変化を考慮した評価関数

まほ公さんの指摘のとおりで、現行のメインで利用している期待値型評価関数は評価点を算出するときに、鳴きへの移行を考慮していない。これを修正する方法については、実はすでに、プランがあることはあります。
どういう風な仕組みなのか、ゲームの木で将棋の場合も交えて紹介します。

将棋の場合
まず、将棋のような決定完全情報２人零和交互ゲームの場合のゲームの木ですが、以下の図のようになります。

ゲームAIの初歩の初歩、いわゆるMin-Max法ってやつです。
これだと、後手番は評価値が一番低い値、先手番は評価値が一番高い値をバックトラックで選択していくわけで、
選択したけっか、現在の局面の評価値を算出するためのノードのパスは終端まで１つのパスでつながり枝分かれがなくなりますし、局面の評価値は終端ノードの評価がそのまま使えることになります。

これだと、αβ法などのよく知られている方法で枝狩りがしやすいのですし、局面評価値も割りと雑でもなんとかなるのです。

麻雀の場合
ところが、不確定要素の入る麻雀の場合そういった手はつかえません。
以下は一人麻雀の評価値を出すためのゲームの木です。

Min-Max法ではなく、Max-Prob法（そんな呼び名無いと思いますが、今私が勝手に命名した）になるわけです。

つまり、「打牌」については最大値を選択することなるけれど、「ツモ」については、イメージてきには、Σ（各ノードの評価値ｘ実現確率）になるわけです。（あくまでイメージです。実際は順目の概念が加わるのでもっと複雑です。）ですので、現在の局面から終端ノードまでは１つのパスにはならず枝分かれが生じることになり、枝狩りがやりにくいのです。さらに、現在の局面の評価値は終端ノードの評価値とはことなることになります。さらに終端ノード以外は評価値に掛け算が加わるので厄介なのです、たとえば精度９０％の読みでも、４回程度、先読みするとほぼ、当てずっぽうになってしまうのと同じなのでどうしても精度が低くなります。

以前「うしうし掲示版」で最適制御理論と機械学習の手法で麻雀の局面評価関数を作成する論文について、疑問を提示したとき、評価値は、先読みするとき確率と親和性のある値でないとまずい。という意図の記述をしたのは、麻雀はこういったゲームの木になるためです。

まったり麻雀の４人ゲームも実は基本はこれの一人麻雀のゲームの木をベースにしています。４人ゲーム化の補正をするために、評価値ｘ実現確率の部分に、牌譜からとった情報を元に、補正値を入れています。
つまりこんな感じの計算になります。Σ（評価値ｘ実現確率＋他家和了時評価点ｘ他家和了確率）

ただ、この4人化のための補正が現在かなり大雑把なために、新アルゴリズムが四人ゲームにしたときに弱くなってしまってます。

さらに、まほ公さんから指摘のあったとおりで、これには、鳴きの考慮が入っていない。
現在は、評価値はツモ前提の評価で、鳴ける牌は別のアルゴリズムを使って、鳴いた牌が出たときに、評価をしているのが現状です。

麻雀に強い人ならば、ご存知のように、ポンチーするパイというのは、鳴いた牌が場に出てから考えているのでは遅いのです。もたもたしている間に次の人につもられてしまうし、ネットだと鳴きラグでばれてしまう。
打牌する前に鳴くことも考慮して打牌を決定するわけです。

まったり麻雀は鳴く牌が出てから考えているため、鳴きラグでCOMが鳴くかどうか迷ってる（？）とばれてしまわないように、鳴き判断の処理速度は極端に気をつかってプログラムをしています。そのため、結果的にあまり深く考えずに鳴いているというのが現状です。

鳴きの考慮は結構難しいので後回しにしていましたが、まったく考えていなかったわけではないのです。プランとしてはだいぶまえから暖めていて、いろいろな作業と絡めなければいけないのでブログで紹介していなかっただけ。先にプランだけ紹介すると、自分が作業する前にほかの人に作られちゃうから、隠したいという気持ちがあったのです。

鳴き考慮の場合

要するに意思を持って変化する局面と確率で変化する局面が交互にくるのが、麻雀の特徴。これでも厄介なのですが、何とかゲームの木にすることが、できますし、実際プログラムとしてまったり麻雀のメインアルゴリズムにつかっています。鳴きが入るとさらに厄介です。鳴き判断は、確率による推移と意思による推移が同時にやってきます。しかし、鳴きのイベントを意思による局面変化と確率による局面変化にわけて、ゲームの木にすることは可能です。

どういったゲームの木になるかというと、以下のようになります。

このようにノードを分ければ、鳴き考慮を打牌の前に判断しておく評価関数が作成可能です。

(麻雀の他家挙動を含めたすべての事象をこのようなゲームの木で確率によって局面が推移するノードと意思によって局面が推移するノードにわけてゲームの木にすることが、麻雀の理想のアルゴリズム実現になるのではないかと思っています。)

＊　＊　＊　＊　＊

ただし、実際これをゲームに組み込んで遊べる形で、実現するためには、どの程度の確率で鳴けるのかとか、手牌が短いときの放銃の確率だとかいろいろデータを取る必要があり、すっごく作業が面倒です。
そういった泥臭い部分を除いても、順目の概念と評価値を組み合わせるのも複雑になり、手順前後による同一局面を枝狩りすることも困難にあります。さらに、一向聴手替なしでさえ、6手先までの深さを読まなければいけないので速度の問題もまた出来る可能性はあります。
＊　＊　＊　＊　＊
実は、前回の手替わり考慮版評価関数はあくまで「布石」にすぎません。それほど落胆しているわけでも、失敗したわけでもありません。ここで紹介した鳴きありの探索や、点数状況判断の考慮のためのベースアルゴリズムとして活用可能なので原理が確立でき、処理速度のめどが立てばそれでOKなのです。

可能であれば、点数状況判断や手替わりの判断の修正をいれるまえに、新アルゴリズムをメイン評価関数にすえて一度、ージョンアップして公開したかったのですが、それができなかったというだけです。布石として着手したことが根本的に失敗だったとは思っていません。

期待値型麻雀評価関数のジレンマ

「真の意味でのデジタル派な…」とか名乗っておきながらこんな言い方するのはなんだけど、オートモードで新アルゴリズムが打っているのをぼんやり見ていると、なんかすごく流れが悪いなと感じる。自摸の運が悪いとかではなくて、打ち方にポリシーを感じないという意味で。

ようするに、天さんからも同様のコメントいただいているけれど、「ここでこう打つなら、さっきああ打てばいいのに。」と感じる打牌が多いのだ。

前の状態だと打牌の良し悪しは別として打牌に一貫性があった。だから、棒聴即リー派な人が打ってると思えば割と自然に感じられたけれど、今度はいかにもコンピュータが打ってるっぽい支離滅裂なうち方と感じるケースも出てくる。変な表現だけれど、山崎一夫さんが打っていたのが途中から小島武夫さんが代打ちに入った感じになる。(!?)

これは、新アルゴリズムが計算量の関係で１向聴のときには使えるけれど、２向聴のときには使えないことに原因がある。２向聴と１向聴でアルゴリズムが替わるので、当然打ち方の癖が変わる。２向聴までは割と棒聴気味の打ち方なのに、１向聴になると手替わりまで読むようになるのだ。

２向聴でも新アルゴリズムが使えると良いのだけれど、どうしても計算量の爆発が起きてしまう。
２向聴で手代わりまできっちり期待値計算することは、３向聴の手で棒テンをで探索するのと同等以上に計算量がかかるのだけど、２向聴(6手先まで探索)から、3向聴(8手先まで探索）に探索の深さを変えると、単純なやり方だと、計算量は２００倍から３００倍程度かかる。
まったり麻雀は２１世紀に入ってから発売開始された程度のPCの能力でも快適に動作できることを目安に計算量を決めているが、それらの比較的古いPCでも、ボウテン期待値型のアルゴリズムで計算させて、２向聴の手牌で最悪でも２，３秒以内には打牌すると思う。けれど、３向聴だと３分以上かかってしまい、ゲームの思考アルゴリズムとして使えない。

麻雀では、手がまとまっていない早い段階で手替わりを考えるのは、有効度が高いが、順目が進んでから考えるのはあまり有効度が低いとされているのだけど、この関係が逆になってしまうというジレンマが起きてしまっている。
私のプログラムは速度的に改善できる点がいっぱいあるので、何とかチャレンジしてみるつもりだけど、正直これはそんなに簡単ではない。このジレンマが解決できるようだと、少なくとも一人麻雀では人間が太刀打ちできない領域に達するだろう。

残念だけどボツ

門前のときに使ってる当たりパイの危険度と同じやり方で染め手読みをやらせようとしてみたが、うまい具合に判定できない。まだ、単純に河にでてる枚数を数えたほうが上手くいく。残念だけどコレはボツ。

とりあえずデータとりはこのくらいにしておいて、実際にゲームの方に組み込むようにしてみる。

役読みアルゴリズム

立直牌の描画部を作成中。

同時に、脳内では、Version0.8.4を出した後の機能を検討中。
今のところ、次はパイの大きさの問題と、鳴き仕掛けへの防御についてを同時にやる予定。

鳴き仕掛けへの防御アルゴリズムの実現方法として、今アイデアとして考えているのが、ベイジアンフィルタを用いた役読みアルゴリズム。

GoogleとかMSがベイズ理論に注目してるって記事を読んだときから、気になって、WEBで調べていたけれど、スパムメールフィルタ（ベイジアンフィルタ）などはベイズ理論の典型的な応用例だそうだ。

ベイジアンフィルタは麻雀にかなり応用が出来そうな予感がしてる。
たとえば、鳴き仕掛けへの防御。
鳴き仕掛けへの防御は、門前と異なって、役や点数を読むことがある程度可能。それをコンピュータにやらせることを考えたときに、スパムメールか通常のメールかを判断するのと同じ要領で役を読む（例えば、混一かどうかなど）ことが出来るのではないかと思う。
また鳴きの仕掛けはかなり個人ごとにクセが出る傾向にあるので、これまたベイズ理論の応用例らしいグーグルパーソナライズド検索と同じ要領で個人のクセを読むアルゴリズムが作れるのかもしれない。（妄想です）
個人のクセを読むってのは今の段階では完全に妄想レベルだけれど、役読み（まずは染め手読み程度）はチャレンジする価値が十分にあると思ってる。

ただ、実現に関して現時点で問題点が３つほど思い当たる。

ひとつは条件付けの問題
英語メールのスパムフィルタの場合は単語がそのま条件付けとして使えたわけだけれど、麻雀の場合は自分で何が条件付けの因子となりえるかを考えなければいけない。例えば、塔子落としとか、捨てパイの偏りとか、鳴き方（例えばオタ風から先に鳴いたとか）、対子場なんかが条件付けの因子になるのかもしれない。
まずはどういう因子をリストアップするかを検討する必要がある。ここら辺は麻雀上級者の経験を頼りにするしかなさそう。麻雀本でも読み漁ってみるかな。(こういった条件を自動的に探せないんじゃあベイジアンフィルタとは呼べないんだろうな。)それと、因子と結果の因果関係がスパムメールよりはずっと弱い気がしてて果たして効力があるかどうかが分からない。英語SPAMメールならSEXYって書いてあれば90%はスパム確定っていえちゃうらしいけれど、そこまで強いファクターは麻雀には無いだろう。
次は、データ解析の問題、東風荘のログを解析するプログラムを作らなければいけない。これだけで結構大変な作業になりそう。もちろん、データも必要。いままではとつげき東北氏のページのデータを使わせてもらっていたけれど、あそこのデータはクイタンなしの第一東風荘のデータが殆どなのであまり鳴きについては役に立たなさそう。泉レイ氏のデータを使わせてもらってそれに自分が打った超ランデータを足した程度の数量で果たして足りるかどうか……

３つ目は私自身の知識の問題。私は後づけ野郎なんで、やりたいことが見つかってから慌てて勉強を開始するタイプ。ぶっちゃけベイズ理論なんて殆ど理解して無い。昨日今日でスパムメールフィルタの理屈がようやく理解できたところ。

とりあえず、だいぶ前にAmazonで買ったベイズ統計学入門の本があるんて、暇を見つけて読んでみるつもり。
でも入門書と言う割には結構難しい数式が多いな、この本……Orz
2006/2/2追記
ぱっと目、難しそうな記号を使った数式が多いけど、じっくり読んでみると、結構当たり前な式が多くて、それほど難しくも無い。式の後に文章で親切な解説があるし、具体例もあるので結構イメージしやすい。実はかなりの良書な気がしてきた。
追記終わり

ちなみに、ポールグラハム方式のスパムフィルタはパラメタの決め方を山勘(?)でやってる部分があるので、こんなのベイズ理論じゃないって言う人もいる。
（Amazonの「ハッカーと画家」の書評にもあるし、別の場所でも批判されているらしい）。
でも、これは、単純に普通のメールをスパムに間違えるのはスパムを普通のメールと判断するよりリスクが大きいから、安全な方向に倒しただけでしょう。
麻雀の場合、遊びなんで、そうったパラメタいじりは多分それほど必要なら無いんじゃないかと楽観的に考えてる。

参考資料:
タグ「ベイズ」を含む注目エントリー