机上のkuwa論

デュエルマスターズ考察 / 間違いがあればコメントでご指摘お願いします

ディールシャッフルの規則性


はじめに

8山切りのあとに、5山切りをするとデッキのカードの並びがもとに戻る”事実をご存じでしょうか?

wikiによると”1回目の山の数と2回目の山の数の積がデッキの枚数になるようにディールシャッフルを行う”と山がもとの順番になるそうです。例えば、dmでは4山切りした後に10山切りをしたら元に戻ります。

では、40の約数の2,4,5,8,10,20での組み合わせで他に元に戻る切り方があるのでしょうか?
それは何通りでしょうか?

そこで今回の記事は
「8切り後に5切りする他に山の順番がもとに戻る組み合わせの検証」
「8切りのあとに5切りをすると元に戻ることを数学的に説明」

の2つのテーマを扱います。

索引

ディールシャッフル

みなさまは普段どんなシャッフルをしているでしょうか? 
ディールシャッフルは通称~山切りなどと呼ばれ、8山切りであれば、8つの山にそれぞれデッキのカードを分配したあとに、その山を戻すシャッフルです。

ディールシャッフルはデッキの枚数確認にも利用されたり(これはイカサマ防止としても有用な手段です。)4積みのカードが固まっている状態を分散させるためにします。ただし、ディールシャッフルは無作為化には適していません。どうしても規則性が生まれてしまいます。

MTGのイベント規定では 引用: ディール・シャッフル(Pile Shuffle、俗に○山切りとも呼ばれる)は、ゲーム開始時にそれぞれ1回カードを数える目的で行われることを除いて認められない。 ようです。今回の記事の主張とずれますが、複数の種類のシャッフルを行うことが推奨されています。

山の順番がもとに戻る組み合わせ

今回は8山切りを1回したあとに、2山切り、4山切り、5山切り、8山切り、10山切り、20山切りのいずれかを複数選択した組み合わせをシミュレーションしました。
そして、回数が多いシャッフルをしても現実のケースと乖離するため6回までのシャッフルで検証します。
「8 -> 5」という表記は8山切りのあと、5山切りをすることを表しています。
以下に結果を折りたたんでいます。

結果の考察

415通りありました。
「8 -> 5 -> 8 -> 5」など、1回もとに戻る場合は除去したつもりです。
「8 -> 10 -> 20」と「8 -> 20 -> 10」は行っていることは同じなので、消せるかもしれません。
ぜひお手元のデッキで山順が元に戻るか確認してみてください。

8切り後、5切りをすると元に戻ることを数学的に説明

デッキをシャッフルする行為は線形代数の行列っぽい見た目な置換で表せます。
簡単に述べると、置換は1行目であるカードの並びをどの位置に移動するかを2行目に対応させる形式です。詳しいことは参考文献を読んでください。

8山切りのシャッフル行為を置換  \sigma
5山切りのシャッフル行為を置換  \tau  とすると、

8山切りのあと、5山切りをすることは置換の積  \sigma \tau をとることと同値です。



  \sigma = \left(
    \begin{array}{ccc}
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 &23 & 24 & 25 & 26 &27& 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 &39 &40      \\
      1 & 6 & 11 & 16 & 21 &26 & 31 &36 & 2 & 7 & 12 & 17 &22 & 27 & 32 & 37 & 3 & 8 & 13 &18 &23 & 28 &33 &38 &4 & 9& 14 & 19 & 24 & 29 & 34 & 39 &5 & 10& 15&20 &25 &30&35&40 
    \end{array}
  \right)



  \tau = \left(
    \begin{array}{ccc}
            1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 &23 & 24 & 25 & 26 &27& 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 &39 &40      \\
      1 & 9 & 17 & 25 & 33 & 2 & 10 & 18 &26 & 34 & 3 & 11 & 19 & 27 &35 & 4 & 12 & 20 & 28 & 36& 5 & 13 & 21 & 29 & 37 & 6 & 14 & 22 & 30 & 38 & 7 & 15 & 23 &31 & 39 & 8 & 16 & 24 & 32 & 40 
    \end{array}
  \right)



  \sigma \tau = \left(
    \begin{array}{ccc}
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 &23 & 24 & 25 & 26 &27& 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 &39 &40      \\
      1 & 6 & 11 & 16 & 21 &26 & 31 &36 & 2 & 7 & 12 & 17 &22 & 27 & 32 & 37 & 3 & 8 & 13 &18 &23 & 28 &33 &38 &4 & 9& 14 & 19 & 24 & 29 & 34 & 39 &5 & 10& 15&20 &25 &30&35& 40 
    \end{array}
  \right)
 \left(
    \begin{array}{ccc}
            1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 &23 & 24 & 25 & 26 &27& 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 &39 &40      \\
      1 & 9 & 17 & 25 & 33 & 2 & 10 & 18 &26 & 34 & 3 & 11 & 19 & 27 &35 & 4 & 12 & 20 & 28 & 36& 5 & 13 & 21 & 29 & 37 & 6 & 14 & 22 & 30 & 38 & 7 & 15 & 23 &31 & 39 & 8 & 16 & 24 & 32 & 40 
    \end{array}
  \right)

