mizdra's blog

ぽよぐらみんぐ

Scalaで乱数ツールを書く話

はじめに

この記事はPokémon RNG Advent Calendar 2017 10日目の記事です.

adventar.org

乱数調整で楽しむ方々の間では乱数調整を支援するツールのことを乱数ツールと呼んでいます. 僕も乱数ツールを作成する内の1人であり, 時々ツールを作成しますがツールのソースコードはどうしても複雑になりがちです. たかが計算ツールといえども綺麗に書きたいですよね.

この記事ではScalaを使い, 乱数ツールを綺麗に書いてみる話をします.

…あれ?🤔

Adventarのコメント欄にはデザインパターンの話をするって書いてあったはずなのにScalaの話?🤔

デザインパターンは???🤔🤔🤔

f:id:mizdra:20171210234047p:plain
証拠です

…申し訳ありませんが今回はテーマを変えて記事を書いています🙇 本当はデザインパターンの話を書こうと思っていたのですが記事に出来るほど知見が溜まっていなかったのでボツ 🚮 となりました. デザインパターンについてはまたいつか別の機会に話そうと思います 🙏

…さて話を戻します. なぜScalaを使って乱数ツールを書くかというと, Scalaには非常に充実したコレクションライブラリが備わっており, これを用いることで乱数列に対する複雑な操作を簡単に記述できるからです*1. 乱数ツールを記述していく中で, このコレクションライブラリがいかに力を発揮していくかを感じでもらえればと思います.

前提

Iteratorを継承したLCGを作成する

まずは乱数生成器(LCG)を作成しましょう. LCGクラスにIteratorトレイトを継承させることで, 乱数列をコレクションとして扱うことができます. そうすることで, コレクションライブラリで提供される非常に多くの便利なメソッドがLCGクラスで利用できるようになります.

class LCG(seed: Int, a: Int, b: Int) extends Iterator[Int] {
  var state: Int = seed

  override def hasNext: Boolean = true
  override def next(): Int = {
    state = state * a + b
    state
  }
  def next(n: Int): Int = java.lang.Integer.remainderUnsigned(this.next(), n)
}

object Wandbox {
  def main(args: Array[String]): Unit = {
    val lcg = new LCG(0x00000000, 0x41c64e6d, 0x6073)
    println(lcg.take(5).map(_.toHexString).toList)
    // stdout: List(6073, e97e7b6a, 52713895, 31b0dde4, 8e425287)
  }
}

サンプルコードの例ではコレクションのメソッド take(), map(), toList() を使用して先頭5つの乱数を16進数表記で出力しています.

調律された乱数列を取得する

通常ではLCGで得られる生の乱数列は乱数性に問題があるため, 下半分のbitを切り落として利用されます. これを先程作成したLCGクラスを用いて書くと以下のようになります.

object Wandbox {
  def temper(state: Int): Int = state >>> 16
  
  def main(args: Array[String]): Unit = {
    val lcg = new LCG(0x00000000, 0x41c64e6d, 0x6073)
    val temperedLcg = (new LCG(0x00000000, 0x41c64e6d, 0x6073)).map(temper(_))
    
    println(lcg.take(5).map(_.toHexString).toList)
    // stdout: List(6073, e97e7b6a, 52713895, 31b0dde4, 8e425287)
    println(temperedLcg.take(5).map(_.toHexString).toList)
    // stdout: List(0, e97e, 5271, 31b0, 8e42)
  }
}

写像を表わす map() メソッドを用いて生の乱数を調律後の値へと変換しています. たったこれだけで, 生の乱数列を調律された乱数列に変換できます.

ただし, これでは map() によって返ってくる型が Iterator[Int] となってしまい, LCGクラスで実装したメソッド (def next(n: Int): Int など) を呼び出せなくなってしまいます. これは後々困ったことになるのでここではLCGクラスを継承して調律された乱数列を生成するTemperedLCGクラスを作成することにしましょう.

class TemperedLCG(seed: Int, a: Int, b: Int) extends LCG(seed, a, b) {
  override def next(): Int = super.next() >>> 16
}

object Wandbox {
  def main(args: Array[String]): Unit = {
    val lcg = new LCG(0x00000000, 0x41c64e6d, 0x6073)
    val temperedLcg = new TemperedLCG(0x00000000, 0x41c64e6d, 0x6073)
    
    println(lcg.take(5).map(_.toHexString).toList)
    // stdout: List(6073, e97e7b6a, 52713895, 31b0dde4, 8e425287)
    println(temperedLcg.take(5).map(_.toHexString).toList)
    // stdout: List(0, e97e, 5271, 31b0, 8e42)
  }
}

fork() メソッドを実装する

LCGインスタンスはmutableな操作をするので, そのまま複数のスレッドに渡すと破滅します. 次は乱数列上の5つの乱数を出力する処理を, 1消費ずつずらしながら各々のスレッドで実行する例です*2.

