「ズンドコキヨシ」と擬似乱数

最近はやりものらしい「ズンドコキヨシ¹」を Go 言語で実装することを考える。既に Qiita でも様々な実装があるが，今回は素朴に

zundoko.go

package main

import (
    "fmt"
    "math/rand"
    "time"
)

const (
    zun     = "ズン"
    doko    = "ドコ"
    kiyoshi = "キ・ヨ・シ！"
)

func generate() chan string {
    ch := make(chan string)
    go func() {
        var zundoko = [2]string{zun, doko}
        rand.Seed(time.Now().UnixNano())
        for {
            ch <- zundoko[rand.Intn(2)]
        }
    }()
    return ch
}

func main() {
    zundoko := generate()
    zcount := 0
    for {
        zd := <-zundoko
        fmt.Print(zd)
        if zd == zun {
            zcount++
        } else if zcount >= 4 {
            break
        } else {
            zcount = 0
        }
    }
    fmt.Print(kiyoshi)
}

としてみた。実行例は以下のとおり。

$ go run zundoko.go
ドコズンドコズンズンドコズンズンドコドコズンドコドコドコズンズンズンズンドコキ・ヨ・シ！

この処理の内容については本家ブログで解説している。

• 「ズンドコチェック」なるものが流行っているらしい — プログラミング言語 Go | text.Baldanders.info

今回は「ズン」「ドコ」の配列を生成している部分 generate() のうち擬似乱数について紹介しておく。

線形合同法（Linear Congruential Generators）

math/rand パッケージで既定で使われている擬似乱数アルゴリズムはちょっと特殊な線形合同法（Linear Congruential Generators; LCGs）らしい。

• [Announce] A rand package for high quality 64bit random numbers (possibly go2) - Google グループ

線形合同法は実装レベルで優劣が分かれるのだが，そもそも線形合同法の問題はある乱数がその前の乱数の影響を強く受けてしまう点にある。今回の「ズンドコキヨシ」に引き寄せて言うなら，「ズン」が4回続いた後に「ドコ」が来る確率が 1/2 にならないのである²。

追記で訂正（2017-03-21）

本家ブログで取り上げたのだが

• モンテカルロ法による円周率の推定（その4 PRNG） — プログラミング言語 Go | text.Baldanders.info

math/rand のアルゴリズムは線形合同法ではなく「ラグ付フィボナッチ法（Lagged Fibonacci Generator）」の一種らしい。ラグ付フィボナッチ法は線形合同法の改良版とされている。

メルセンヌ・ツイスタ（Mersenne Twister）

線形合同法の欠点を克服すべく様々な擬似乱数アルゴリズムが考えだされた。そうしたアルゴリズムでかなり性能が良いと言われているアルゴリズムのひとつが松本眞，西村拓士両氏によって発表されたメルセンヌ・ツイスタ（Mersenne Twister; MT）である³。

• Mersenne Twister: A random number generator (since 1997/10)

Go 言語の標準パッケージはメルセンヌ・ツイスタをサポートしていないが， seehuhn/mt19937 パッケージでメルセンヌ・ツイスタが使える⁴。

実は math/rand パッケージは以下の interface を持つ任意の擬似乱数生成パッケージを使うことができる。

// A Source represents a source of uniformly-distributed
// pseudo-random int64 values in the range [0, 1<<63).
type Source interface {
    Int63() int64
    Seed(seed int64)
}

したがって，最初に示した generate() は以下のように書き換えられる。

import (
    "math/rand"
    "time"

    "github.com/seehuhn/mt19937"
)

func generate() chan string {
    ch := make(chan string)
    go func() {
        var zundoko = [2]string{zun, doko}
        r := rand.New(mt19937.New())
        r.Seed(time.Now().UnixNano())
        for {
            ch <- zundoko[r.Intn(2)]
        }
    }()
    return ch
}

メルセンヌ・ツイスタは科学シミュレーション（モンテカルロ法など）でよく使われるほか，ゲーム内の乱数生成器としても使われているようである。

もうひとつの rand パッケージ

線形合同法にしろメルセンヌ・ツイスタにしろエントロピー源として与えられる seed が同じなら同じ値になってしまう。暗号用に乱数を生成するためにはエントロピー源の与え方を工夫する必要がある。また得られた乱数をそのまま使うのもよくないと言われている。

Go 言語では暗号用に crypto/math パッケージを用意している。 crypto/math パッケージは math/rand パッケージとは互換性がない⁵。

ブックマーク

• 良い乱数・悪い乱数
  • 悪い乱数のリスクを視覚的に明らかにする
• Big Sky :: Mersenne Twister のライセンスが変更された
• MSC30-C. 疑似乱数の生成に rand() 関数を使用しない
• RFC 4086 - Randomness Requirements for Security （IPA による日本語訳）
• サイコロを振るのは簡単である、しかし、ゲームでサイコロを実装するにはサイコロを知らなければならない - Qiita

脚注

---

1. 「ズンドコキヨシ」「キヨシチェック」「ズンドコチェック」などと呼ばれているらしいが，今回は「ズンドコキヨシ」で統一する。 ↩

2. 線形合同法には本当にいろいろな実装があり，古い UNIX 処理系では生成した乱数の最下位ビットが 1 と 0 交互に出現するらしい。この場合，永遠に「ズンドコキヨシ」が終わらないことになる。線形合同法の改良版（math/rand もそのひとつ）では過去に指摘された問題は緩和される傾向にあるがアルゴリズム上の欠陥はどうしようもない。 ↩

3. 現在は改良版である SIMD-oriented Fast Mersenne Twister (SFMT) が公開されている。またソースコードが BSD ライセンスで提供されている。 ↩

4. メルセンヌ・ツイスタのオリジナルコードは BSD または MIT のデュアル・ライセンスで提供されているが， seehuhn/mt19937 パッケージのライセンスは GPLv3 なので取り扱いに注意が必要である。 ↩

5. crypto/math は乱数生成用のエントロピー源にハードウェア・デバイスを使用する。 UNIX 系のプラットフォームでは /dev/urandom を参照する。 Windows プラットフォームでは CryptGenRandom を使うようだが，この API の内部実装は公開されていない。やれやれ。 ↩