【TCG】確率統計と計算機工学から考える適切なシャッフル【DCG】
2022/11/07
ベルヌーイシフト写像と長期予測不能性について注釈を追加2023/03/28
ディールシャッフルの引用文献について追記
(※1)の内容を一部修正
セルフカットになってからシャッフル後にトップ解決するとめっちゃ気まずい。
墓地0枚の相手にポクチンちん、chapuddingです。
時の流れは早いもので、大型感染症が流行し始めてからもうすぐ3年が経過しようとしています。
感染症拡大防止の観点からTCGでは相手のカードに触れることが禁忌として扱われるようになりました。
これにより不正防止のために行われていた相手の山札をシャッフルする行為は禁止され、対戦相手のシャッフル後に山札を指定通りに操作してもらう方式に切り替わりました。
しかしこの方式では相手の不正な山札操作を防ぐ行為として十分に機能していない場合が多く、大型大会の配信卓ですら不正を疑われるような行動が散見されるのが現状です。
そのため、近年SNSではシャッフルの方法について議論されてる機会が多くなりました。
ところで、著者は学士課程から修士課程にて計算機工学について学んでおり、浅学ながらも知見があります。
確率と密接に関与しているカードゲームと確率統計や計算機工学は親和性が非常に高く、過去にもこれらを用いたカードゲームに対する考察をしている記事をいくつか執筆しています。
そこで、本記事ではシャッフルの意義や適切な方法などを確率統計や計算機工学の観点から考察します。
記事内には誤りや誤解を招く内容が含まれる可能性がありますので、書いてある内容を鵜呑みにせず各々で吟味していただければと思います。
特に確率統計についてはかなり怪しいことを言っている可能性があります。
誤りなどを発見した場合は他人に迷惑をかけず著者に分かる形でご指摘や誹謗中傷をしていただけると助かります。
Twitter: @chapuddingEA
また、マニアックな追記を行う場合は(※)を用いて注釈を入れています。
興味のない方はスルーしてもらっても構いませんが、目を通していただけると幸いです。
※内には私も内容に不安のあるものも含まれていますので、有識者の方には是非一読していただけると幸いです。
シャッフルの種類
現在主に行われているシャッフルには大きく分けて3つある。
3つのシャッフルの方法と特徴、そのシャッフルのみを行った際にできる不正行為などについて軽く示す。
ヒンズーシャッフル
片方の手に山札を持ち、もう片方の手で山札の下側のカードの束を上側に持ってくる操作を繰り返すシャッフル
カードゲームに触れたことがない人間が最初にイメージするシャッフル手法
山札の上側に来るカードが大きく変化する一方で、カードの束の中での順序の入れ替わりが起こらない切り方
そのため元の山札の順序を完全に記憶していた場合、このカードを引いたから次はこのカードを引く可能性が高いと推測しやすくなる
ファローシャッフル
山札を2つの束に分け、2つの束のカードが交互に重なり合うように２つの束を合わせて1つの山札に戻す方法
多くのプレイヤーが最も頻繁に行うシャッフル手法
山札の中間にあるカードの位置が大きく変化する一方で、山札の上側や下側にあるカードの位置がほとんど変化しない切り方
そのため作為的に山札の1番上を特定のカードにしてからファローシャッフルのみを行うことで、シャッフルしているように見せて特定のカードを山札の1番上に固定することが可能
ディールシャッフル
山札のカードを5〜10の束に1枚ずつ配り、配り終えた後に束を再び重ねて1つの山札に戻す方法
トランプゲームをする際にカードを全てのプレイヤーに配る際の動作を応用したシャッフル手法
山札の全てのカードの位置が様々な位置に変わる一方で、全く同じ順序の山札に全く同じディールシャッフルをすると全く同じ順序になる
そのため、各試合の前に順序に並び替えをした後にディールシャッフルのみを行うと、毎試合全く同じデッキの順序を再現することが可能
シャッフルの意義
無作為化とは
シャッフルをする最大の目的は、山札の順序を無作為化することである。
無作為化とは、同名カードを区別した場合に全ての山札の順序のパターンが等確率で発生することを表す。
ところで、下の2つの図はある法則に従って打たれた点と完全に無作為に打たれた点を表している。
両者を比較してどちらが無作為に打たれた点なのか、ある法則とは何かを考えてみてほしい。
正解は、左の図が完全に無作為に打たれた点(一様乱数によって打たれた点)である。
右側の図は画像を方眼紙のように細かく分け、それぞれのマスの中に1つずつ点を打つという操作を行って作成された図である。
言い換えれば右の図は作為的に均一に打たれた点であると言える。
人間は順序や分布に偏りがあると何かしらの法則があると考えてしまうことが多いが、偏ることも均一になることも平等に起こり得るのが無作為化である。
DCGでは「同じカードが固まって手札に来た、アルゴリズムがおかしい」などといった発言が散見されるが、これはむしろ適切な無作為化がされている証拠でもある。(※1)
(※1)
現在では全ての山札の順序のパターンを等しく再現できるアルゴリズムとして、Fissher-Yatesのシャッフルアルゴリズムが広く知られている。
そのため、現在商用でリリースされているDCGは全て適切なシャッフルが行われていると考えて良い。
一方で、このアルゴリズムが広く知られていなかった昔のゲームでは順序のパターンに偏りがある。
例えば、カードゲームに近いシステムのゲーム「ロックマンエグゼ」シリーズ(2001〜2005)では、1フレームに1回山札の2枚のカードの位置を入れ替える操作を行うのみだったため対戦開始前に山札の2枚のカードを入れ替える操作を30回行うのみだったため、デッキリストの上の方に配置したカードが最初の手札に来やすいといった偏りがあった。
(2023/03/28修正)
また音楽再生アプリのシャッフル機能などでは、同じ曲が何度も流れないように意図的に均一化しているものも数多く存在する。
均一は希少
多くのカードゲームプレイヤーは同じカードが複数枚手札に来ると、シャッフルが十分ではなかったと感じることが多いだろう。
しかし、前の節でも説明した通り無作為化は均一化ではない。
例えば、40枚の山札のカードゲームにおいて同じカードを4枚ずつ10種類入れたデッキを使うことを考える。(デュエル・マスターズを想定)
このデッキを使った際に、デュエル・マスターズの最初の手札枚数である5枚の全てが別々のカードである確率はどの程度であるかを想像していただきたい。
正解は約39.2%である。
おそらく多くの読者が想像していた確率よりも低いことが予想される。
また、逆に事故と呼べるほどカードが重複しているパターン(2, 2, 1枚、3, 1, 1枚、3, 2枚、4, 1枚)は合計すると約11.8%も存在する。(※2)
このように一般的な感覚で無作為化されていると感じる均一な状態というのは、人間が思っている以上に希少な事象である。
山札の中身が均一になるようなシャッフルの方法は、均一な状態を作為的に作成する行為であるため不正行為の一種であると言える。
具体的には、各試合の前に全てのカードを整列させてディールシャッフルをする行為などがこれに該当する。
試しに、サンプルリストのような4枚×10種類の山札で普段行なっているシャッフルをして上から5枚を確認する行為を10回行なってみてほしい。
もし5枚全てのカードが異なるパターンが7回以上出たなら、あなたのシャッフルは過度な均一化をしている可能性がある。(※3)
(※2)
それぞれの重複枚数のパターンの確率は以下の通り。
(同じカードが3枚と残りが別々のカードの場合、3-1-1と表記)
1-1-1-1-1
$${\frac{{}_{10}\mathrm{C}_4\times 4^5}{{}_{40}\mathrm{C}_5}\times 100(\%)\simeq 39.22(\%)}$$2-1-1-1
$${\frac{10\times {}_4\mathrm{C}_2 \times 4^3\times {}_9\mathrm{C}_3}{{}_{40}\mathrm{C}_5}\times 100(\%)\simeq 49.02(\%)}$$2-2-1
$${\frac{{}_{10}\mathrm{C}_2\times ({}_4\mathrm{C}_2)^2 \times 32}{{}_{40}\mathrm{C}_5}\times 100(\%)\simeq 7.88(\%)}$$3-1-1
$${\frac{{}_4\mathrm{C}_3\times 10\times 4^2\times {}_9\mathrm{C}_2}{{}_{40}\mathrm{C}_5}\times 100(\%)\simeq 3.50(\%)}$$3-2
$${\frac{{}_4\mathrm{C}_3\times 10\times {}_4\mathrm{C}_2 \times 9}{{}_{40}\mathrm{C}_5}\times 100(\%)\simeq 0.33(\%)}$$4-1
$${\frac{10\times 36}{{}_{40}\mathrm{C}_5}\times 100(\%)\simeq 0.05(\%)}$$
(※3)
二項分布における検定を行った際に、シャッフルが適切に行われていないと判断される回数を検討した。
帰無仮説$${H_0}$$を
「あなたが4枚×10種類の山札でシャッフルをして上から5枚確認する行為を10回行った際に、確認した5枚のカードがすべて異なっている回数が3.92回($${\simeq}$$0.3922$${\times}$$10)である」
とし、対立仮説$${H_1}$$を
「あなたが4枚×10種類の山札でシャッフルをして上から5枚確認する行為を10回行った際に、確認した5枚のカードがすべて異なっている回数が3.92回($${\simeq}$$0.3922$${\times}$$10)ではない」
と仮説を立てて有意水準$${\alpha=0.05}$$にて両側検定を行った際に、帰無仮説が棄却されて対立仮説が採択されるのが0回のときと7〜10回の場合である。
5枚のカードがすべて異なっていた回数が0回の場合は逆にカードが固まりすぎているため、これもまた十分な無作為化が行われていないといえる。
また、統計検定はあくまでも帰無仮説が棄却された場合にあなたのシャッフルが適切ではないとするだけである。
5枚のカードがすべて異なっていた回数が1～6回であったとしてもあなたのシャッフルが適切に行われていることは保証しないことをここに明記する。
計算機工学から見た適切なシャッフル
ここまでで、シャッフルを用いた不正や不適切なシャッフルについて多く言及してきた。
ここからは、最初に紹介した3つのシャッフルのうち何をどの程度やるのが適切なのかについて計算機工学の観点から考察する。
ディールシャッフルは無作為化ではない
まずここで大前提として、ディールシャッフルを複数回行うことは無作為化に相当しないことを確認する必要がある。
ディールシャッフルは先にも説明した通り、元の山札の順序が同じであれば全く同じ山札の配列を再現できる方法である。
ディールシャッフルを複数回行っても無作為化はされないことを、実際にデュエル・マスターズのデッキを例に説明する。
デュエル・マスターズを詳しく知らないプレイヤーにかなりかみ砕いて説明すると、このデッキは金色に光っている左上の数字が大きいカードが重要であり、これらのカードが最初の手札5枚の中に1～2枚存在するとゲームを非常に有利に進められるデッキである。
このデッキに対して、ディールシャッフルを3回ほど行った際に山札がどのように変化するのかを以下の画像に示す。
3回目のディールシャッフルを行った後の山札の順序の中で、どの連続する5枚を確認しても必ず金色に光っているカードがちょうど1～2枚含まれていることが確認できる。
均一についての節でふれたとおりこのような均一な山札の状態は一般的な人間の感覚と比べると稀であり、稀な状態を作為的に再現する行為は紛れもない不正行為である。
実際に、Magic: the Gatheringというカードゲームでは2017年にフロアルール改定でシャッフルに関する以下のルールが追加された。
Section 3.9 (Shuffling): In the previous Tournament Rules update, we announced rule changes regarding "pile shuffling." Based on observation and feedback, we are now restricting pile shuffling to once per game and only at the beginning of that game. Remember: "pile shuffling" is not sufficient shuffling. It should only be used to count the cards in a deck.
3.9節 (シャッフル): 前回のフロアルール改定時に、ディールシャッフル(パイルシャッフル)に関するルール変更を発表した。観察とフィードバックをもとに、ディールシャッフルは対戦開始時に一度のみ行うことをここに制定する。
ディールシャッフルは十分なシャッフルではなく、デッキの枚数を確認するためにのみ行うべきであることに留意すること。
(訳: chapudding)
上記のようにMagic: the Gatheringではディールシャッフルをシャッフルとしては認めておらず、枚数を数えるためにのみ利用されるべきであると明言されている。
あなたがもし複数回のディールシャッフルを行っていた場合は、今日からゲームごとに1回限りとするように変えることを強く推奨する。
複数回のディールシャッフルは時間がかかるだけではなく、対戦相手から疑いの目をかけられる原因にもなる。
※2023/03/28追記
上記で引用していたMAGIC TOURNAMENT RULES RELEASE NOTESのリンクが切れていたため、今日時点でのMagic: the Gatheringのトーナメントルールを改めて掲載する。
ディールシャッフルは無作為化目的のシャッフルとしては認められていないことが明記されている。
Pile shuffling alone is not sufficiently random and may not be performed other than once each at the beginning of a game to count the cards in the deck.
Pile shuffling is completely non-random, since individual cards can be tracked and since cards are shuffled into a deterministic order. A single pile shuffle can help players count their decks and loosen sticky cards, but more than that a pile shuffle does not contribute to randomization and will qualify as Slow play. Once the game has begun the need to count the deck during randomization is largely gone. As such, a single pile shuffle at the start of the game is permitted, but is not allowed at any other time. Please remember when applying the IPG that habits are hard to break, and a single caution may be appropriate the first time.
ディールシャッフル(Pile Shuffling: パイルシャッフル)だけでは十分なランダム性が得られない。そのため、ゲーム開始時に各1回、デッキのカード枚数を数える目的以外に行えない場合がある。
ディールシャッフルは、個々のカードを追跡することができ、カードが決定論的な順序で並び替えられるため、完全に非ランダムである。
1回のディールシャッフルはデッキ枚数を数えたり、湿気などでプレイしにくい状態のカードをほぐすのに役立つが、それ以上のディールシャッフルは無作為化に寄与しないので、遅延行為として認定される。
ゲームが始まったら、無作為化の際にカードの枚数を数える必要性はほとんどなくなる。
そのため、ゲーム開始時に1回のディールシャッフルを行うことは認められるが、それ以外のタイミングでのディールシャッフルは認められない。
違反処置ガイド(Infraction Procedure Guide, IPG)を適用する際には、習慣を是正するのは難しいことであるため、初回は警告程度のペナルティが適切であることに留意すること。
(訳: chapudding)
また、デュエル・マスターズのフロアルールにも以下のように明記されている。
ゲームの開始時や切り直すよう指示されたとき、デッキを無作為化しなければならない。無作為化とは、どのプレイヤーにもデッキの中の並びやカードの位置がまったく分からない状態にすることである。ディール・シャッフル（Pile Shuffle、俗に○山切りとも呼ばれる）だけでは充分な無作為化とは認められない。
(2019年7月2日発効)より一部抜粋
いずれにせよ、ディールシャッフルは無作為化としての機能はないことが名言されている。
ファローシャッフルと長期予測不能性
一般的にシャッフルの話題において良いシャッフルとされているファローシャッフルについて、無作為化ができるかの観点に立って考える。
山札のカードの位置は座標に置き換えることができる。
ここでは山札の一番下にあるカードの座標を0とし、山札の上にあるカードの座標を1とする。
シャッフルが行っているカードに対する操作を座標系上の点の操作として捉えると、完全なファローシャッフル(山札をちょうど半分に分け、1枚違わず交互に重ね合わせる)は以下のように考えることができる。
$${x\geq\frac{1}{2}}$$の点の座標を$${-\frac{1}{2}}$$する
全ての座標の点を2倍に引き伸ばす
すなわち、ファローシャッフルが行う座標操作$${f(x)}$$は以下の式で表すことができる。
$$
f(x)=\left\{\begin{array}{ll}2x&(0\leq x<\frac{1}{2})\\2x-1&(\frac{1}{2}\leq x\leq 1)\end{array}\right.
$$
これはベルヌーイシフト写像と全く同じ形である。
ベルヌーイシフト写像は、$${x_{t+1}=f(x_t)}$$で得られる離散時間時系列$${x_t}$$がカオス時系列になることが知られている。
ここで言うカオス時系列とは、写像などの決定論によって変化する時系列のうち長期予測不能性や非周期性などの特徴を持つ時系列の総称である。
カオス時系列の性質の1つでもある長期予測不能性とは、言い換えれば繰り返し同じ操作を行うことで元の状態を完全に把握していても最終的な状態を予測することが困難であることを意味している。
完全なファローシャッフルと対応するベルヌーイシフト写像ですら長期的な予測が困難であることが示されている。
人間が行う不完全なファローシャッフルならなおさら予測は困難となる。
そのためファローシャッフルを繰り返し行うことで山札の順序を予測できない状態、すなわち無作為な状態を再現できるといえる。(※4)
しかし、ファローシャッフルをする際には大きく2つのことに留意する必要がある。
1つ目はファローシャッフルは繰り返し行うことで初めて無作為化の意味を成すということである。
上で説明した通りファローシャッフルが保証するのは長期予測不能性であり、1, 2回程度のファローシャッフルで十分な無作為化ができないことに留意する必要がある。
具体的にどの程度ファローシャッフルを行えば良いか具体的な数値を理論的に求めることは難しいが、対戦開始前などの対戦時間に影響しない場面でのシャッフルでは最低10回以上はファローシャッフルを行うべきであろう。(※5)
2つ目に、ファローシャッフルの特性上山札の1番上のカードや1番下のカードが十分に無作為化できないことである。
これについては、数回ファローシャッフルを行なったのちにヒンズーシャッフルを1回混ぜることで解決できる。
以上のことから、数回のファローシャッフルの後に1回のヒンズーシャッフルを行うことを1セットとし、このセットを複数回繰り返し行うのが計算機工学の観点から考える適切なシャッフルである。
(※4)
2022/11/07追記
ベルヌーイシフト写像が長期予測不能性を示すのは、初期値が無理数の場合のみである。
初期値が有理数の場合は周期的な時系列になることが知られている。
各カードの座標は有理数(分数で表現できる数)であるため、完全なファローシャッフルを繰り返すと山札の順序は周期的に変化することとなる。
(そもそも完全なファローシャッフルは$${\frac{n}{2}}$$山に分けるディールシャッフルに相当する。($${n}$$は山札の枚数))
しかし、完全なファローシャッフルを行うことの困難さ、ディールシャッフルよりも圧倒的にシャッフルの回数を増やしやすい(写像回数を重ねることの容易さ)から、人間の目から見ると長期予測不能性が担保されると考えた。
(※5)
ベルヌーイシフト写像はモジュロ演算(割った余りを求める演算)を用いて以下のように書き直せる。
$$
f(x)=2x\ (\mathrm{mod}\ 1)
$$
このモジュロ演算を取り払った場合を考えると、カード1枚分の座標の違い(40枚のデッキでは約0.026)は10回ファローシャッフルをすることで1024枚分の座標の違い(40枚のデッキでは約26.254、デッキを26週と少しに相当)にまで発展することとなる。
モジュロ計算を取り払った際に1枚の位置の差がこれだけの大きさになるならば、人間が無作為な状態であると感じるには十分であると考えたため10回という数値を提示した。
何かの指標に基づいた判断ではないため、もっと少ない回数で目的を達成できる可能性や逆に不十分である可能性もある。
ちなみに、初期値の微細な誤差(今回で言うところのカード1枚分の座標の違い)が時間経過とともに拡大し続ける性質のことを初期値鋭敏依存性(バタフライエフェクト)という。
まとめ
本記事では、シャッフルの意義や適切なシャッフルについて確率統計や計算機工学の観点から考えてみました。
最終的に本記事では、ディールシャッフルはゲーム開始時に一度だけとしファローシャッフルを何度も繰り返し行い、時折ヒンズーシャッフルを混ぜるのが適切なシャッフルであると結論付けました。
いつものことながらまともに構成を考えず完全な見切り発車でお気持ち表明をしただけなので、かなり読みにくい文章になってしまったことをここにお詫びします。
気がつけば半分くらいシャッフルを利用したイカサマについての記事になってしまい、かなり本筋から逸れてしまっていました。
しかし、シャッフルに対して自分と相手お互いに真摯に取り組むことは運の要素に大きく左右されるカードゲームにおいて非常に重要なことです。
知識として不正を知って対策を施すことで、お互いに疑念の残らない形で対戦に集中できます。
信頼は行動によってのみ得られるため、綺麗事を並べる前に万人に信頼されるように行動をしましょう。
再三となりますが、不明点や誤りがありましたら遠慮なく著者にご連絡ください。
Twitter: @chapuddingEA
それではみなさん、良いカードゲームライフを。
おわり。