麻雀の待牌探索の基本方針

一度書きかけたらずるずる追記

やっぱり好きなのかも。こーゆーの。
なつかＣ。
「麻雀って楽しいよね」（咲）とゆーか、麻雀ゲームの実装の課題としては中難易度くらいに相当する待牌探索でこれだけ語りうることがあるんだから、面白いです。前の理牌の話とかステートマシンの話が低難易度、NPCのAIが高難易度（まあ、向聴数が改善するように打って、ぼうてんそくりーぜんつっぱ、でも割と強いんだけどさ、それは人間ぽくないので、人間っぽくかつ強いAIのために何を演算するか、が難しい）というような広がりもあるし。しかも、コンピュータ麻雀の突っ込んだ解説書とかはまだないので（嚆矢は出たが、売れなかったので類書が出なかったパターンだと思われる）ネタの宝庫だ。丁寧にやれば、向聴数計算までで1冊、それなりにごつい本になる。（下記は丁寧じゃないのであしからず：答えだけ言ってる感じ）

データ形式

麻雀の手牌の表現方法には色々あります。

/*(1)牌ひとつずつの種類を配列に納める方法*/
   t_pai pai[14];
   int painum;
/*(2)牌の種類ごとに所持枚数を配列に納める方法*/
   int painum[9+9+9+3+4+1];/* ダミーが1要素含まれる */
   int pairednum[4];/* painumと重複して、赤牌の枚数だけを格納（ダミーが1要素含まれる） */
/*(3)木構造みたいな扱い方もあるのかしら？よくわからんけどきっと非効率*/
   t_pai_node top;
   top.same(), top.more(), top.less(), //とか？ 要はトップレスと言いたかった。

(1)は表示系や模打フローで扱うのに向いていますが、この記事を最後まで読んで頂ければ分かるように麻雀の待ち牌探索などの分析には(2)の方が高速です。(1)のままでも、頭の良いやり方をすればそれなりに高速にしうると思いますが、一歩一歩ifを噛まして走査しなくてはならないので、コードが複雑になります。和了候補牌の効率的なリストアップは困難ですし、面子分解はswapを繰り返してソートのようなやり方をする必要があります。ただし、要素数が小さいので、そこだけはメリットですが、いかんせんTRYが深くなるのを避けられず、パイプラインに乗りにくそうなアルゴリズムになりますので、まあまず(2)の勝ちでしょう。異論は検討するけどね。そして、多くの麻雀ソフトがそれをやっているような気がします。

(1)から(2)を生成するのは容易なので、牌姿分析するとき以外は(1)で管理しておいて、牌姿分析の時にざっくりと(2)を生成するのが適切だと思います。(2)でダミーを用意しているのは、鳴いて枚数が少ないときにも分岐ジャンプなしで(1)→(2)を行うためです。つまり、最後の要素はnull牌の枚数ですね。

また、別の最適化のために、painum[12+12+12+12+1]とすべきかも知れません。それについては、後述します。

鳴き牌については、ここでは触れませんが、これとは別管理すべきでしょう。役判定用の一次配列（刻子・順子データ）にのみ、事前に反映させておきます。

以下、(2)のデータ形式を前提として、書かせて頂きます。

某所につけたコメントの転載

麻雀の待牌探索には大きく分けて2つの方針がありまして、

A【発展性はあるが、待牌特定のためには複雑になりがち】
try 単騎（1枚～3枚の所有牌）
　両端から刻子優先で刻子・順子を取り去って、取り切れれば単騎待ちOK
try 雀頭確定（2枚～4枚の所有牌）
　両端から刻子優先で刻子・順子を取り去って、余ったら、それが待ち形
　最後に残った待ち形を上記で取り去ったメンツと融通しあって派生形を求める
　　例えば最後が45なら、取り去った順子で3か6が含まれるものとやりとり
　　　例えば678があるなら、（45・678）→（456・78）と読み替える。
　　　　さらに78から以下同文
　　　例えば234があるなら、（45・234）→（345・24）と読み替える
　　　例えば66が雀頭なら、（45・66）→（456・6）の単騎待ちと読み替える
　　　例えば666があるなら、（45・666）→（456・66）で、雀頭とのシャボ待ちと読み替える
　　　ご想像の通り、ループしないように探索してちょんまげ
4枚使いの待牌を待牌から取り除く

B【待ち形の特定には一手間要るが、待牌を発見するだけなら高速】
try 所有牌とその前後の牌を加えてみる
  try 雀頭確定（加えた結果が2枚～4枚の所有牌）