// 破滅する例
object Wandbox {
  def printRands(lcg: LCG, n: Int) = println(for (i <- 1 to n) yield lcg.next())
  
  def main(args: Array[String]): Unit = {
    val lcg = new LCG(0x00000000, 1, 1)
    
    (1 to 3).map(_ => {
      val f = Future {
        printRands(lcg, 5)
      }
      lcg.drop(1) // 1つずらす
      f
    }).foreach(Await.ready(_, Duration.Inf))
    // stdout:
    // Vector(4, 5, 6, 7, 8)
    // Vector(9, 10, 11, 12, 13)
    // Vector(14, 15, 16, 17, 18)
    
    // 本当は次のようになって欲しい(行については順不同):
    // Vector(1, 2, 3, 4, 5)
    // Vector(2, 3, 4, 5, 6)
    // Vector(3, 4, 5, 6, 7)
  }
}

そこで自身のクローンを作成する fork() メソッドを実装してクローンをスレッドに渡すようにしてみましょう.

import scala.concurrent._
import ExecutionContext.Implicits.global
import scala.concurrent.duration.Duration

class LCG(seed: Int, a: Int, b: Int) extends Iterator[Int] {
  // ...
  def fork(): LCG = new LCG(state, a, b)
}

class TemperedLCG(seed: Int, a: Int, b: Int) extends LCG(seed, a, b) {
  // ...
  override def fork(): TemperedLCG = new TemperedLCG(state, a, b)
}

// 破滅しない例
object Wandbox {
  def printRands(lcg: LCG, n: Int) = println(for (i <- 1 to n) yield lcg.next())
  
  def main(args: Array[String]): Unit = {
    val lcg = new LCG(0x00000000, 1, 1)
    
    (1 to 3).map(_ => {
      val forkedLcg = lcg.fork()
      val f = Future {
        printRands(forkedLcg, 5)
      }
      lcg.drop(1) // 1つずらす
      f
    }).foreach(Await.ready(_, Duration.Inf))
    // stdout:
    // Vector(1, 2, 3, 4, 5)
    // Vector(3, 4, 5, 6, 7)
    // Vector(2, 3, 4, 5, 6)
  }
}

これで並列処理でも安全にLCGインスタンスを扱うことができます.

作成したLCGをエンカウント処理で使う

ここまで作成したLCGクラスを使って3世代の野生乱数の処理を書いてみましょう. 問題を簡単にするために次のような仕様で処理を書くことにします.

  • seedは 0x00000000
  • 検索する消費数の範囲は 1 〜 100000
  • CDS個体値がVのものを検索
  • 並列処理する

…と簡単にしたと言ってもなかなか複雑そうなプログラムになりそうですが, ここでもScalaのコレクションライブラリの力が発揮されます. コードを見てみましょう*3.

class LCG(seed: Int, a: Int, b: Int) extends Iterator[Int] { ... }

class TemperedLCG(seed: Int, a: Int, b: Int) extends LCG(seed, a, b) { ... }

// エンカウントデータ
case class Encounter(frame: Int, slot: Int, level: Int, nature: Int, pid: Int, ivs: Seq[Int], item: Int) {
  override def toString(): String = {
    s"frame: $frame, slot: $slot, level: $level, nature: $nature, pid: ${pid.toHexString}, ivs: ${ivs.mkString("(", ", ", ")")}, item: $item"
  }
}

// エンカウントデータを生成するBuilder
class EncounterBuilder(wantedIvs: Seq[Range]) {
  var frame: Int = 0
  var slot: Int = 0
  var level: Int = 0
  var nature: Int = 0
  var pid: Int = 0
  var ivs: Seq[Int] = Nil
  var item: Int = 0
  def frame(frame: Int): Unit = this.frame = frame
  def slot(slot: Int): Unit = this.slot = slot
  def level(level: Int): Unit = this.level = level
  def nature(nature: Int): Unit = this.nature = nature
  def pid(pid: Int): Unit = this.pid = pid
  def ivs(ivs: Seq[Int]): Unit = this.ivs = ivs
  def item(item: Int): Unit = this.item = item

  def result(): Option[Encounter] = {
    // 個体値が条件を満たしていなければ None を返す
    val isValidIvs = (wantedIvs zip ivs).forall({ case (range, iv) => range.contains(iv) })
    if (isValidIvs) Some(Encounter(frame, slot, level, nature, pid, ivs, item))
    else None
  }
}

