【計算機工学】僕のシャッフル、本当に無作為化できてる？【検証】

2023年11月12日 13:11

ファローシャッフルを拒否する人間、いない
墓地のない相手にブラッドゥ、chapuddingです。
シャッフル、してますか？
カードゲームの競技シーンにおいてデッキの無作為化は切っても切り離せないものであり、公正な対戦をするうえで欠かせない要素です。
しかし、ポケモンカードのシティリーグ（デュエマで言う年4回しか出られないCS）ではシャッフルへの意識が希薄であり、予選5回戦すべての対戦相手が交換シャッフルの際に相手のデッキをファローすらせず簡単なカットで済ませていました。
これは非常に由々しき事態であり、悪意を持って積み込みをするプレイヤーであればかなりの高確率で全勝で予選通過できるだろう、と感じさせられるほどでした。
対戦相手を信頼するという側面においてもシャッフルは重要なものであり、シャッフルについては定期的にSNS上でも議題に上がります。

カードゲームにおいてシャッフルは非常に重要な要素の一つであり、私も適切なシャッフルについて計算機工学の観点から考察した記事を執筆したことがあります。
以下の記事でシャッフルの種類の説明、無作為化とはなにか、ディールシャッフルは無作為化ではない、適切なシャッフルは何かなどの議論を行っています。

この記事では「ファローシャッフルを2～3回した後にヒンドゥーシャッフルを1回する、という動作のセットを複数回行う」というのが適切な無作為化を行える手順であると結論づけました。
しかし、上記の記事では理論的な議論のみで結論を導いており、実際に適切なシャッフルであるかの確認はしていませんでした。
そこで、今回は統計学と計算機工学の観点から私のシャッフルが本当に無作為化できているのかについて調べてみました。

本記事では上の記事の内容をある程度読んでいることを前提として執筆しているので、まだ読んでいない方はこの記事よりも先に読んでみてください。
また、不真面目な大学生であったため情報系の学科に属していたにも関わらず統計学については浅学です。
統計学方面では誤りを発信している可能性がある上に、分かりやすく説明するために正確性を欠いた表現を多用します。
統計学がわからない方は鵜呑みにしないようにしてください。
また、統計学に造詣のある方は不適切な表現に目を瞑っていただくと共に、表現の誤りでは済まないような間違いに気づき次第Twitterの方までご連絡いただけると非常に助かります。
Twitter: @chapuddingEA

検証するシャッフル

本記事では、著者が実際にデュエル・マスターズのCSで自分のデッキに対して行っているシャッフルについて検証する。
著者は普段以下の手順にて自分のデッキのシャッフルを行っている。

ファローシャッフルを3～4回行う
7つの山に分けるパイルカウント(ディールシャッフル)を行う
ファローシャッフルを7～10回行う

以前の記事ではヒンドゥーシャッフルを織り交ぜることが大切だと結論付けたが、上記の手順には組み込んでいない。
ヒンドゥーシャッフルを混ぜる理由はデッキの上と下が固定されないようにすることである。
そのため、意識的にデッキの上と下が固定されないようにファローシャッフルすればよいと考え、著者はカードの券面を表向きにしてしまうリスクの高いヒンドゥーシャッフルを避けるようにした。

プログラムに自分を再現させる

実際に著者のシャッフルが無作為化できているのかを検証するにあたり、自分のシャッフルの結果のデータを取得することが必要となる。
ここで、実際に1セットのシャッフルを行いデッキの配列を記録することを繰り返してデータを取得するのは現実的ではない。
そのため、著者のシャッフルを再現できるようなプログラムを作成することで検証することとした。

パイルカウントは何回行っても必ず同じ結果になるが、ファローシャッフルはランダムな要素がいくつか介入する。
そこで、著者がどのような特徴のファローシャッフルをしているのか確認するため、実際に50回ファローシャッフルのデータを計測した。

山札を分ける枚数

ファローシャッフルの第一段階として、デッキを2つに分ける必要がある。
著者はまずデッキを左手に持ち、デッキの上半分を右手で掴むことで分けている。

このときに正確に半分ずつに分けることは難しく偏りが生まれるため、この偏りを計測した。
実際に計測した結果、以下のようになった。
(左手の枚数:右手の枚数)で表記

18:22 7回
19:21 17回
20:20 21回
21:19 5回

そのため、デッキを半分に分けるときはそれぞれ上から15%、35%、40%、10%として実装をした。

デッキの上下の余り

