麻雀の待ち判定アルゴリズム。
http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.html
実は以前考えたことある*1
愚直な場合わけをしてたけど、再帰で書き直したらすっきりした。 OpenSourceコミュニティに貢献するという想定で英語でコメント＆変数名を書いてある。コアとなる判定ルーチンは以下だけ
// Check if given hand has one pair plus (4-ntriplet) triplets // May call itself recursively. // // input: // Hand hand: hand data to check // int start: hand has no triplets nor pair in a range 0 .. start-1 // int pair_idx: -1 if pair is needed. When we already have a pair, pair_idx= piece id // int ntriplet: number of triplets we already have bool Win(Hand hand, int start, int pair_idx,int ntriplet) { int i=start; bool result = false; if(ntriplet==4 && pair_idx !=-1) { // Win! return true; } while(hand[i] ==0) { // no more pieces in hand if (hand[i] == -1) return false; i++; } //fork: possible pair found // hand[i]=3, 4 case is handled after 123-type is removed if(hand[i] ==2 && pair_idx == -1) { hand[i]-=2; result |= Win(hand, i+1, i, ntriplet); hand[i]+=2; } //fork: possible 111-type found // hand[i]=4 case is handled after 123-type is removed if(hand[i]==3) { hand[i]-=3; result |= Win(hand, i+1, pair_idx, ntriplet+1); hand[i]+=3; } //fork: possible 123-type found if(hand[i+1]>0 && hand[i+2]>0 ) { hand[i]--; hand[i+1]--; hand[i+2]--; result |= Win(hand, i, pair_idx, ntriplet+1); hand[i]++; hand[i+1]++; hand[i+2]++; } return result; }
http://d.hatena.ne.jp/ita/00010416/p1
待ちを探すというより、「１−９それぞれ一枚仮想的に持ってきて和れるか」とした方が分かりやすい。
各牌を何個持っているかの histogram bin で手を記憶しているけど、ソーズ、ピンズ、字を混ぜるときでも配列を拡張して個数を入れて、マンズとソーズ、ソーズとピンズの間に１つ空白を入れて番兵の０を入れておけば同じコードで判定できる。字牌も２つ間隔で０を入れればいいけど、こっちはIF文でシュンツの判定をoffにしたほうがいいかも。
１牌の無駄もあってはいけないので、もっと探索を減らせるかもしんない。
