claustrophobia

一般λがなんか書くとか

Egisonで国士無双の判定(及び「速い」Egisonコードの書き方について少し)

RubyKaigiの実況TL (Egison at RubyKaigi 2014 - Togetterまとめ)にて、
Egisonで麻雀の役判定する話になったとき「国士無双は?」みたいな声を2、3見掛けたので、今更書いてみる。

;; tileの定義は公式のサンプルコードと同じ。

;; 么九牌の判定
(define $yaochu
  (pattern-function []
    (| <hnr _> <num _ ,1> <num _ ,9> )))

;; 全13種の么九牌のリスト
(define $all-yaochu-list
  {<Hnr <Haku>> <Hnr <Hatsu>> <Hnr <Chun>>
   <Hnr <Ton>> <Hnr <Nan>> <Hnr <Sha>> <Hnr <Pe>>
   <Num <Wan> 1> <Num <Wan> 9>
   <Num <Pin> 1> <Num <Pin> 9>
   <Num <Sou> 1> <Num <Sou> 9>})

;; 国士無双の判定
(define $kokushi-musou
  (pattern-function []
    <cons (yaochu) ,all-yaochu-list>))

つまり、「アタマの么九牌」+「13種類の么九牌」で正しく判定できる。

できるんですが、実は速度的に若干の問題を抱えているというか、このコードだと
「アタマを選んでから残りがall-yaochu-listとマッチするかどうかを判定する」という挙動になるので、
例えば手牌全部么九牌だけど国士無双じゃないみたいなコードは一々全部の牌をアタマにしたケースを探索してしまいます。

なので、こう書いたほうが速いはず。

(define $thirteen-orphans-fast
  (pattern-function []
    <join ,all-yaochu-list <cons (yaochu) <nil>>>))

multisetにはsnocがないのでjoinを使って、先に「13種類全ての么九牌がある」かどうかを判定して、残った一牌がアタマとして正しいかどうかを判定するパターンにしています。こうすれば、13種類の么九牌がなかった時点、或いはアタマが不適切(つまり么九牌じゃない)だった場合に即座に失敗してくれます。

しかしなんというか、こんな風にマッチャーの挙動が計算量に割とクリティカルに作用*1してくるケースが生じてくるのは、Egisonプログラミングの難点の一つなのかなぁと思いました。要は、Egisonの処理系の速い遅いの問題はともかく、コーディングする側が「速度」を意識してパターンマッチを書くのが結構難しいんですよね。麻雀の役判定ぐらい複雑なパターンマッチになると、その辺はどうしても無視できなくはるはずです。

たとえば、サンプルコードで七対子の判定パターンがありますが、
あれもたとえば手牌に3対子(aa, bb, cc)しかない状態で判定を走らせると、

  • th_1 = aa, th_2 = bb, th_3 = cc
  • th_1 = aa, th_2 = cc, th_3 = bb
  • th_1 = bb, th_2 = cc, th_3 = aa
  • th_1 = bb, th_2 = aa, th_3 = cc
  • th_1 = cc, th_2 = aa, th_3 = bb
  • th_1 = cc, th_2 = bb, th_3 = aa

の6通りの失敗パターンを通るわけですが、一つ目失敗した時点でもう全体のマッチ失敗が確定するはずなんで、探索を切っていいはずですよね。

そういえば、昔のEgison*2にはcut patternってのがあって、

(twin !$th_1 (twin !$th_2 ...

みたいな感じで、th_1, th_2にマッチしたら、その一つ目の結果でダメなら探索を切るということができました。
要はつまりPrologのカット節と同じ感じで「バックトラックを行わない」ことを指定できたんですが、もう復活はしないのかな。

*1:今回のコードは前者でもまあまあ速いですが。

*2:少なくともversion 2にはあった。