日本式打天九の牌のデータ構造

2023年11月にSteamで「日本式打天九」というゲームをリリースしました。
本記事は日本式打天九で実装した牌のデータ構造を紹介するという、かなりニッチな内容の記事になります。
ちょっとだけネタバラシすると、複数枚の牌の組み合わせを一つの数に対応させるという、ちょっとトリッキーなことをしています。

そもそも打天九とは

詳細はググっていただくとして、本記事を読むにあたって必要最小限のルールを説明します。
打天九は麻雀のように牌を使って4人でプレイするゲームです。
一見すると麻雀のように見えますが、ルール自体は大富豪に似ていて、前の人が出した牌よりも強い牌を出した人が基本勝ちです。

牌のデータ構造

打天九では天九牌と呼ばれる牌を使います。
牌は文牌と武牌の2種類があり、その内訳は、文牌11種類 x 2の22枚, 武牌10種類の合計32枚です。
この32枚の牌を最初に4人に分配するので、手牌は最大8枚で構成されます。
また最大4枚の同時に出せる牌の組み合わせがあります。

トランプと同じようにランクとスート(文牌/武牌)がありますが、トランプの場合はランクとスートを指定すると一意にカードが定まる一方で、天九牌では区別できない同一の牌が2枚まで含まれます。
たとえば文牌で一番強い「天」はゲーム中2枚存在し、この2つは絵柄が全く同じなため区別できません。
そして大富豪と同様に、同じランクの牌2枚の同時出しや、特別な組み合わせの同時出しがあります。

これらを考慮して牌のデータ構造を考える必要がありました。

すぐに思いついくのは

public enum　ナイーブ天九牌:
    NONE = 0,
    銅錘六 = 1,
    高脚七 = 2,
    紅頭十 = 3,
    ...
    八2 = 19,
    九1 = 20,
    九2 = 21,

このように区別できる牌の種類に整数を順に割り当ててenumとして扱い、手牌はこの配列にすることかと思います。

ぶっちゃけこれで十分なんですが、たとえばチェスなんかはbitboardと言って駒のデータ構造はゴリゴリに最適化されています。
日本式打天九でも最適化されたデータ構造を考えてみました。

日本式打天九で実装した方法

日本式打天九でもenumを使っていますが、連続する整数ではなく素数を割り振っています。

public enum　天九牌:
    NONE = 0,
    銅錘六 = 2,
    高脚七 = 3,
    紅頭十 = 5,
    ...
    八2 = 67,
    九1 = 71,
    九2 = 73,

そしてここがキモなのですが、
複数枚の牌の組み合わせを対応する素数の積で表します。

たとえば「銅錘六=2」と「高脚七=3」の組み合わせの場合は 6(= 2 x 3) という整数を対応させます。
数学好きの方はこの時点で素数を使った理由が分かったかと思います。

打天九では模様の異なる牌は区別されますが、牌の組み合わせについて、その順番は区別されません。これは多くのゲームで共通すると思います。大富豪や麻雀でも[1,2,3]と[2,1,3]は同じ意味になります。ソートされてない方は、ちょっと気持ち悪いくらいの違いしかありません。

この順番に依存しないという性質が整数の積に対応しています。 2 x 3 も 3 x 2 も答えは同じ6になりますよね。
配列でもつと [2, 3]　になるところを、 6　という一つの整数で表せるのでスッキリしました。それでいてゲームルールが牌の順番に依存しないおかげで必要な情報も落ちていません。
たいしたことなさそうに感じますが、たとえば毎ターンの手牌情報をデータベースに格納することを考えてみてください。RDBだとすると手牌の数は最大8枚あるので列数が8つ必要になり、最初のターン意外はnullとかNONEを入れることになり無駄ですよね。麻雀や大富豪なんかはこの辺どうやっているんでしょうか？

素因数分解の一意性

掛け算で表すとスッキリするのは分かったと思います。
ではどうしてわざわざ素数を選んだかというと、それが素因数分解の一意性になります。

たとえば紅頭十には5という素数を割り当てていますが、これを素数ではない4にしてみましょう。
銅錘六 = 2 と紅頭十 = 4 を持っている場合、その積は8になります。
この8という数から、逆にどの牌の組み合わせで構成されているか分かるでしょうか？
8を因数分解してみると、
8 = 2 * 2 * 2
8 = 2 * 4
8 = 8
このように3パターンも出てきてしまいました… 銅錘六が最大2枚しかないことを考えると最初のパターンは消せますが、それでも2パターンあり一意に定りません。そもそもそんな判定自体したくありません。

では素数の場合はどうでしょうか？
銅錘六 = 2(素数) と紅頭十 = 5(素数)に対しては 2 * 5 = 10という数になりますが。 10を因数分解するとき 10 = 2 * 5 以外のパターンはありません。

素数の積で表せる数のことを合成数といいますが、合成数を素数に因数分解したとき、そのパターンは1つしかないことが知られており、これを素因数分解の一意性と言います。
天九牌を素数で表し、その組み合わせを積で表すことで、元は何の牌で構成されていたかを正確に復元することができるのです。

練習問題
[68231を素因数分解せよ]
こたえ 31x31x71
これは日本式打天九では[天][天][九]という牌の組み合わせに対応しています。

特定の牌の組み合わせが手牌にあるかどうか?

最大8枚の手牌の中に特定の牌の組み合わせがあるか？　という判定を日本式打天九では何度も行っています。
いまのデータ構造だとこの種の判定をとても簡単にできるようになります。

その方法とは手牌を判定したい牌の組み合わせで割り切れるかどうかチェックするだけです。

 if (手牌 % 牌組 == 0)
 {
    // あるとき

 }
 else
 {
    // ないとき

 }

もしこれを配列で実装していたとすると、ループ処理が必要になります。

他のゲームにも応用できるか？

この方法の弱点は積で表現するために、その数が簡単に大きくなることです。
都合の良いことに、打天九は出し方が最大4枚の組み合わせなので、これはint型(32bit)で収まりますし、手牌が最大8枚なので最大の数は133869006807307になるのですが、これはlong型(64bit)に収まります（なるべく小さい値に収まるように武牌を文牌よりも大きい素数に対応させています）。

しかし麻雀の場合は打天九よりも牌の種類が多く、手牌の数が多いためlong型でも大きくなりすぎて表現できません。
そのため、この方法は牌の種類が少なく、使用する枚数も少ないゲームにしか適用できません。
でもまあ、そんなゲームではここまで最適化しなくてもパフォーマンスはあまり気にならない、というオチになりそうですね。
なので実用性については限定的かもしれません。他に用途が見つかったときは是非教えてください。

おわりに

オンラインマルチプレイではプレイヤー間でデータを通信する必要があります。
そんなときにも配列ではなく一つの数を送ればいいだけなので非常に簡潔に実装することができました。
このデータ構造の用途はかなり限定的だと思いますが、少なくとも日本式打天九の実装にはかなり刺さりました。
何より実装していて楽しかったです。順序の交換可能なものってなんだっけ？　という切り口で考えて試しに実装したあと、牌の存在判定にも使えることに気付いたときはこれしかないと思いました。
こんな扱うのに解説が必要なデータ構造なんて、仕事で使うのは厳しいかもしれないので、小規模開発ならではの楽しさ・醍醐味の一つだったと思います。
たまには楽しいプログラミングもしたいですよね…

天九牌のデータ構造