ここで置換の相等より置換  \tau の上段の並びを,置換  \sigma の下段の並びに合わせると



  \sigma \tau = \left(
    \begin{array}{ccc}
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 &23 & 24 & 25 & 26 &27& 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 &39 & 40  \\
      1 & 6 & 11 & 16 & 21 &26 & 31 &36 & 2 & 7 & 12 & 17 &22 & 27 & 32 & 37 & 3 & 8 & 13 &18 &23 & 28 &33 &38 &4 & 9& 14 & 19 & 24 & 29 & 34 & 39 &5 & 10& 15&20 &25 &30&35 & 40 
    \end{array}
  \right)
 \left(
    \begin{array}{cc}
           1 & 6 & 11 & 16 & 21 &26 & 31 &36 & 2 & 7 & 12 & 17 &22 & 27 & 32 & 37 & 3 & 8 & 13 &18 &23 & 28 &33 &38 &4 & 9& 14 & 19 & 24 & 29 & 34 & 39 &5 & 10& 15&20 &25 &30&35&40 \\
           1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 &23 & 24 & 25 & 26 &27& 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 &39 & 40      
       
\end{array}
  \right)



   = \left(
    \begin{array}{ccc}
            1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 &23 & 24 & 25 & 26 &27& 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 &39 &40      \\
     1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 &23 & 24 & 25 & 26 &27& 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 &39 &40      
    \end{array}
  \right)

となります。この置換の積  \sigma \tau の結果は、
上段を下段の位置に移動するという意味なので、
これはつまり、そのまま元の山順に戻るということです。

こうして、他のディールシャッフルに関しても置換の積を使って説明できます。

あとがき

今回は40の約数のみの切り方で検証しましたが、7山切りや9山切りなどの奇数切りも競技シーンで行われるため、40の約数以外の切り方でもシミュレーションしても面白いかもしれません。また、パケット(分配後の山)の重ね方がパケット数をdとすると d! 通りあるので、さらに組み合わせが多くなります。

組み合わせの検証には過去に作成したディールシャッフルプログラムを再利用しました。今後、行列の置換で作り直していこうと思います。そうすればどんなシャッフルでも楽に実装できそうです。そして実行速度が早い。

ファローシャッフルとディールシャッフルの組み合わせでデッキが元に戻る検証も一応行ったのですが、文献を読んでいるとファローシャッフルは確率的にカードが重なりあい、それはGilbert–Shannon–Reeds modelに沿うようです。過去に作成したファローはいわゆるパーフェクトシャッフルと呼ばれるもので、確率的にはシャッフルしていません。一意に決まります。というかパーフェクトシャッフルも、ディールシャッフルと同じように規則性が生まれるためシャッフルとしては適していないし、繰り返すと確実にもとに戻ることが予測できます。

ディールシャッフルの複数の山切りで元に戻る厳密な証明や、感覚的な説明は他の方に任せたいと(ぜひご自身のブログで)思います。

参考文献:トランプのシャッフルにおける可視化と最適な組み合わせに関する検討 "井手 広康 奥田 隆史 "
URL : https://www.ipsj.or.jp/award/9faeag0000004f1r-att/CF-011.pdf