ファローシャッフルをするにあたり、正確に1枚ずつ重ね合わさることはまれである。
その中でも、デッキの上端下端については顕著であり、5枚以上カードが余ることも多々あった。

前述の通り、著者はデッキの上端下端が固定されないようなファローシャッフルを心がけていたためデッキの下側、すなわち左手側のカードが意図的に上側に来るようにファローシャッフルをしていた。
実際に左手側のカードが上から何枚余っていたかをカウントした。
マイナスの場合は右手側のカードがその枚数分上側に来ている。

-3枚 1回
-2枚 4回
-1枚 3回
1枚 7回
2枚 9回
3枚 7回
4枚 7回
5枚 6回
6枚 3回
7枚 0回
8枚 2回
9枚 1回

以上のデータから、それぞれの枚数になる確率をそれぞれ以下のような確率に設定した。

-3枚 1%
-2枚 5%
-1枚 10%
1枚 15%
2枚 20%
3枚 15%
4枚 13%
5枚 10%
6枚 5%
7枚 3%
8枚 2%
9枚 1%

不完全な重ね合わせ

前述の通り、ファローシャッフルをするにあたり正確に1枚ずつ重ね合わさることはまれである。
たまに2枚重なって重ね合わせられることがある。

このように重なることが上端と下端以外でどの程度起こり得るのか確認した。
1枚は交互に重ね合わさっていることを示している。

1枚 1519回
2枚 70回
3枚 4回
4枚 1回

そのため、このような重なり合わせが起こる確率を以下のように設定した。

2枚 4.4%
3枚 0.25%

検証方法

順番のデータ化

プログラムに著者のシャッフルを再現させたところで、それを評価する手段が妥当でなければ意味がない。
以前執筆した記事では妥当な評価手段が考えつかなかったため、カード一枚分の位置の差がどの程度発展するかという曖昧な評価方法で結論を出した。
しかし、下記の論文にて非常に優れた評価方法が紹介されていたため本記事ではその評価方法の一部を拝借することとした。
この論文は本記事を執筆するきっかけにもなったものであり、母国語で読める論文は貴重であるため興味のある読者は是非ご一読願いたい。

この論文では複数回のシャッフルの結果をまとめる手段として、シャッフル前の位置とシャッフル後の位置を行列で管理する手法を用いている。

デッキのカード枚数(デュエルマスターズの場合40枚)を$${n}$$としたとき、$${n\times n}$$の正方行列$${A}$$の各要素$${a_{i,j}}$$の要素を以下のように定義する。

$${k}$$回のシャッフルを行った際、シャッフル前に上から$${i}$$枚目にあったカードがシャッフル後に上から$${j}$$番目に移動していた回数

例えば、シャッフルをする前にデッキの1番上にあったカードがシャッフル後に上から9番目に移動していた場合、$${a_{1,9}}$$の数字を1つ増やす。
これを、シャッフルをする前にデッキの上から2番目にあったカード、3番目にあったカード、…と全てのカードに対して行う。
こうすることで1回のシャッフルの集計が完了する。
これを何回も繰り返し行うことで、行列$${A}$$を作成する。

カイ二乗適合検定

上記の方法で順番をデータに変換した。
このデータを用いて、本当に著者のシャッフルが無作為化できているかを確認するためにカイ二乗検定を用いた。
カイ二乗適合検定とはデータが予想されている割合になっているかを確認する検定であり、例えばダイスが歪んでいるかなどを検定できる。
カイ二乗検定について分かりやすく解説しているサイトがあるため、詳細に知りたい場合は以下のサイトを参照してもらいたい。

かなり大雑把な説明をすると、以下の式で定義される$${\chi^2}$$が特定の値の範疇に収まってなければ、そのデータは予想した分布に従っていないとする検定である。

$$
\chi^2=\sum_{i=1}^k\frac{(O_i-E_i)^2}{E_i}
$$

ここで$${O_i}$$は要素$${i}$$の観測度数、$${E_i}$$は要素$${i}$$の期待度数を表している。
用語のイメージがしやすいように、上のサイトにあるダイスの例で説明する。
ダイスが歪んでいるかを確認するために60回ダイスを振って片側5%のカイ二乗適合検定を行うこととした。
(本記事の本質ではないため、帰無仮説や対立仮説の説明については省略する。)
出目を調べた結果、それぞれの出目が以下のようになった。

1: 13回
2: 8回
3: 14回
4: 11回
5: 6回
6: 8回