　  両端から刻子優先で刻子・順子を取り去って、取り切れればOK

B'【上記の待ち形の特定の一手間】
　　加えた牌が雀頭に含まれている→単騎
　　加えた牌が順子に含まれている→含まれ方により、辺張・嵌張・両面
　　加えた牌が刻子に含まれている→シャボ
　　3連刻形なら順子に読み替えたときの待ち形も追加
　　上記は複数の解釈ができる → 符計算＆役判定して、最も点数の高い解釈をすべき
　　　　　　　　　　　　　　 → ツモ符は待ち形で変わるので、最低限ツモフラグが可視でないといけない
　　　　　　　　　　　　　　 → 点数を確定させるなら、自風・場風・リーチ状態・ドラ等も可視
　　　　　　　　　　　　　　　　　　→ これはAでも同じこと。なかなか綺麗にモジュール化できない
　　　　　　　　　　　　　　　　　　　 ゲームデータの多くを可視のままここに突っ込む必要がある

待牌を特定して、役判定する目的ならBがスムーズです。向聴数や和了形までの確率を加味した距離の計算などは、Aの延長線上にありますので、多くの場合、両方実装することになるでしょう。なお、Bで待ち形の特定をした上で、待ち形毎に、ツモ・出和了の別もフラグで渡しておかないと、ツモり3暗刻の判定ができなかったり、ピンフの判定を間違ったりします。コメントにも書いたように、いずれにせよこの種の処理は、ゲームデータ丸ごと（正直、河以外のほとんど全部を渡さないと）完結させられないとゆー、とても厄介な代物なのです。

で、最適化だ！

で、これをどうジャンプ最小で、かつL1キャッシュに収まるメモリしか使わずに書くか、というのがポイントなわけですが、というのは、麻雀ゲームのサーバを書くなら、処理のほとんどは牌姿の分析をしていることになるので、こいつが速ければ速いほど多くの人数を収容できるわけです。ステートマシンは、鳴きと和了の複合とかダブロンとか暗カンとかチャンカンとか、そういう細々としたルールに丁寧に対応するのが面倒なだけで（とは言え、ルールを可変にしようとするとえらく面倒なのは確かですが）処理時間を食うようなものではありません。それこそ今なら、ロビーとゲームフローはNode.js＋react.js＋socket.ioでも何とかなるんじゃないでしょうか。しかし、牌姿分析だけは、C++バインドを用いて低レベルなコーディングをしないと折角のC10Kには対応できません。

向聴数は、ツモ1回につき高々1しか減りませんので、正しい向聴数計算ができれば、サーバでの牌姿分析は数巡に1度でOKです。（向聴数-1）巡は、牌姿分析をスキップすることができます。そしてこれが、最も根っこの枝刈りで、最も効果的です。それを踏まえた上で、さらには向聴数計算を含め、和了判定、聴牌判定、リーチ可能判定などを最適化します。なお、向聴数計算は、七対・国士・面子手の3通りの計算が必要ですが、面子手の向聴数はここで説明する内容を超えた枝刈りの工夫が必要になります。というのは、塔子・対子・面子の組み合わせに分解して、その数から向聴数は算出できるのですが、その分け方は案外多義的で、下手なやり方をすると深い探索に陥ったり、間違った値を得てしまうという厄介なものなのです。気が向いたらそのうちそれも書いてみようかと思いますが、まずは、基本からはじめます。

  a[0]>=3なら
　[ a[0], a[1], a[2] ] = [ a[0]-3, a[1], a[2] ] /*端っこから刻子を取ってみる*/
  それ以外なら
　st = min(a[0],a[1],a[2])としたとき、
　[ a[0], a[1], a[2] ] = [ a[0]-st, a[1]-st, a[2]-st ] /*端っこから順子を取ってみる*/

/*もちろんこの後、
a[1], a[2], a[3]
a[2], a[3], a[4]
a[3], a[4], a[5]
a[4], a[5], a[6]
a[5], a[6], a[7]
a[6], a[7], a[8]
に対して順次同じ処理を施すのですよ。
刻子は、
a[7]
a[8]
に対しても同じ処理を施すのですよ。
後述のメモリ配置で字牌処理をやるのなら
a[9]
も刻子処理が必要です。
*/

という計算を、分岐無しでビット演算等の組み合わせやテーブル参照で行い、引けたものの記録が残ればいいわけです。まあ、「影響が残らないで欲しいものは0を引く」というのが大体の場合の答えです。そして、結果の記録は、とりあえず書いて、記録を残したいときだけ、ポインタアドレスへの増分が1になるようにし、それ以外の時はポインタアドレスに0を足しておけば、いずれ上書きされるか最終的に無視されるのです。

