Hatena::ブログ(Diary)

oupoの日記

2017-12-12

DeSmuME用デバッガと霊界の布ときのみスクラッチ

00:00

Pokémon RNG Advent Calendar 2017の12日目の記事です。

DeSmuME用デバッガ

f:id:oupo:20171211224406p:image

DeSmuME用デバッガを作りました。

DeSmuMEはGDB Remote Stub Protocolを実装しています。これを使ってDeSmuMEとやり取りしデバッガの動作を行っています。

ARMとGDB StubであればDeSmuMEに限らずほかのエミュレータでも動くかもしれません。(未チェック)

というわけで、DS用ゲームを解析したい方、どうぞご利用ください。

と、これだけではRNGともPokémonとも関係ない記事になってしまうのでポケモン乱数の話をします。

霊界の布

ダイヤモンドパールで霊界の布をゲットする乱数調整を行いました。

D

きのみスクラッチ

f:id:oupo:20171212004151p:image

プラチナHGSSバトルフロンティアにおけるきのみスクラッチを解析しました。

どういう仕組みできのみが決まっているのか日本語で解説するのは面倒なのでseedを入力したらそのときの結果を出力するプログラムを貼ります。Rubyで書いています。

# Pt, HGSSでのフロンティアのきのみスクラッチ

class LCG
  def initialize(seed)
    @seed = seed
  end

  def clone
    LCG.new(@seed)
  end

  def rand()
    @seed = (@seed * 0x41c64e6d + 0x6073) % 2**32
    @seed >> 16
  end

  def rand_n(n)
    rand() % n
  end
end

ITEM_LIST = [0x00A9, 0x00AA, 0x00AB, 0x00AC, 0x00AD, 0x00AE, 0x00B8, 0x00B9, 0x00BA, 0x00BB, 0x00BC, 0x00BD, 0x00BE, 0x00BF, 0x00C0, 0x00C1, 0x00C2, 0x00C3, 0x00C4, 0x00C5, 0x00C6, 0x00C7, 0x00C8]

ITEM_NAMES = {
  0x005C => "きんのたま",
  0x00A9 => "ザロクのみ",
  0x00AA => "ネコブのみ",
  0x00AB => "タボルのみ",
  0x00AC => "ロメのみ",
  0x00AD => "ウブのみ",
  0x00AE => "マトマのみ",
  0x00B8 => "オッカのみ",
  0x00B9 => "イトケのみ",
  0x00BA => "ソクノのみ",
  0x00BB => "ソンドのみ",
  0x00BC => "ヤチェのみ",
  0x00BD => "ヨブのみ",
  0x00BE => "ビアーのみ",
  0x00BF => "シュカのみ",
  0x00C0 => "バコウのみ",
  0x00C1 => "ウタンのみ",
  0x00C2 => "タンガのみ",
  0x00C3 => "ヨロギのみ",
  0x00C4 => "カシブのみ",
  0x00C5 => "ハバンのみ",
  0x00C6 => "ナモのみ",
  0x00C7 => "リリバのみ",
  0x00C8 => "ホズのみ",
}

def make_scratch(lcg)
  # メタモンの位置決め
  arrange = Array.new(9, nil)
  2.times do |i|
    while true
      i = lcg.rand_n(9)
      if not arrange[i]
        arrange[i] = 4
        break
      end
    end
  end

  #きのみの配置を決定
  item = lcg.rand_n(4)
  count = 0
  9.times do |i|
    x = lcg.rand_n(9)
    if not arrange[x]
      count = 0
      arrange[x] = item
      if i == 2 or i == 4 or i == 6
        item = (item + 1) % 4
      end
    else
      count += 1
      redo if count < 30
      count = 0
      9.times do |j|
        next if arrange[j]
        arrange[j] = item
        if i == 2 or i == 4 or i == 6
          item = (item + 1) % 4
        end
        break
      end
    end
  end

  # アイテムを決定
  items = Array.new(4, nil)
  i0 = lcg.rand_n(4)
  4.times do |i|
    if i == i0
      items[i] = 0x5c
    else
      item = ITEM_LIST[lcg.rand_n(23)]
      redo if items.include?(item)
      items[i] = item
    end
  end
  
  [arrange, items.map{|x| ITEM_NAMES[x] }]
end

def main()
  print "seedを入力> 0x"
  seed = gets.to_i(16)
  print "最大消費数を入力> "
  max_f = gets.to_i
  lcg = LCG.new(seed)
  max_f.times do |f|
    puts "消費#{f}:"
    l = lcg.clone()
    3.times { p make_scratch(l) }
    lcg.rand()
  end
