犬2匹+ラティのとき初期seed上2桁が一つずれてもラティの位置が変わらないことがよくあるのはなぜかという問題
2010-01-01 - だだぢぢのポケモン日記のコメント欄を読んで調べてみた。
0x00123456: 35,44,15 0x01123456: 35,44,15 0x02123456: 35,44,1 0x03123456: 35,44,1 0x04123456: 35,44,1 0x05123456: 35,44,12 0x06123456: 35,44,12 0x07123456: 35,44,12 0x08123456: 35,44,24 0x09123456: 35,44,24 0x0a123456: 35,44,24 0x0b123456: 35,44,24 0x0c123456: 35,44,9 0x0d123456: 35,44,9 0x0e123456: 35,44,9 0x0f123456: 35,44,20 0x10123456: 35,44,20 0x11123456: 35,44,20 0x12123456: 35,44,20 0x13123456: 35,44,6 0x14123456: 35,44,6 0x15123456: 35,44,6 0x16123456: 35,44,17 0x17123456: 35,44,17 0x18123456: 35,44,17 0x19123456: 35,44,3 0x1a123456: 35,44,3 0x1b123456: 35,44,3 0x1c123456: 35,44,3 0x1d123456: 35,44,14 0x1e123456: 35,44,14 0x1f123456: 35,44,14
こんな感じで上2桁がずれてもラティの位置が変わらないことがよくある。なぜだろうか。
カントーの道路の数は25個。
ラティの位置の計算に使われるのはseed[3]の値。その値を見てみる。
0x00123456: 35,44,15 (19389 % 25 = 14) 0x01123456: 35,44,15 ( 189 % 25 = 14) 0x02123456: 35,44, 1 (46525 % 25 = 0) 0x03123456: 35,44, 1 (27325 % 25 = 0) 0x04123456: 35,44, 1 ( 8125 % 25 = 0) 0x05123456: 35,44,12 (54461 % 25 = 11) 0x06123456: 35,44,12 (35261 % 25 = 11) 0x07123456: 35,44,12 (16061 % 25 = 11) 0x08123456: 35,44,24 (62397 % 25 = 22) 0x09123456: 35,44,24 (43197 % 25 = 22) 0x0a123456: 35,44,24 (23997 % 25 = 22) 0x0b123456: 35,44,24 ( 4797 % 25 = 22) 0x0c123456: 35,44, 9 (51133 % 25 = 8) 0x0d123456: 35,44, 9 (31933 % 25 = 8) 0x0e123456: 35,44, 9 (12733 % 25 = 8) 0x0f123456: 35,44,20 (59069 % 25 = 19) 0x10123456: 35,44,20 (39869 % 25 = 19) 0x11123456: 35,44,20 (20669 % 25 = 19) 0x12123456: 35,44,20 ( 1469 % 25 = 19) 0x13123456: 35,44, 6 (47805 % 25 = 5) 0x14123456: 35,44, 6 (28605 % 25 = 5) 0x15123456: 35,44, 6 ( 9405 % 25 = 5) 0x16123456: 35,44,17 (55741 % 25 = 16) 0x17123456: 35,44,17 (36541 % 25 = 16) 0x18123456: 35,44,17 (17341 % 25 = 16) 0x19123456: 35,44, 3 (63677 % 25 = 2) 0x1a123456: 35,44, 3 (44477 % 25 = 2) 0x1b123456: 35,44, 3 (25277 % 25 = 2) 0x1c123456: 35,44, 3 ( 6077 % 25 = 2) 0x1d123456: 35,44,14 (52413 % 25 = 13) 0x1e123456: 35,44,14 (33213 % 25 = 13) 0x1f123456: 35,44,14 (14013 % 25 = 13)
上位2桁の値が1つ増えるごとに乱数の値が19200ずつ減っている。なるほど、19200ずつ減っているから変わらないのかー。で、なんで19200ずつ減っているの？
次のseedを求める式
seed[n+1] = (seed[n] * 0x41C64E6D + 0x6073)
seed[n+1] = seed[n] * A + B とすると、seed[n+2] = (seed[n] * A + B) * A + Bとなる。同様に seed[n+3] = ((seed[n] * A + B) * A + B) * A + B となるので...
seed[n+3] = seed[n] * A**3 + B * A**2 + B * A**1 + B * A**0
となる。
AとBに値を入れると、seed[n+3] = seed[n] * 0x807dbcb5 + 0x52713895となる。
初期seed上位2桁が1増えると、seed[3]は0x01000000 * 0x807dbcb5増える。
((0x01000000 * 0x807dbcb5) >> 16) & 0xffff = 46336 で、seed[3] >> 16は 46336ずつ増える。46336ずつ増えるというのは、65536 - 46336 = 19200で19200ずつ減るということだ。
