LoginSignup
0
0
@youce

ドブル (Dobble / Spot it!) 自作 (1): ドブルデッキの構築

Last updated at Posted at 2023-09-24

はじめに

Qiita 初記事です。よろしくお願いします。

ボードゲーム ドブル (Dobble / Spot it!) を Python 実装した dobble-maker の解説です。

本記事ではドブルデッキの構築について説明します。

  • ドブルデッキの構築
    • 任意の 2 枚のカードを選んだ時に、必ず共通するシンボルが 1 つだけ存在するような組み合わせを決定する
  • カード内でのシンボルのレイアウト
    • シンボル間の重なり無く、程よくランダムに配置する
  • 生成ツールの紹介
    • 画像ファイルから印刷用PDFまで生成するツールの紹介
    • 仕組みはいいから作りたい！ という方はこちらです

アルゴリズムの解説

条件

カードゲーム ドブル(Dobble)の数理によれば、カード 1 枚当たりのシンボル数を$N$とした場合、必要な全シンボル数およびカード数は $N * (N - 1) + 1$ になります。
また、$N$は「素数の累乗 + 1」であることが条件とされています。

以下では、$n = N - 1$として、$n$が素数（$2, 3, 5, 7, ...$）の場合と、素数の累乗（$2^2, 2^3, 3^2, ...$）の場合とで分けて説明をします。

n = N - 1 が素数の場合

$n$が素数の場合は、次の手順でデッキの構築が可能です。以下、$N=4 (n=3)$の場合を例に説明します。

(a) $n$次の正方行列に$0$から$n^2-1$までの数字を順に並べる

(a) \quad
\begin{matrix}
0 & 1 & 2 \\
3 & 4 & 5 \\
6 & 7 & 8
\end{matrix}

(b1) (a)の 0 列目はそのまま、1 列目を上に 1 シフト、2 列目を上に 2 シフトする
（(a)の対角成分が 0 行目に来るようにシフトする、とも考えられます）

(b1) \quad
\begin{matrix}
0 & 4 & 8 \\
3 & 7 & 2 \\
6 & 1 & 5
\end{matrix}

(b2) (a)の 0 列目はそのまま、1 列目を上に 2 シフト、2 列目を上に 4 シフトする
（あるいは(b1)の対角成分が 0 行目に来るようにシフトする）

(b2) \quad
\begin{matrix}
0 & 7 & 5 \\
3 & 1 & 8 \\
6 & 4 & 2
\end{matrix}

上記の(b)を作る操作を$n-1$回繰り返します。
ここでは$n=3$なので、(b2)まで作って終わりです（$n$回目で(a)に戻ってしまう）。

(c) (a)を転置する

(c) \quad
\begin{matrix}
0 & 3 & 6 \\
1 & 4 & 7 \\
2 & 5 & 8
\end{matrix}

上記の(a), (b1), (b2), (c)に、それぞれ 1 列ずつ追加する。各列の値は、それぞれ$n^2$から$n^2+n$までの値とする。