end

main() if $0 == __FILE__

2017-12-11

バトルファクトリー Lv50 1周目〜5周目 乱数調整

00:00

f:id:oupo:20171211001731p:image

Pokémon RNG Advent Calendar 2017の11日目の記事です。

バトルファクトリー 必勝(?)乱数調整 - oupoの日記の続きです。

第4世代のポケモンバトルファクトリーというレンタルポケモンを使って勝ち進める施設で乱数調整を行います。

前回(なんと3年前!)は鉢巻きムクホークと襷道連れムウマージでオープンレベル4周目を必勝するseedを探して乱数調整しました。

今回はLv50 1周目〜5周目で乱数調整します。前回のように必勝までは難しくて実現できていません。

1周目

D

seedは0x532b6a85

勝ち筋:クチートヌケニン

ヌケニン完封できるやつが1匹以上いてそれ以外のポケモンもだいたいクチートに弱い的なseedを探した。

だいたいクチートに弱い、の判定がかなりザル。

2周目に備えて全交換

2周目

D

seedは0xb50a44ff

勝ち筋:オオスバメ

一応必勝判定関数を全試合で使用

オオスバメの根性どくどく玉からげんきの火力は目を見張るものがあるが、守るを覚えておらず1回相手の攻撃を耐える必要があるのが難点。

交換なし

3周目

D

seedは0x004ce889

勝ち筋:キングドラオオスバメ

7戦目にだけ必勝判定関数使用 (そうでないと全然seedが見つからなかった)

キングドラが出ているとき素早さが負けていたら雨を降らせるような戦略をプログラムにしたのだが、実はミスがあってその部分が動いていなかった

7戦目、ヌオーに波乗りを打つミスをした。

交換3回。

4周目

D

seedは0x01686087

勝ち筋: ハピナス

敵トレーナーがランク3の場合必勝判定をさぼる (やはりそうしないとseedが見つからなかった)

肝心のハピナスを活躍させられなかった。ゴウカザルがずっと活躍。

6戦目、カメールが瓦割りを覚えていることを知らなくてハピナスに交換するミスをした。

交換1回。

5周目

D

seedは0x4ab4b12e

勝ち筋: スカーフトリックポリゴンZりゅうのまいギャラドス

AIの技決定がランダムではなくなったので、逆にスカーフトリックなどではめれる。

キノガッサをスカーフトリックでうまくいく相手にしていたのはよくなかった。

所感

  • seedを見つける条件がザルい周多め。運が悪いと負ける可能性あるよなー
  • モンテカルロ法で対戦シミュレーションとかして勝率の高いseedを見つけようとしたものの、敵AIの解析とかもしないといけないのが大変で実現できなかった
  • 5周目の戦略は気に入っている

使ったツールは以下

検索に使ったコードは以下

2017-12-09

乱数調整で遊ぼう 別解

06:05

ろいしんさんの乱数調整で遊ぼうを中身を見ながら解析します。

1. 文字列を調べる

飛ばしてもよいです。バイナリエディタでは2バイトアラインされていないところの2バイト文字が見れなかったりするので念のため。

以下のRubyスクリプト文字列を出力します

fname = ARGV[0]
File.binread(fname).scan(/(?:[\x81-\x9f\xe0-\xfc][\x40-\x7e\x80-\xfc]|[\x20-\x7e]){4,}/n).each do |matched|
  puts matched.encode("utf-8", "cp932", undef: :replace)
end

結果

おいしいみず
サイコソーダ
ミックスオレ
何をしますか?
おかね:%d円
しらべる -> 0
ポケモン -> 1
かいもの -> 2
________
| || ⊂⊃⊂⊃ ||
| || [][][][] ||
| ||
| || [][][][] ||
| || poke
 Θ ||
| || 口口口口 ||
|| ==== ||
    ̄ ̄ ̄ ̄ ̄ ̄
自動販売機が ある!
ほしい 飲み物は....
1. おいしいみず 200円
2. サイコソーダ 350円
3. ミックスオレ 400円
0. やめる
 おかね:%d円
