変種オセロをSwiftに移植してみた。（その10）

昨日はプレイヤーの実装。

今日はランダムAIを実装していく。

乱数の取得

さて、ランダムAIを実装するのだけど、やはりRubyのArray#sampleのような気の利いたメソッドはないわけで。

ということで、まずは乱数の取得から。

乱数の話

乱数といえば、srand()で初期化してrand()で乱数を取得するというのが定番だと思ってたけど、どうやらこの方法はよくないらしい。
というのも、昔のrand()の実装だと、上位ビットの方があまりランダムになってないらしいから。
これが改善されたのがsrandom()やrandom()らしいのだけど、これもあまりよくないらしい。
なぜかというと、乱数の生成方法と過去の出力から、未来の出力が予測可能だかららしい。
乱数の生成方法と過去の出力が分かっても未来の出力が予測不可能な乱数を暗号論的擬似乱数というみたいで、arc4random()を使うことで、こういった乱数を得ることが出来るみたい。

ただ、Xcodeのドキュメントを検索してみると、SecRandomCopyBytes()という関数を使う方法がヒットして、arc4random()を使うことについての言及がない・・・（一応、man pageはヒットする）
このSecRandomCopyBytes()という関数も暗号論的擬似乱数のバイト列を取得できる関数で、こちらはXcodeに言及するドキュメントが用意されているので、今回はこちらを使うことにした。

SecRandomCopyBytes()

とはいうものの、SecRandomCopyBytes()の具体的な使い方が書かれていない。

SecRandomCopyBytes()のインタフェースは、以下のような感じ。

func SecRandomCopyBytes(_ rnd: SecRandomRef,
                      _ count: Int,
                      _ bytes: UnsafeMutablePointer<UInt8>) -> Int32

第1引数はkSecRandomDefaultというオブジェクトを渡すみたいで、第2引数は取得する乱数のバイト列のサイズ、そして第3引数は取得した乱数のバイト列を格納するバッファのポインタを渡すというインタフェースらしい。
そして、成功した場合は0が、失敗した場合は-1が、戻り値として返ってくる。

じゃあ、どうすればUInt32の乱数が得られるんだろうと試行錯誤したところ、次のようにすればいい感じだった。

// バッファを確保し、そのポインタを取得
var buf = UnsafeMutablePointer<UInt32>.alloc(1)
// ポインタをUInt8のポインタにキャストして、
// SecRandomCopyBytes()を呼び出す
SecRandomCopyBytes(kSecRandomDefault, 4, UnsafeMutablePointer<UInt8>(buf))
// バッファの値を読み出す
let randomValue = buf.memory
// バッファを解放
buf.dealloc(1)

C言語に置き換えると、これは次のようなコードになっている。

uint32_t* buf = (uint32_t*)malloc(sizeof(uint32_t) * 1);
SecRandomCopyBytes(kSecRandomDefault, 4, (uint8_t*)buf);
uint32_t randomValue = *buf;
free(buf);

重要なのは、ポインタのキャスト。
UnsafeMutablePointerにはイニシャライザとしてUnsafeMutablePointer<T>#init<U>(_: UnsafeMutablePointer<U>)というものが用意されていて、これで別の型のポインタにキャストをすることが出来る。

上限値のある乱数

上記の方法で得られる乱数は0x0000_0000〜0xffff_ffffまでの乱数なので、実際には乱数を配列のサイズに収めないといけない。
こういった、0以上、上限値未満の乱数を得たい場合、よくやる方法は得られた乱数を上限値で割った余りを使うという方法。
ただ、この方法は問題があるみたいなので、改善が必要。

なんでこの方法に問題があるのかというと、例えば0〜9の乱数を生成する生成器があったとして、0以上6未満の乱数を得たいときに、6で割り算した余りを使うと

乱数が0, 6 → 0
乱数が1, 7 → 1
乱数が2, 8 → 2
乱数が3, 9 → 3
乱数が4 → 4
乱数が5 → 5

となって、4と5の出る確率が低くなってしまうから。
このように、上限値が乱数で生成されうる数の個数をちょうど割り切れないと、乱数に偏りが出てしまう。

これを防ぐために、arc4random()にはarc4random_uniform()という関数も用意されているみたいだけど、SecRandomCopyBytes()を使うのなら、相当する関数を自分で用意してやらないといけない。

じゃあ、どうすればいいのかというと、簡単な方法として、上限値で乱数が生成される範囲を区切っていったときに、余りとなる数字（先ほどの例なら6〜9）にヒットした場合は無視して、新しい乱数を取得するという方法があるみたい。

コードで書くと、次のような感じ。

let uniformedRandomValue: UInt32
let ignoreRegion = 0xffff_ffff - 0xffff_ffff % upperBound
while true {
  let randomValue = (0x0000_0000〜0xffff_ffffの乱数を生成する)
  if randomValue < ignoreRegion {
    uniformedRandomValue = randomValue % upperBound
    break
  }
}

Arrayの拡張

ここまでを踏まえて、Arrayを拡張してArray#sample()というメソッドを用意した。

/* RandomCom.swift */

import Security

private func getUniformedRandom(upperBound: UInt32) -> UInt32 {
  let ignoreRegion = 0xffff_ffff - 0xffff_ffff % upperBound

  while true {
    var buf = UnsafeMutablePointer<UInt32>.alloc(1)
    SecRandomCopyBytes(kSecRandomDefault, 4, UnsafeMutablePointer<UInt8>(buf))
    let randomValue = buf.memory
    buf.dealloc(1)
    if randomValue < ignoreRegion {
      return randomValue % upperBound
    }
  }
}

extension Array {
  private func sample() -> T {
    let index = getUniformedRandom(UInt32(self.count))
    return self[Int(index)]
  }
}

// 続く

ちょっとハマったのが、Arrayの拡張の書き方。
拡張の宣言を開始する部分で、型パラメータのTは書かないっぽい。
（けど、sample()の戻り値の型として型パラメータのTを使っているので、なんか変な感じ）

ランダムAIの実装

Array#sample()の拡張さえ出来てしまえば、あとは簡単。

// 続き

public class RandomCom: Player {
  public func select(board: Board) -> Board.Action? {
    let action = board.legalActions.sample()
    switch action {
    case .Pass:
      println("pass.")
    case let .Play(row, col):
      println("play (\(row), \(col)).")
    case let .Change(row, col):
      println("change (\(row), \(col)).")
    }
    return action
  }
}

これでランダムAIが実装できた。

今日はここまで！

いものやま。

雑多な知識の寄せ集め