はじめに
この記事はPokémon RNG Advent Calendar 2017 10日目の記事です.
乱数調整で楽しむ方々の間では乱数調整を支援するツールのことを乱数ツールと呼んでいます. 僕も乱数ツールを作成する内の1人であり, 時々ツールを作成しますがツールのソースコードはどうしても複雑になりがちです. たかが計算ツールといえども綺麗に書きたいですよね.
この記事ではScalaを使い, 乱数ツールを綺麗に書いてみる話をします.
…あれ?🤔
Adventarのコメント欄にはデザインパターンの話をするって書いてあったはずなのにScalaの話?🤔
デザインパターンは???🤔🤔🤔
…申し訳ありませんが今回はテーマを変えて記事を書いています🙇 本当はデザインパターンの話を書こうと思っていたのですが記事に出来るほど知見が溜まっていなかったのでボツ 🚮 となりました. デザインパターンについてはまたいつか別の機会に話そうと思います 🙏
…さて話を戻します. なぜScalaを使って乱数ツールを書くかというと, Scalaには非常に充実したコレクションライブラリが備わっており, これを用いることで乱数列に対する複雑な操作を簡単に記述できるからです*1. 乱数ツールを記述していく中で, このコレクションライブラリがいかに力を発揮していくかを感じでもらえればと思います.
前提
- 次の条件を満たす読者を対象としています
- http://mizdra.hatenablog.com/entry/2016/12/01/235954 を読んでいること
- Scalaを何となく読める
- コレクションメソッドが多く出てくるのでScalaコレクションメソッドメモ(Hishidama's Scala collection method Memo)などを見ながら読み進めると良いと思います
- 3世代(RS/FRLG/Em) の野生乱数を扱います
- メソッドずれは発生しないものとします
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で乱数ツールを書く話」となります. いかがでしたでしょうか. この記事を読んでちょっとしたツールの作成でも綺麗なコードを意識して取り組むきっかけになれればと思います 😃
11日目は oupo さんの担当です!
参考
- GitHub - OlegIlyenko/scala-icon: Simple scala icon with shadow
- The scala artwork is licensed under a Creative Commons Attribution 4.0 International License.
- http://mizdra.hatenablog.com/entry/2016/12/01/235954
- Scalaコレクションメソッドメモ(Hishidama's Scala collection method Memo)
- Scala Standard Library 2.13.1
- 第3世代/RS/野生乱数 - 乱数調整Wiki（仮） - アットウィキ