...やっぱり やめた
YOU LOSE...
ペラップを しばいた!
もう一度遊びますか?
はい -> 1
いいえ -> 0
おかねが 足りない....
ガコン!
%sが でてきた!
当たりだ! もう一本
%sが でてきた!
YOU WIN!!
ベトベター
オニドリル
マグマッグ
ベトベトン
がんばりや
さみしがり
ゆうかん 
いじっぱり
やんちゃ 
ずぶとい 
すなお  
のんき  
わんぱく 
のうてんき
おくびょう
せっかち 
まじめ  
ようき  
むじゃき 
ひかえめ 
おっとり 
れいせい 
てれや  
うっかりや
おだやか 
おとなしい
なまいき 
しんちょう
きまぐれ 
するどいくちばし
きんのたま
モンスターボールを 買いました
おかね:%d円
野生の%sを つかまえた!
%s Lv.%d
性格:%s
個体値:%d-%d-%d-%d-%d-%d
なんと!
つかまえた%sが %sをもっていた!
%sを 売って
%d円 手に入れた
おかね:%d円
YOU LOSE...

2. とりあえず普通に遊ぶ

遊びます

3. IDAで逆アセンブルする

IDAで逆アセンブルします。

f:id:oupo:20171209053737p:image

右下に文字列一覧があります。

試しに「当たりだ! もう一本」をクリックしましょう

f:id:oupo:20171209054049p:image

「DATA XREF DATA XREF: sub_4011D0+9F↑o」というのがありますね。

これを使うと、この文字列を参照しているコードに移動できます。大変べんり。

f:id:oupo:20171209054050p:image

無事、乱数を使ってあたりが出るかどうか判定しているところが見れました。

疑似乱数はx_{n+1} = (x_n * 41C64E6Dh + 6073h) % 2^32のようで、seedはdword_404374に格納されているようです。

初期seed決定も調べておきましょう。

dword_404374を選んで「Jump to xref to operand」を押すと、seedを読み書きしている部分が表示されます。

f:id:oupo:20171209054051p:image

見つかりました。

これを見るとtime64()の戻り値 (1970年1月1日 00:00:00からの経過秒数)の下32bitを使っているようです。

ゲームの12/8からのバージョンではペラップが実際に音を鳴らすようになりました。

これを調べてみます。

Beepという文字列があるのでBeep() APIを使って音を鳴らしているのだと推定されます。呼んでいるところを見てみましょう。

f:id:oupo:20171209054054p:image

(((seed >> 16) * 8192) >> 16) * 110 / 8192 + 440

によって周波数を定めているようです。

4. seed書き込みをトレースしながら実行

seed書き込みがあったらそのことを出力しながら実行してみます。

メニュー > Debugger > Breakpoints > Breakpoint listを開きます。

f:id:oupo:20171209120128p:image

このように設定します。

そしてメニュー > Debugger > Start Processを押してみましょう。プログラムが実行されます。

このとき遊んでみると、seedが更新されるたびにTrace Windowにそのことが出力されます。

f:id:oupo:20171209120434p:image

初期seedは0x5a2b5249であることがわかります。Rubyで確認してみると

irb(main):026:0> (Time.utc(1970,1,1) + 0x5a2b5249).getlocal
=> 2017-12-09 12:02:33 +0900

となって確かに起動時刻が使われています。

ペラップを鳴かせると1消費したり野生のポケモンを捕まえるといくつか消費したり、といったこともトレースされます。

長くなってきたのでこの辺りで。

これ以外の情報が気になる方はぜひ自分で解析してみてください。

2017-12-08

ペラップの鳴き声からseedを特定するツールを作った

00:01

Pokémon RNG Advent Calendar 2017の8日目の記事です。

f:id:oupo:20171207173047p:image

作りました。oupoとmizdraさんの二人の共同作です。

DSポケモンにおいてペラップの鳴き声からseedを特定するためのツールです。要マイク。

使い方

1. ペラップの「おしゃべり」機能で880hzのサイン波を録音しておく (youtubeで880hzと検索すれば出ます)

2. このツールを開いた状態で、ペラップの鳴き声を鳴らす。するとツールの入力ボックスに自動的に入力される

3.検索したいモードなどを設定して検索を実行する

4. seed または消費数が見つかる

注意

マイクが遠くてペラップの鳴き声が拾われない、あるいは逆にペラップ以外のBGMの音も拾ってしまうという場合。このときはページ下部のmaxDecibelsを調整してください。-99から-1までの値を設定できます

うっかり鳴き声を取りこぼしてしまった場合は入力に「?」の行を入れておいてください。その行は任意の周波数にマッチするものとして処理されます。

開発

githubリポジトリを置いています。

プルリクエスト、イシュー投稿歓迎です。また、MITライセンスで公開しているのでご自由に。