上記の冒頭を単純に、ジャンプなしに直すと、下記の通りです。

sample

if(a[0] >= 3)
{
    a[0] -= 3;
    *result++ = pai_1pin_ko;
}
//  ↓
int kotsu[] = {0,0,0,3,3};
*result = pai_1pin_ko;
result += kotsu[a[0]]>>1;
a[0] -= kotsu[a[0]];

みたいな感じ。初め論理演算で書いたら間違えちったので、腹が立ってテーブル参照に書き換えた。このサイズの配列がキャッシュに乗らないことはあり得ないので、充分速い。多分論理演算より速い。

ついでに追記

上の奴はテーブル参照の勝ち。小さなテーブル参照というのはアホのように速いです。ですが、minなんかは有名な算法があり、論理演算の勝ちです。それがこれ。この、31ビット右シフトというのは、正負に分かれる演算を使って3項演算子みたいなことをやるための定石です。ジャンプ排除のためにはとってもよく出てきます。

sample

st = min(a[0], a[1], a[2]);
    /*↓*/
/*こちらこそビット演算。有名な奴だ*/
int ab = a[0] + (((a[1]-a[0])>>31) & (a[1]-a[0]));
int st = ab + (((a[2]-ab)>>31) & (a[2]-ab));
assert((0x80000000>>31)==(-1));

例えば、正数チェックなんかをする際には、((-a)>>31)とか、そういうことをします。一応環境依存なので、通用するかどうかを判定するassertも載せておきました。麻雀での応用で言うと、和了候補牌を列挙するときの所有牌とその前後の牌、と言ったとき、

p[0]=a[1]*a[2],p[1]=a[2]*a[3]..., 
q[1]=a[2]*a[0],q[2]=a[3]*a[1]..., 
r[2]=a[0]*a[1],r[3]=a[1]*a[2]..., 
p[0]+=q[0]+r[0]+a[0],p[1]+=q[1]+r[1]+a[1]...
p[0]=((-p[0])>>31),p[1]=((-p[1])>>31)...

とやった上で、非零になった牌を候補にすれば良いのです。

なお、上のコードで、a,p,q,rのバッファはわかりやすさと美しさのために書いただけで、本当はバッファは元データaと結果保持用pの2本だけで良いですよ。

ちなみに、前後の牌とは言っても、もし2筒が手牌にない場合に2筒が和了候補牌になり得るかを検討する時、3筒だけあって4筒も1筒もなかったら和了候補牌にはなり得ないでしょ？だから、隣ふたつをみるのです。

ここで、乗算と加算が出てきますが、値の大小に意味はありません。0×0=0,0×正数=0,正数×0=0,正数×正数=正数、それから、0+0=0,0+正数=正数,正数+0=正数,正数+正数=正数、という、いわば論理積・論理和のようなものとして使っています。あと、この場合、pとrには同じ式が7対出てきますから、そのへんをうまく流用するように組み立てます。それは、コンパイラに任せても良いかもしれませんね。

ついでに中学生っぽい最適化をするとね。単純な式変形で、こうします。

p[2] = (a[0]+a[3])*(a[1]+a[4])-a[0]*a[4]+a[2];

計算量自体は、元のp[2] = a[0]*a[1]+a[1]*a[3]+a[3]*a[4]+a[2];ってのと変わらないけど、後で出てくる「筋 mod 3」というのの計算の途中経過を利用してここも計算するという邪悪な手もあります。そこまでかりかりにやるより、メモリアクセスをL1キャッシュ内に収めて、ジャンプを減らし、パイプラインを回す方が有効なんですけどね。もう可読性なんてなにそれおいしーの状態ですな。この処理が「筋 mod 3」と近接してる場面があるのよ。

既に4枚使いになっている牌を検討から外すのは、4枚使いは大変頻度が低いので、当たり牌を特定してから、後で排除する方針でも良いかも知れませんね。4枚使いにはちょっと笑える話があって、「１１１１２３４４４４」で流局後ノーテン扱いになった、というバグ報告があった覚えがあります。いや、当たり牌、世の中にないっす。話はどんどん逸れるが、ノベタン形には似た話があって、3フーロで「３４５６」で「３」が上家から出て、「ロン」の選択肢は出たのに「チー」は出なかった、とかね。食い替え確定だから鳴けないよね。

そして話を戻すが、雀頭にできるかどうかの判断なら、((2-a)>>31)ですね。そんなに素直に判定して良い場合ばかりではないのだが……。次へ！

