UnityでFisher-Yates Shuffleアルゴリズムを実装してみた

最近は季節の変わり目なのか、寒暖の差が激しいですね。
ここしばらくブログの更新が滞っていました(汗)が、今日はUnity(というかC#で数学ネタ)を取り上げてみました。
ランダムシャッフルの実装です。

ちなみに、この記事の続きです。

Fisher-Yates Shuffle
Unityで実装
参考

Fisher-Yates Shuffle

ランダムなシャッフルって？

文字通り、リストの中身を無作為に並べ替えるということです。トランプの手札や数字の並べ替えなどが代表的な例ですね。

言葉にすれば簡単なのですが、では無作為なとはどういうことでしょうか？
要は並び方に意図や法則などが見当たらない、言ってしまえば毎回でたらめにパターンが出てくるというだけなのですが、言うは易し行うは難し、という典型例でこの「でたらめ」を作ることが本当に難しい。何せ、パターン自体の並び方はもとより、出現する組み合わせの順番にも気を付けなければならないからです。

例えば、1~4の4つの数字が入った配列を並び替えるとして、「1324, 4132, 2413,…」という結果が出たとします。
一見するとバラバラにも見えますが、よく見比べると「リストの要素を毎回右に一つずつずらす」という法則が分かります。そうするとこれはもうランダムとは言えなくなってしまいます。

どうやって作るのか？

プログラミングでランダムを生み出す際は、もっぱら乱数が使われます。

まあ、当然といえばそうなのですが、問題はその使い方。今回の場合、すぐに思いつくのは「乱数で適当な2要素の並べ替えを繰り返す」というものではないかと。何回か繰り返せばとりあえず中身が混ざるのではないかと考えてもおかしくはありません。

しかし、問題は並べ替えの回数。果たして何回行えば十分にシャッフルできたといえるでしょうか？例えば要素の数だけ実行したとして、実は不十分だったり、あるいは過剰に回しすぎているのかは分かりません。更には要素数が増えたらどうするかも不明です(ランダムシャッフル | Programming Place Plus　アルゴリズムとデータ構造編【その他のアルゴリズム】　第２章 )。

Fisher-Yates Shuffle

そこで、ロナルド・フィッシャーとフランク・イェーツという人物が考案した手法を元にコンピュータ用へ改良したアルゴリズムが「Fisher-Yates Shuffle」です。疑似コードは以下の通り(Wikipedia)。

要素数が n の配列 a をシャッフルする(添字は0からn-1):
  i を n - 1 から 1 まで減少させながら、以下を実行する
       j に 0 以上 i 以下のランダムな整数を代入する
       a&#91;j] と a&#91;i]を交換する

要素数が n の配列 a をシャッフルする(添字は0からn-1):

i を n - 1 から 1 まで減少させながら、以下を実行する

j に 0 以上 i 以下のランダムな整数を代入する

a[j] と a[i]を交換する

言い換えると「最後尾の要素から一つずつ順に、それより前の要素とランダムに並び替え」るという手法で、最大の利点はすべての要素が最低でも1回は並び替えの対象になるということです。交換対象の一つが最後尾から前に1個ずつ順番に選ばれるので、全要素が並び替えられる上、(前述の手法と比べて)乱数の生成回数も減るので処理の効率化にもつながります。

Unityで実装

では、このアルゴリズムを実装してみましょう。今回はUnityとC#を使ってみました。

空のオブジェクト作成

まずはC#スクリプトを作ります。空のゲームオブジェクト(Create Empty)を作成して、Add Componentボタンから「New Script」を選び、好きな名前を付けてから「Create and Add」ボタンで作成します。今回はRandomShuffleと名付けました。

C#スクリプトがAssetsフォルダに出てくるので、さっそくエディタで開いてみましょう。

C#スクリプトの編集

エディタでスクリプトを開いたら、C#でFisher-Yatesを実装します。下のコードをコピペすればOKです。
ちなみに、このコードは2種類のシャッフル方法(ランダム選択とFisher-Yates)を実装しています。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System.Linq;

public class RandomShuffle : MonoBehaviour
{
    class Pattern
    {
        /// <summary>
        /// パターン配列
        /// </summary>
        internal int[] sequence;
        /// <summary>
        /// 出現数(最初は1)
        /// </summary>
        internal int count = 1;

        internal Pattern() : this(new int[]{ 0 })
        {

        }
        internal Pattern(int[] seq)
        {
            sequence = seq;
        }

        /// <summary>
        /// LINQのSequenceEqualと同じ処理
        /// </summary>
        /// <param name="pat">比較対象</param>
        /// <returns>配列が全く同じ並びかどうか</returns>
        internal bool Match(int[] pat)
        {
            // 長さが異なる場合やnullの場合はfalse
            if (pat?.Length != sequence?.Length)
            {
                return false;
            }
            // 違う要素がどこかにあってもfalse
            for (int i = 0; i < sequence.Length; i++)
            {
                if (pat[i] != sequence[i])
                {
                    return false;
                }
            }
            return true;
        }
    }

    [System.Serializable]
    enum Mode { RANDOM, FISHERYATES, }

    /// <summary>
    /// シャッフルする図形
    /// </summary>
    [SerializeField]
    GameObject[] models;

    /// <summary>
    /// シャッフルモード
    /// </summary>
    [SerializeField]
    Mode mode = Mode.RANDOM;

    /// <summary>
    /// 試行回数
    /// </summary>
    [SerializeField, Range(0, 100000)]
    int trials = 1000;

    /// <summary>
    /// 各試行のフレーム間隔
    /// </summary>
    [SerializeField, Range(1, 60)]
    int cycle = 1;

    List<Pattern> patterns = new List<Pattern>();

    // Start is called before the first frame update
    void Start()
    {
        //もし何も登録されてなかったら
        if (models == null || models.Length <= 0)
        {
            //立方体と円柱と球体の3種類を作る
            models = new GameObject[3];
            models[0] = GameObject.CreatePrimitive(PrimitiveType.Cube);
            models[1] = GameObject.CreatePrimitive(PrimitiveType.Cylinder);
            models[2] = GameObject.CreatePrimitive(PrimitiveType.Sphere);
        }
    }

    // Update is called once per frame
    void Update()
    {
        // 残り回数が 0になるまで、かつフレーム数が変数cycleの倍数になったら
        if (trials > 0 && Time.frameCount % cycle == 0)
        {
            // 回数の更新
            trials--;

            // シャッフルする配列の初期化
            var pat = new int[models.Length];
            // 配列は0 ~ (あらかじめ入れたモデル数)
            for (int i = 0; i < pat.Length; i++)
            {
                pat[i] = i;
            }

            // Fisher-Yates Shuffle
            if (mode == Mode.FISHERYATES)
            {
                ShuffleFisherYates(pat);
            }
            // ランダムに交換を繰り返す
            else
            {
                ShuffleRandom(pat);
            }

            // 同じパターンがあるか検索
            var index = patterns.FindIndex(s => s.sequence.SequenceEqual(pat));
            //一応、自作の比較関数でも
            //var index = patterns.FindIndex(s => s.Match(pat));    
            // なかったら追加
            if (index < 0)
            {
                patterns.Add(new Pattern(pat));
            }
            // あれば既存のパターンの出現数をカウント
            else
            {
                patterns[index].count++;
            }

            // シャッフルしたリストに基づき図形を並べ替え
            for (int i = 0; i < pat.Length; i++)
            {
                var num = pat[i];
                // スクリプトがつけられたオブジェクトの位置を基準にX軸方向へずらす
                // ずらす幅は好みで調整
                models[num].transform.position = transform.position + new Vector3(i * 2, 0, 0);
            }

            // 0になったら結果表示
            if (trials == 0)
            {
                // 試行回数と出現総数が同じか比較
                var sum = patterns.Sum(s => s.count);
                Debug.Log("Total Count: " + sum);
                // 各パターンの統計
                for (int i = 0; i < patterns.Count; i++)
                {
                    Debug.LogFormat("Mode({0}) -> pattern: [{1}], count: {2}, rate: {3}%", 
                        // アルゴリズム, 数列パターン、出現回数、割合
                        mode.ToString(), string.Join(",", patterns[i].sequence.Select(s => s.ToString())), patterns[i].count, patterns[i].count * 100 / (double)sum);
                }
                // 頻度が最大と最小のパターンの差
                var diff = (patterns.Max(s => s.count) - patterns.Min(s => s.count)) * 100 / (double)sum;
                Debug.Log("Rate difference: " + diff + "%");
            }
        }
    }

    /// <summary>
    /// 配列からランダムに2つ選んで交換。偏りが出やすい
    /// </summary>
    /// <typeparam name="T">数値型</typeparam>
    /// <param name="list">シャッフルしたいリスト</param>
    void ShuffleRandom<T>(IList<T> list) where T : struct
    {
        for (int i = 0; i < list.Count; i++)
        {
            var k = Random.Range(0, list.Count);
            var n = Random.Range(0, list.Count);
            // 値の交換
            T temp = list[k];
            list[k] = list[n];
            list[n] = temp;
        }
    }

    /// <summary>
    /// Fisher-Yates Shuffleアルゴリズムによるランダムシャッフル。偏りがほとんどない
    /// </summary>
    /// <typeparam name="T">数値型</typeparam>
    /// <param name="list">シャッフルしたいリスト</param>
    void ShuffleFisherYates<T>(IList<T> list) where T : struct
    {
        var n = list.Count;
        // n を list.Count から 2 までループさせる
        while(n-- > 1)
        {
            // 0 <= k < n+1
            var k = Random.Range(0, n + 1);
            // 値の交換
            T temp = list[k];
            list[k] = list[n];
            list[n] = temp;
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

using System.Collections;

using System.Collections.Generic;

using UnityEngine;

using System.Linq;

public class RandomShuffle : MonoBehaviour

{

class Pattern

{

/// <summary>

/// パターン配列

/// </summary>

internal int[] sequence;

/// <summary>

/// 出現数(最初は1)

/// </summary>

internal int count = 1;

internal Pattern() : this(new int[]{ 0 })

{

}

internal Pattern(int[] seq)

{

sequence = seq;

}

/// <summary>

/// LINQのSequenceEqualと同じ処理

/// </summary>

/// <param name="pat">比較対象</param>

/// <returns>配列が全く同じ並びかどうか</returns>

internal bool Match(int[] pat)

{

// 長さが異なる場合やnullの場合はfalse

if (pat?.Length != sequence?.Length)

{

return false;

}

// 違う要素がどこかにあってもfalse

for (int i = 0; i < sequence.Length; i++)

{

if (pat[i] != sequence[i])

{

return false;

}

return true;

}

[System.Serializable]

enum Mode { RANDOM, FISHERYATES, }

/// <summary>

/// シャッフルする図形

/// </summary>

[SerializeField]

GameObject[] models;

/// <summary>

/// シャッフルモード

/// </summary>

[SerializeField]

Mode mode = Mode.RANDOM;

/// <summary>

/// 試行回数

/// </summary>

[SerializeField, Range(0, 100000)]

int trials = 1000;

/// <summary>

/// 各試行のフレーム間隔

/// </summary>

[SerializeField, Range(1, 60)]

int cycle = 1;

List<Pattern> patterns = new List<Pattern>();

// Start is called before the first frame update

void Start()

{

//もし何も登録されてなかったら

if (models == null || models.Length <= 0)

{

//立方体と円柱と球体の3種類を作る

models = new GameObject[3];

models[0] = GameObject.CreatePrimitive(PrimitiveType.Cube);

models[1] = GameObject.CreatePrimitive(PrimitiveType.Cylinder);

models[2] = GameObject.CreatePrimitive(PrimitiveType.Sphere);

}

// Update is called once per frame

void Update()

{

// 残り回数が 0になるまで、かつフレーム数が変数cycleの倍数になったら

if (trials > 0 && Time.frameCount % cycle == 0)

{

// 回数の更新

trials--;

// シャッフルする配列の初期化

var pat = new int[models.Length];

// 配列は0 ~ (あらかじめ入れたモデル数)

for (int i = 0; i < pat.Length; i++)

{

pat[i] = i;

}

// Fisher-Yates Shuffle

if (mode == Mode.FISHERYATES)

{

ShuffleFisherYates(pat);

}

// ランダムに交換を繰り返す

else

{

ShuffleRandom(pat);

}

// 同じパターンがあるか検索

var index = patterns.FindIndex(s => s.sequence.SequenceEqual(pat));

//一応、自作の比較関数でも

//var index = patterns.FindIndex(s => s.Match(pat));

// なかったら追加

if (index < 0)

{

patterns.Add(new Pattern(pat));

}

// あれば既存のパターンの出現数をカウント

else

{

patterns[index].count++;

}

// シャッフルしたリストに基づき図形を並べ替え

for (int i = 0; i < pat.Length; i++)

{

var num = pat[i];

// スクリプトがつけられたオブジェクトの位置を基準にX軸方向へずらす

// ずらす幅は好みで調整

models[num].transform.position = transform.position + new Vector3(i * 2, 0, 0);

}

// 0になったら結果表示

if (trials == 0)

{

// 試行回数と出現総数が同じか比較

var sum = patterns.Sum(s => s.count);

Debug.Log("Total Count: " + sum);

// 各パターンの統計

for (int i = 0; i < patterns.Count; i++)

{

Debug.LogFormat("Mode({0}) -> pattern: [{1}], count: {2}, rate: {3}%",

// アルゴリズム, 数列パターン、出現回数、割合

mode.ToString(), string.Join(",", patterns[i].sequence.Select(s => s.ToString())), patterns[i].count, patterns[i].count * 100 / (double)sum);

}

// 頻度が最大と最小のパターンの差

var diff = (patterns.Max(s => s.count) - patterns.Min(s => s.count)) * 100 / (double)sum;

Debug.Log("Rate difference: " + diff + "%");

}

/// <summary>

/// 配列からランダムに2つ選んで交換。偏りが出やすい

/// </summary>

/// <typeparam name="T">数値型</typeparam>

/// <param name="list">シャッフルしたいリスト</param>

void ShuffleRandom<T>(IList<T> list) where T : struct

{

for (int i = 0; i < list.Count; i++)

{

var k = Random.Range(0, list.Count);

var n = Random.Range(0, list.Count);

// 値の交換

T temp = list[k];

list[k] = list[n];

list[n] = temp;

}

/// <summary>

/// Fisher-Yates Shuffleアルゴリズムによるランダムシャッフル。偏りがほとんどない

/// </summary>

/// <typeparam name="T">数値型</typeparam>

/// <param name="list">シャッフルしたいリスト</param>

void ShuffleFisherYates<T>(IList<T> list) where T : struct

{

var n = list.Count;

// n を list.Count から 2 までループさせる

while(n-- > 1)

{

// 0 <= k < n+1

var k = Random.Range(0, n + 1);

// 値の交換

T temp = list[k];

list[k] = list[n];

list[n] = temp;

}

オブジェクトの配置と設定

スクリプトを編集したら、CGモデルを配置してみましょう。
今回はテストなのでプリミティブ(立方体、球体、カプセル、円錐)を配置してみました。場所はどこでも構いません。

そのあとはスクリプトの設定をします。設定項目と役割は以下の通りです。

Models: シャッフルの対象となるオブジェクト
Mode: シャッフル方法(ランダム交換 or Fisher-Yates)
Trials: シャッフルの試行回数
Cycle: 各試行のフレーム間隔(次のシャッフルまで何フレーム空けるか)

Modelsには、要素数を指定してから対象のゲームオブジェクトを割り当てます。今回は直前で配置したプリミティブを指定しましょう。また、プリミティブをRandomShuffle(が割り当てられたゲームオブジェクト)の子要素にしておくと後々扱いやすくなります。

Modeはシャッフル方法の選択です。ランダム交換の繰り返しとFisher-Yatesのどちらかをドロップダウンメニューで選べます。

また、Trialsで試行回数を、Cycleで各試行のフレーム間隔を指定します。試行回数が増えれば(Fisher-Yatesでの)パターンのばらつきが減少していき、フレーム間隔が増えればシャッフルがゆっくり実行されていきます。
なお、シャッフル時間 = Trials / (FPS / Cycle) と概算できるので、時間に注意しながら設定しましょう。

シャッフル方法の比較

プリミティブの割り当てと親子付けが終わったら、Ctrl+Dで複製します。また、複製したオブジェクトを少し上に移動しておきます。

上に移動したら、Modeをコピー元とは別のシャッフル方法にしておきます。

テスト

設定が完了したら、さっそく実行してみましょう。

UnityでFisher Yatesアルゴリズムを試してみた

プリミティブがランダムに並べ替えられていく様子が見られます。

シャッフルが終わると、各パターンの出現数と割合、そして最多と最少パターンの偏差を出してくれます。今回はランダム交換で約6.3%(=19回)、Fisher-Yatesで約4.3%(=13回)でした。

思ったより偏りが多いなと思われる方もいらっしゃるかもしれませんが、試行回数が300と少ないことに起因するものです。実際、Trialsを1000や10000と増やしていくとFisher-Yatesでは偏りがより少なくなる一方で、ランダム交換ではまだ偏差が出てしまうので、Fisher-Yatesの効果の高さがうかがえます。

カードゲームの作成などでシャッフル方法を探していた方は、ぜひ一度お試しあれ。