今後の課題

  • フォームに入力された値を覚えておくようにしたい
  • Reactを全然使っていないのをリファクタリング
  • ペラップの音を拾う部分をもっと精度よく

2017-11-22

DSのROMのオーバーレイたちを展開するスクリプト

18:16

背景

DSはメインメモリが4MBしかなく、ゲームの全てのプログラムをメモリ上に載せることができません。そこで必要なときに必要なモジュールをメモリ上にロードしています(たとえば戦闘に入ったら戦闘用のプログラムモジュールをロードするなど)。

この各モジュールのことをオーバーレイと呼びます。

ROMファイルには各オーバーレイに対する

(ファイルID, 展開先のメモリアドレス)

の情報が入っています。

また、ファイルIDに対応する各ファイルのROM内のオフセットとサイズはROMFAT領域に格納されています。

そこで各オーバーレイをファイルとして取り出し、圧縮を解凍し、逆アセンブルするスクリプトを書きました。

利点

ndsdis2 (http://i486.mods.jp/old/nds/ndshack.html)はメインメモリを全て逆アセンブルする仕組みでした。

これではプログラム以外が格納されているメモリも逆アセンブルするので無駄があります。

またメモリダンプしたそのときに載っているオーバーレイしか逆アセンブルできないという欠点があります。

今回のスクリプトはすべてのプログラムデータを無駄なく逆アセンブルできます。

必要なもの

スクリプト

nitrodis.rb

# NDSファイルの中のoverlayたちを展開して逆アセンブルする

# Usage: ruby nitrodis.rb <filename>.nds


require "fileutils"

OBJDUMP = 'C:/devkitPro/devkitARM/bin/arm-none-eabi-objdump.exe'
SIZEOF_OVR = 32

Fat = Struct.new(:start, :end)
Ovr = Struct.new(:id, :ramaddr, :ramsize, :bsssize, :start, :end, :file_id, :reserved)

def read_u32(f, ofs)
  f.seek ofs
  f.read(4).unpack("V")[0]
end

def read_u32_list(f, ofs, len)
  f.seek ofs
  f.read(4 * len).unpack("V*")
end

def read_cstr(f, ofs, len)
  f.seek ofs
  f.read(len).unpack("Z*")[0]
end

def read(f, ofs, bytes)
  f.seek ofs
  f.read(bytes)
end

def do_file(fname, bin, addr)
  File.binwrite(fname+".orig", bin)
  system "./DSDecmp", "-d", "-f", "lzovl", fname+".orig", fname
  destfname = File.exist?(fname) ? fname : fname + ".orig"
  system OBJDUMP, "-b", "binary", "-m", "arm",
         "-Mforce-thumb", "--adjust-vma=#{addr}",
         "-D", destfname, {1 => destfname + ".dis"}
end

fname = ARGV[0]
open(fname, "rb") do |f|
  romname = read_cstr(f, 0, 12).gsub(" ", "")
  arm9exe_start = read_u32(f, 0x20)
  arm9exe_size = read_u32(f, 0x2c)

  fat_off = read_u32(f, 0x48)
  fat_size = read_u32(f, 0x4c)
  num_files = fat_size / 8
  arm9_overlay_off = read_u32(f, 0x50)
  arm9_overlay_size = read_u32(f, 0x54)
  num_overlay_9 = arm9_overlay_size / SIZEOF_OVR
  fats = []
  ovrs = []
  num_files.times do |i|
    s, e = read_u32_list(f, fat_off + i * 8, 2)
    fats << Fat.new(s, e)
  end
  dirname = "overlay-#{romname}"
  #FileUtils.rm_r dirname
  FileUtils.mkdir_p dirname

  bin = read(f, arm9exe_start, arm9exe_size)
  do_file "#{dirname}/arm9exe", bin, 0x02000000

  num_overlay_9.times do |i|
    ovr = Ovr.new(*read_u32_list(f, arm9_overlay_off + i * SIZEOF_OVR, 8))
    ovrs << ovr
    fat = fats[ovr.file_id]
    #puts "%d %08x %d %d %08x %08x %d %d %08x" % [ovr.file_id, ovr.ramaddr, ovr.ramsize, ovr.bsssize, ovr.start, ovr.end, fat.start, fat.end - fat.start, ovr.reserved]
    #puts "%d %08x %d" % [ovr.file_id, ovr.ramaddr, ovr.ramsize]
    bin = read(f, fat.start, fat.end - fat.start)
    ovrfname = "#{dirname}/#{ovr.file_id}"
    do_file ovrfname, bin, ovr.ramaddr
  end
end