大技「色別 mod 3」

さて、上記の和了候補牌の事前検証は字牌も入れて高々34種類。事前検証で試行すべきとされるのは、手牌枚数の制約があるので高々25種類。もし聴牌していないときはスキャンしないことにすると、20種類より多い候補が見つかった場合は絶対ノー聴なので枝刈りできます。が、そんな絞り込みがばかばかしくなるくらい凄い絞り込みが、次に挙げる「色別 mod 3」による絞り込みです。

和了候補牌がどの色にあるか、などは、色別の枚数で、実はだいぶ絞り込めます。各色の保有牌枚数のmod 3をみたとき、まず、和了形では、雀頭がどこかにあって、それ以外は全て3枚ずつの面子になっているので、(2,他は0)という組み合わせになっています。面子手の時は絶対にそうです。

では聴牌の時というのはどうかというと、面子手から1枚引いた状態なので、2のところから1枚引くか、0のところから1枚引くかで2パターンあります。つまり、(1,他は0)、(2,2,他は0)の2通りの時しか聴牌ではありません。そして、当たり牌を引いたところは非零になっていますので、非零のところに当たり牌がある可能性があるということになります。パターン毎に整理すると、(1,他は0)の時には雀頭も当たり牌と同じ色、(2,2,他は0)の時には雀頭と当たり牌が異なる色になってきます。ここまで来ると、当たり牌候補・雀頭候補がだいぶ絞れてきます。

この絞り込みの過程でジャンプを抑制することにはあまり意味がないので（とは言え、テーブルは上手に使った方が良いです）、ifも適切に使ってパターン分けしましょう。1の時には、「try 当たり牌」×「try 雀頭候補」を行う必要がありますが、2,2の時には、片方で「try 雀頭候補」＋残りで「try 当たり牌」を行うことになるので、それに特化した判定コードを書くと、さらに最適化できます。（個人的には前者を積探索、後者を和探索、と呼んでいます）

このように判定した結果を元に、開始ポインタを挿げ替えてつっ走るように作れば良いのですが、ただ1点、異なる色に対する検証処理をインターリーブして、パイプラインを最大限に活用しようとしたとき、それぞれの色を指すポインタの値域が重なり合わないことはコンパイラには分かりません。ですので、手動でインターリーブしないといけないのです。とは言え、だいぶ条件の整った混一色の和了判定みたいな状態になっているわけですから、根性があれば超速く書けますね。このmod 3を使う方法は、他の牌姿分析（向聴数算出など）でも枝刈りに頻出する基本的なアイディアのひとつです。

因みに余談ですが、リーチ可能判定は、1枚ずつ捨ててみて判定する、というのでも構わないのですが（クライアント側で計算させる方針ならなおさらです）安全のためにそこまでサーバ側で判定してクライアントに通知する形にするならば、「try 捨牌 try 和了候補牌」のループは案外深いので、最適化したくなります。また、NPCをそれなりの数サーバで運用するなら、それは必須になります。

リーチ可能判定、すなわち14枚状態での聴牌判定だと、「色別 mod 3」は、(2,他は0),(1,1,他は0),(1,2,2,他は0)の3通りしかないことになります。そして、捨牌候補の色も、もうパターン毎に特定できましたね？　1があれば1の色、さもなくば0,2の色が捨て牌候補です。さらによく考えると、捨て牌の色は、さらに限定できます。「完全面子分解」を「Tris」と呼ぶことにすると、
　1,1なら、
　「ある1が積探索に成功、別の1は1枚切ってTrisで、他の色もTris」というのが条件です。同様に、
　1,2,2なら、
　「2,2は和探索に成功し、唯一の1は1枚切ってTrisで、他の色もTris」、
　2なら、
　a「2は1枚切って積探索に成功し、0は全てTris」か
　b「2は待牌込Trisで、ある0は1枚切って雀頭込Tris、他の色はTris」か
　c「2が雀頭込Trisで、ある0は1枚切って待牌込Tris、他の色はTris」
となります。大変そうですが、コードを書いてみると、どんどん絞り込めて良い感じです。「雀頭Tris」⊃「待牌Tris」なので、待牌Tris判定の中でどのカテゴリに属するかを一度に調べてしまえば良いのです。（すなわち、待牌Trisかつ雀頭Tris、非待牌Trisで雀頭Tris、どちらも不合格、の3通りの出力ということ：後述の「筋 mod 3」も参照）そして、和了からのフリテンリーチである可能性を先に判定して別扱いにしておけば、2のケースはもう少し絞れて、0が全てTrisである場合、和了形でないときには必ずaに属します。なので、それ以外の場合には、Tris判定がNGである0が必ず1つ存在し（2つ以上存在する場合、ノーテンです）、b,cは色を固定して一気に判定することができるのです。というわけで、「try 和了候補牌」に相当する「待牌Tris判定」を行わなければならなくなるケースはものすごく絞られました。高々2回です。