ここで観測度数はそれぞれの出た目に対応するため、$${O_1\sim O_6=13, 8, 14, 11, 6, 8}$$となる。
また、60回ダイスをふったときそれぞれの目が出る回数の期待値は10回ずつであるため、$${E_1=E_2=\cdots E_6=10}$$となる。
そのため、$${\chi^2}$$は以下のように計算できる。

$$
\begin{array}{rcl}
\chi^2&=&\sum_{i=1}^6\frac{(O_i-E_i)^2}{E_i}\\
&=&\frac{(13-10)^2}{10}+\frac{(8-10)^2}{10}+\frac{(14-10)^2}{10}\\
&&+\frac{(11-10)^2}{10}+\frac{(6-10)^2}{10}+\frac{(8-10)^2}{10}\\
&=&0.9+0.4+1.6+0.1+1.6+0.4\\
&=&5.0
\end{array}
$$

6種類の出目が一様分布に従って出る歪みのないダイスの出目の自由度は5であるため、歪みのないダイスは自由度5の$${\chi^2}$$分布に従う。
以下のサイトで先ほど導出した$${\chi^2}$$の値の上側累積確率を求める。(上側累積確率は、計算した値の散らばり度が上位何パーセントに位置するかを示している。)

このサイトで計算をすると、上側累積確率は約41.6%となる。
片側5%の検定では上側累積確率が5%以下であると差があると判断するため、今回のダイスの出目の頻度は歪のないダイスでも出る範疇であるということが分かった。
(統計学的には不適切な表現を多分に含んでいるが、有識者の方には多めに見ていただきたい。)

シャッフルの結果を行列でまとめることで、100回のシャッフルをして1番上のカードが上から7枚目に移動した回数が3回だった、といった具合にシャッフルの結果をダイスでそれぞれの目が出た回数と同じようにカイ二乗適合検定ができるようになる。

検証

実際にプログラムに著者自身のシャッフルを再現させた上で、プログラム上の著者にデュエルマスターズのデッキ(40枚)で対戦前にするシャッフルを100万回させてカイ二乗適合検定を行った。

100万回シャッフルした際の行列$${A}$$は以下のようになった。

このデータに対して、片側カイ二乗適合検定を行った。
正しい無作為化がされている場合、シャッフル前に1番上のカードがシャッフル後にも1番上に戻る確率も、2番目にくる確率も、3番目に来る確率も等しく$${\frac{1}{40}}$$である。
そのため、行列$${A}$$の各要素$${a_{i,j}}$$の期待度数は$${\frac{1,000,000}{40}=25,000}$$となる。

上記のデータに対して$${\chi^2}$$の値を計算したところ、$${1550.99864}$$となった。
正しい無作為化がされている場合の行列$${A}$$の自由度は1599であるため、自由度1599の$${\chi^2}$$分布における上側累積確率を求めた。
上で紹介した計算サイトにて計算をした結果、上側累積確率は約80.1%となった。
上側累積確率が5%以下では無かったため、今回のデータは正しい無作為化をした場合でも起こり得る範疇であることがわかった。
すなわち、今回の結果だけ見れば著者のシャッフルは正しく無作為化できていると言える。

まとめ

今回は私のモノマネマシーンにシャッフルを100万回シャッフルをさせて、きちんとシャッフルできているかを確認してみました。
結果として、私のシャッフルは今回の評価方法ではきちんと無作為化ができているということがわかって安心しました。
ただし、今回の評価方法では「このカードの次にこのカードがきやすい」といった事象が起こり得ないことの証明はできていないため、良い評価方法があればまた実験してみたいと思います。

また、「結局どのくらいファローすればいいの？」ということは今回は調べてません。
そのため、自分のシャッフルが不安だ、相手のシャッフルが不十分だ、と感じた人はとりあえず僕と同じようにファロー3〜4回した後にパイルカウント(ディールシャッフル)をし、ファローを7〜10回するというのを実践してみてください。

過剰すぎると感じる人もいるかと思いますが、初対面の対戦相手との信頼関係はその時の行動によってのみ築かれます。
正しい無作為化は身の潔白を証明する唯一の手段であり、対戦相手の信頼をするための唯一の手段でもあります。
競技志向であるか否かに関わらず、ポケカのシティリーグやCLに出場する方は世界大会への切符をかけている大会であることを意識して入念にシャッフルしてください。

おわり。

この記事が気に入ったらサポートをしてみませんか？