(a') \quad
\begin{array}{ccc|c}
0 & 1 & 2 & 9 \\
3 & 4 & 5 & 9 \\
6 & 7 & 8 & 9
\end{array}

\qquad

(b1') \quad
\begin{array}{ccc|c}
0 & 4 & 8 & 10 \\
3 & 7 & 2 & 10 \\
6 & 1 & 5 & 10
\end{array}

\qquad

(b2') \quad
\begin{array}{ccc|c}
0 & 7 & 5 & 11 \\
3 & 1 & 8 & 11 \\
6 & 4 & 2 & 11
\end{array}

\qquad

(c') \quad
\begin{array}{ccc|c}
0 & 3 & 6 & 12 \\
1 & 4 & 7 & 12 \\
2 & 5 & 8 & 12
\end{array}

(d) 先ほど追加した各列の値を並べた行を 1 つ作る。

(d) \quad
\begin{matrix}
9 & 10 & 11 & 12
\end{matrix}

以上。
(a') から (d) の各行がカード 1 枚分のシンボルの組となります。$N=4$の場合には全 13 枚のカードから成るデッキが構築されます。

\begin{matrix}
0 & 1 & 2 & 9 \\
3 & 4 & 5 & 9 \\
6 & 7 & 8 & 9 \\
0 & 4 & 8 & 10 \\
3 & 7 & 2 & 10 \\
6 & 1 & 5 & 10 \\
0 & 7 & 5 & 11 \\
3 & 1 & 8 & 11 \\
6 & 4 & 2 & 11 \\
0 & 3 & 6 & 12 \\
1 & 4 & 7 & 12 \\
2 & 5 & 8 & 12 \\
9 & 10 & 11 & 12
\end{matrix}

ドブルデッキの特徴

カードあたりのシンボル数を$N$とした時のドブルデッキの特徴を整理します。

  • 全カード数は、$N*(N-1)+1$
  • 全シンボルの種類数は、全カード数と同じ
  • 1 つのシンボルは、全カードの中で$N$回出現する
  • 任意の 2 枚のカードには、必ず共通するシンボルが 1 つだけ存在する
  • 任意の 2 つのシンボルは、必ずいずれかのカードに 1 回だけ出現する

n = N - 1 が素数の累乗の場合

n が素数の場合と同様に処理すると？

さて、$n$が素数の累乗の場合に同じ手順を踏むとどうなるでしょうか？
例えば$N=5$ ($n=4=2^2$) の場合で考えます。

(a) 正方行列を作る

(a) \quad
\begin{matrix}
0 & 1 & 2 & 3 \\
4 & 5 & 6 & 7 \\
8 & 9 & 10 & 11 \\
12 & 13 & 14 & 15
\end{matrix}

(b1) (a)の$k$列目を上に$k$シフトする
(b2) (a)の$k$列目を上に$2k$シフトする
(b3) (a)の$k$列目を上に$3k$シフトする

(b1) \quad
\begin{matrix}
0 & 5 & 10 & 15 \\
4 & 9 & 14 & 3 \\
8 & 13 & 2 & 7 \\
12 & 1 & 6 & 11
\end{matrix}
\qquad
(b2) \quad
\begin{matrix}
0 & 9 & 2 & 11 \\
4 & 13 & 6 & 15 \\
8 & 1 & 10 & 3 \\
12 & 5 & 14 & 7
\end{matrix}
\qquad
(b3) \quad
\begin{matrix}
0 & 13 & 10 & 7 \\
4 & 1 & 14 & 11 \\
8 & 5 & 2 & 15 \\
12 & 9 & 6 & 3
\end{matrix}

ここで(a)と(b2)を比較すると、2 列目 $2 \quad 6 \quad 10 \quad 14$ が同じ並びになっています。
もともと先頭列は各行列で共通なので、(a)と(b2)は先頭列と 2 列目が一致していることになります。
そのため、「カード間（＝行間）で共通する要素が 1 つである」ドブルの構成を満たせません。

このように$n$が素数の累乗の場合、(a)から(b)を作る操作として各列のシフトではダメ、ということになります。
そのため別の操作で(b)を作る必要があるのですが、これはガロア体（有限体）を導入することで解消できます。

ガロア体

ガロア体を簡単に説明すると、四則演算できる有限の要素数の集合のことです。
この要素数を位数と呼びます。

ガロア体は位数が素数、あるいは素数の累乗の場合でしか定義できません。

GF(3)

例えば位数 3 のガロア体は$GF(3)$と表記し、${0, 1, 2}$の 3 つの要素から成ります。
$GF(3)$において四則演算は、

  • $0 + 2 = 2$、対応する減算は$2 - 2 = 0$
  • $1 + 2 = 0$、対応する減算は$0 - 1 = 2$、$0 - 2 = 1$
  • $2 \times 2 = 1$、対応する除算は$1 \div 2 = 2$

という結果になります。
位数が素数の場合、加算・乗算は普通に計算して最後に位数で割った余りがガロア体における計算結果になります。
減算・除算は、加算・乗算の逆を取ることで定義できます。

GF(4)

同様に、位数 $4=2^2$ のガロア体は$GF(4)$とし、${0, 1, 2, 3}$の 4 つの要素から成ります。
ところが$GF(4)$の四則演算は、$GF(3)$のような位数の剰余では定義できません。

試しに位数の剰余で乗算を計算してみると、

  • $2 \times 1 = 2$、対応する除算は$2 \div 2 = 1$？
  • $2 \times 3 = 2$、対応する除算は$2 \div 2 = 3$？

このように異なる値を掛けたのに同じ値になる組み合わせが存在し、除算の結果が不定になってしまいます。

位数が素数の累乗の場合は、位数の剰余ではない方法で四則演算を定義する必要があります。
その定義を用いれば、乗算して結果が衝突することなく、除算を一意に計算できます（詳細は参考を見てください）。

実装の解説

ここまでの説明を踏まえて、dobble-makerのドブルデッキを構築する処理（make_dobble_deck関数）を説明します。

make_dobble_deckは、カード 1 枚当たりのシンボル数n_symbols_per_cardから、各カードに描画されるシンボル ID のリストを生成します。

  • n_symbols_per_cardは2 または 素数の累乗+1であること
make_dobble_deck（抜粋）
import galois
...
def make_dobble_deck(n_symbols_per_card: int) -> tuple[list[list[int]], int]:
    ...
    n = n_symbols_per_card - 1
    if n == 1:
        gf = lambda _: 0
    else:
        gf = galois.GF(n)

    pairs: list[list[int]] = []

    # 最初の N * N 枚のカード
    for i in range(n):
        for j in range(n):
            pairs.append([int(gf(i) * gf(k) + gf(j)) * n + k for k in range(n)] + [n * n + i])

    # 次の N 枚のカード
    for i in range(n):
        pairs.append([j * n + i for j in range(n)] + [n * n + n])

    # 最後の 1 枚
    pairs.append([n * n + i for i in range(n + 1)])

    ...

まず$n = N - 1$と$GF(n)$を初期化します。
ガロア体の四則演算はgaloisパッケージを用いました（PyPIで公開されています）

初期化
    n = n_symbols_per_card - 1
    if n == 1:
        gf = lambda _: 0
    else:
        gf = galois.GF(n)

次に(a')及び(b')の各行列を生成します。

(a'), (b')の生成
    # 最初の N * N 枚のカード
    for i in range(n):
        for j in range(n):
            pairs.append([int(gf(i) * gf(k) + gf(j)) * n + k for k in range(n)] + [n * n + i])

上記の[int(gf(i) * gf(k) + gf(j)) * n + k for k in range(n)]で(a), (b)の行列を作り、[n * n + i]を末尾に追加することで(a'), (b')を作ります。
i == 0が(a')、i == 1が(b1')、i == 2が(b2'), ...に対応し、j行k列の値を上記の式で決めていきます。

nが素数の場合は、int(gf(i) * gf(k) + gf(j))と(i * k + j) % nは等価です。これは前述の通り、位数が素数のガロア体での加算・乗算は、位数で割った余りを求めるだけで良いためです。
そしてこの計算が列を上にシフトする操作に対応します。

nが素数の累乗の場合に(a)と(b2)で一致した列があったというのは、iが異なりk, jが同じだった場合に(i * k + j) % nが同じ値になったことを意味します。
これも先に説明した通り、nが素数の累乗の場合、四則演算を位数の剰余で定義することはできません。それとは異なる方法で四則演算を定義したガロア体が必要で、それを用いれば結果の衝突は起こりません。

続いて(c')の行列を生成します。

(c')の生成
    # 次の N 枚のカード
    for i in range(n):
        pairs.append([j * n + i for j in range(n)] + [n * n + n])

最後に(d)の組み合わせを生成します。

(d)の生成
    # 最後の 1 枚
    pairs.append([n * n + i for i in range(n + 1)])

おわり

参考

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0