そして、パターンの組み合わせ毎に「色Aの完全面子分解と、色B,Cの和探索」などを混ぜて探索するようにすると、パイプラインに乗りやすいコードが書けるわけです。ここで、字牌の順子を判定しないようにするための工夫は必要ですが、萬筒索字それぞれ12要素ずつにして、
　一二三四五六七八九◆◆◆
　①②③④⑤⑥⑦⑧⑨◆◆◆
　１２３４５６７８９◆◆◆
　東南◇西北◇白発◇中◆◆
みたいにメモリ上に配置するのも一案です。刻子探索をa[9]まで行い、当たり牌候補算出の後に◇を0で上書きすればOKですね。Tris判定・積探索等の高速アルゴリズムがそのまま例外無く使えるようになるメリットの方が、多少のムダな処理が発生するロスよりも上回るはずです。ここまでなら10要素で良いのですが、次節の「筋 mod 3」を分岐抑制して使うなら、12要素でないといけませんね。ま、どうせ諸々の計算量が増えるわけではなく、「筋 mod 3」の和を求める時に触るだけなんで、確保しちゃっていいんじゃないすかね。

「筋 mod 3」だって使えます

ここ、超書き直した。編集履歴は見ないでね。はずかしーから（はあと）。「色別」の時と微妙に事情が違うので、ややこしいんですってば。というわけで、気を取り直して丁寧に行きましょう。

「筋 mod 3」とは

int suji[3];
suji[0] = (a[0]+a[3]+a[6]) mod 3;
suji[1] = (a[1]+a[4]+a[7]) mod 3;
suji[2] = (a[2]+a[5]+a[6]) mod 3;

とし、s( suji[0], suji[1], suji[2] )等のように略記することにすると、刻子はどこにあってもs(0,0,0)、順子はどこにあってもs(1,1,1)であるから、Tris合格であれば、常にs(a,a,a)となる。ここまでOK？

で、13枚系(n*3+1)であれば、足して paisum mod 3 == 1 となるはずなので、常に順不同ながら、s(a,a,a+1) の形になる。雀頭を取り去ることは、2枚同じ牌を取り去るということなので、s(-2,0,0) = s(+1,0,0) 、ツモ牌を仮定するのも、s(1,0,0)。（どの筋かはまだ未確定）

s(a,a,a+1)に、重複しても良いので、2箇所に1を足して s(a',a',a')にするためには、

s(a +1,a +1,a+1)か、s(a,a,a+1 +1+1)のどちらか。

OK。これで積探索に使えるね。s(a,a,a+1)のa+1に雀頭を仮定したら、待牌も同じ筋にある（だから、ここは手牌に1枚しかない場合でも雀頭TRYが必要になる）。そして、aのどちらかに雀頭を仮定したら待牌は異なるa筋にある（だから、この場合の雀頭TRYは既に手牌に2枚以上あるときしか試せない）ということだ。

だから、雀頭をピックアップするときに待牌をトライすべきなのはどの筋かを記録しながらやる形にすれば、常に雀頭ごとに3回のTrisで良くなる。Trisの判定を、雀頭が-1枚という壊れた状態でちゃんと偽判定できるようにしとかなきゃいけないけど、高々9回*Tris3回、平均的には3～4回×3回のループなので、エンロールしてテーブルジャンプで積判定ができるということだ。テーブルジャンプでの分岐予測もある程度当たるだろう。3割くらいかな？

あーすっきりした。いつもどおりと言っちゃなんだが、最初てきとーなこと書いてまっことすまんかった。

話は逸れるけども

若い頃、コンパイラへのヒントで入力の定義域を与えれば、狂ったような最適化ができるかも、と夢見たことがありましたが、自分で定義域を利用した狂った最適化を色々やってみると、機械にやらせるのはあまり有望ではないとも思うようになりました。しかし、CPU律速の処理もまだまだあるようだし、クロックスピードは理論限界間近ということを考えると、もしかしたらなにがしかの活路になるかも知れません。用途は限られるでしょうから、CとかHaskellとか、それぞれ手続き型・関数型の基礎的な言語の拡張ということになりましょうが、言語実装者の方、「定義域利用による最適化」というテーマ、どうでしょう。