object Wandbox {
  def printRands(lcg: LCG, n: Int) = println(for (i <- 1 to n) yield lcg.next())
  def getPID(lid: Int, hid: Int): Int = lid.toInt | (hid.toInt << 16)
  def isValidPID(pid: Int, nature: Int): Boolean = java.lang.Integer.remainderUnsigned(pid, 25) == nature
  def getIVs(rand: Int): (Int, Int, Int) = ((rand >> 10) & 0x1F, (rand >> 5) & 0x1F, rand & 0x1F)
  def searchEncounter(lcg: LCG, builder: EncounterBuilder, frame: Int) = {
    builder.frame(frame)
    
    // 出現スロット, レベル, 性格の決定
    builder.slot(lcg.next(100))
    builder.level(lcg.next())
    val nature = lcg.next(25)
    builder.nature(nature)
    
    // (pid % 25) == nature となるような PID を探す
    val pid: Int = lcg
      .grouped(2) // List(LID, HID) の組にする
      .map(iter => getPID(iter.head, iter.tail.head))
      .find(pid => isValidPID(pid, nature))
      .get // 必ずPIDが見つかることが保証されているので getOrElse の代わりに get を使っている
    builder.pid(pid)
    
    // 個体値決定
    val (b, a, h) = getIVs(lcg.next())
    val (d, c, s) = getIVs(lcg.next())
    builder.ivs(Vector(h, a, b, c, d, s))
    
    lcg.drop(5) // 5つの乱数をスキップ
    
    // 持ち物の決定
    builder.item(lcg.next(100))
    
    // 個体が条件を満たしていれば Some(Encounter), そうでなければ None が返る
    builder.result()
  }
  
  def main(args: Array[String]): Unit = {
    val lcg = new TemperedLCG(0x00000000, 0x41c64e6d, 0x6073)
    val wantedIvs = Vector( // 検索する個体値の範囲
      0 to 31,  // h
      0 to 31,  // a
      0 to 31, // b
      31 to 31, // c
      31 to 31, // d
      31 to 31  // s
    )
    val maxFrame = 100000
    
    val results: Seq[Encounter] = (1 to maxFrame).map(frame => {
      val forkedLcg = lcg.fork()
      val builder = new EncounterBuilder(wantedIvs)
      val f: Future[Option[Encounter]] = Future {
        searchEncounter(forkedLcg, builder, frame)
      }
      lcg.drop(1) // 1つずらす
      f
    }).map(Await.result(_, Duration.Inf)).flatten
    
    results.foreach(println _)
  }
}

出力

frame: 15506, slot: 40, level: 7292, nature: 0, pid: d000755f, ivs: (6, 27, 31, 31, 31, 31), item: 38
frame: 15530, slot: 86, level: 27437, nature: 0, pid: d000755f, ivs: (6, 27, 31, 31, 31, 31), item: 38
frame: 15540, slot: 72, level: 47192, nature: 0, pid: d000755f, ivs: (6, 27, 31, 31, 31, 31), item: 38
frame: 31693, slot: 21, level: 43592, nature: 1, pid: 44b35699, ivs: (2, 19, 18, 31, 31, 31), item: 64
frame: 36963, slot: 73, level: 6376, nature: 9, pid: 8e20683d, ivs: (13, 7, 24, 31, 31, 31), item: 43
frame: 36983, slot: 85, level: 41274, nature: 9, pid: 8e20683d, ivs: (13, 7, 24, 31, 31, 31), item: 43
frame: 36993, slot: 90, level: 26931, nature: 9, pid: 8e20683d, ivs: (13, 7, 24, 31, 31, 31), item: 43

乱数列からエンカウントデータを生成する searchEncounter() では, Builderパターンを用いています*4. PIDの決定では grouped() メソッドを使い, コレクションを (LID, HID) の組にすることで2つずつ乱数を消費しながら条件を満たすPIDの検索をしています.

Builderに注目すると, Builder自身に検索する個体の条件を持たせていることがわかります. これは result() で使用していて, 条件を満たさなければエンカウントデータの代わりに条件を満たす個体が見つからなかったことを表わす None を返しています. また条件が満たされているかの判定には zip, forall を使っています. Builderパターンを採用することで個体の生成, および個体のフィルタリング処理が searchEncounter() からBuilderに切り離されることになります.

このように, Scalaのコレクションライブラリの力を借りることで乱数ツールのコードを綺麗に記述することができます 👍

おわりに

以上が Pokémon RNG Advent Calendar 2017 10日目「Scalaで乱数ツールを書く話」となります. いかがでしたでしょうか. この記事を読んでちょっとしたツールの作成でも綺麗なコードを意識して取り組むきっかけになれればと思います 😃

adventar.org

11日目は oupo さんの担当です!

参考

*1:他にも「型システムが強力だから」, 「関数型言語であるから」などの理由があります.

*2:この後すぐに出てきますが, このようなテクニックは乱数ツールの中でよく使われています.

*3:何の関係もない話ですが最初にこのコードをwandboxで書き上げた時にタブがフリーズし, 1時間の成果が水の泡になる出来事が発生しました

*4:申し訳程度のデザインパターン要素です