あぁ、スペースインベーダー

僕がコンピュータ、なるものに興味を持ったきっかけは、スペースインベーダーです。「コンピュータ」で動いている、と教えてもらい驚愕しました。それまで、ブラウン管は放送を受信するものだったのでした。そこで、まったく違うことが展開されるのです。

地球を宇宙からの侵略から守ろうと必死に戦ったことを思い出します。

スペースインベーダーにはイロモノとしてUFOが出てきて、撃ち落とすとランダムに50点、100点、150点、300点と点数がもらえます。

ランダム、あるいは「乱数」というのを僕が知ったのはこの時が最初でした。

8-bit整数での擬似乱数生成

当時のマイコンは8-bitですが、内部状態を8-bitの1バイトで出力も8-bitの1バイトの擬似乱数生成ルーチンを覚えています。すなわち、「13掛けて5を足す。」

記憶だけ残っているのですが、どこで教えてもらったか分かりません。

確かに、これは 256 の状態を回ります。

内部状態を0として初期化すると、5, 70, 147, 124, 81 とランダムっぽい数列となります。 えー、今、Emacs で出力してみました:

00 05 46 93 7c 51 22 bf b8 5d be ab b4 29 1a 57
70 b5 36 c3 ec 01 12 ef 28 0d ae db 24 d9 0a 87
e0 65 26 f3 5c b1 02 1f 98 bd 9e 0b 94 89 fa b7
50 15 16 23 cc 61 f2 4f 08 6d 8e 3b 04 39 ea e7
c0 c5 06 53 3c 11 e2 7f 78 1d 7e 6b 74 e9 da 17
30 75 f6 83 ac c1 d2 af e8 cd 6e 9b e4 99 ca 47
a0 25 e6 b3 1c 71 c2 df 58 7d 5e cb 54 49 ba 77
10 d5 d6 e3 8c 21 b2 0f c8 2d 4e fb c4 f9 aa a7
80 85 c6 13 fc d1 a2 3f 38 dd 3e 2b 34 a9 9a d7
f0 35 b6 43 6c 81 92 6f a8 8d 2e 5b a4 59 8a 07
60 e5 a6 73 dc 31 82 9f 18 3d 1e 8b 14 09 7a 37
d0 95 96 a3 4c e1 72 cf 88 ed 0e bb 84 b9 6a 67
40 45 86 d3 bc 91 62 ff f8 9d fe eb f4 69 5a 97
b0 f5 76 03 2c 41 52 2f 68 4d ee 1b 64 19 4a c7
20 a5 66 33 9c f1 42 5f d8 fd de 4b d4 c9 3a f7
90 55 56 63 0c a1 32 8f 48 ad ce 7b 44 79 2a 27

観察すると、あんまりランダムじゃないことも分かります。 16の周期で下位4-bitが同じになっていて、各列の下一桁が一緒でしょ?

UFOの得点はビームの数に関係していた

スペースインベーダーの話に戻りますが、UFOの得点は実はランダムではなくて、ビーム砲から発射されるビームの数で決まる、という関係がありました。

300点出たら、その後は15発ごとに300点が取れるというのを当時、皆が知っていて、「1, 2, 3... 15」と、ビームの数を数えながらインベーダを倒したのです。

もしかしたらスペースインベーダの擬似乱数の実装も...

もしかしたらスペースインベーダの擬似乱数の実装も、当時の秘伝?の「13掛けて5を足す。」だったかもしれません。15発ごとというのが、それっぽいかな。

UPDATE: いや、違うでしょ、それ。

インベーダの話の周期は15で、「13掛けて5を足す。」の周期は16ですから、「13掛けて5を足す。」は違うでしょう。

「13掛けて...」というのは機械語の8080/Z80では、やらないでしょう。掛け算が高価ですから。これは、おそらく当時のBASICのテクニックじゃないでしょうか。

先日、乱数に関連して18年前の PIC16F84 の話を思い出しました。周期15ということでは、むしろ、そこで触れたM系列のほうが蓋然性があります。

30年ぶりくらいに8080で書いてみました:

          RND: EQU 1000
3A 00 10       LDA RND
E6 09          ANI 9
C6 07          ADI 7
E6 08          ANI 8
C6 F8          ADI F8
3A 00 10       LDA RND
17             RAL
E6 0F          ANI 0F
32 00 10       STA RND
C9             RET

当時考えたのは、おそらく「できるだけテンポラリのレジスタを使わない」ということだったかと記憶しているので、そういうようにしてみました。また、当時は、そういうことは考えなかったと思いますが、計算の実行時間がコンスタントになるように分岐命令は使わないようにしました。

初期値を 1 とすると、これで得られる列は、

3, 7, 16, 14, 13, 10, 5, 11, 6, 12, 9, 2, 4, 8, 1, ...

となります。

ひとつテンポラリにBレジスタを使うとすると、プログラムは短くできて、下記のようでしょうか。

          RND: EQU 1000
3A 00 10       LDA RND
47             MOV B,A
E6 09          ANI 9
C6 07          ADI 7
E6 08          ANI 8
87             ADD A
B0             ORA B
1F             RAR
32 00 10       STA RND
C9             RET

初期値を 1 とすると、これで得られる列は、

8, 12, 14, 15, 7, 11, 5, 10, 13, 6, 3, 9, 4, 2, 1, ...

となります。

上記のプログラムは4-bitでした、すみません

「8-bit整数での擬似乱数生成」と話をしておきながら、4-bitの話になってました。

8-bitの擬似乱数生成を8080で書くと(えー、左にシフトする場合、たとえば8Eもしくは95をタップすればM系列となって)、8Eとすれば下記のようでしょうか。

RND: EQU 1000
RANDOM:
3A 00 10       LDA RND
47             MOV B,A
E6 8E          ANI 8E
C6 78          ADI 78
E6 86          ANI 86
C6 7C          ADI 7C
E6 82          ANI 82
C6 7E          ADI 7E
C6 80          ADI 80
78             MOV A,B
17             RAL
32 00 10       STA RND
C9             RET

ついでにこちらの 8080/Z80エミュレータ を対象に、HEX_PRINTも作りました。

HEX_PRINT:
47             MOV B,A
0F             RRC
0F             RRC
0F             RRC
0F             RRC
E6 0F          ANI F
FE 0A          CPI A
DA 26 00       JC  L0
C6 07          ADI 7
C6 30     L0:  ADI 30
D3 01          OUT 1
78             MOV A,B
E6 0F          ANI F
FE 0A          CPI A
DA 34 00       JC  L1
C6 07          ADI 7
C6 30     L1:  ADI 30
D3 01          OUT 1
3E 0D          MVI 0D
D3 01          OUT 1
3E 0A          MVI 0A
D3 01          OUT 1
C9             RET

CD 00 00       CALL RANDOM
CD 18 00       CALL HEX_PRINT
76             HALT

初期値を1 として実行すると出力の列は、

02 05 0B 16 2C 58 B1 63 C7 8F 1E 3D 7A F4 E8 D0
A1 43 87 0F 1F 3F 7F FF FE FC F9 F2 E4 C8 90 21
42 85 0A 14 29 53 A7 4F 9F 3E 7D FA F5 EA D5 AA
55 AB 57 AE 5C B8 70 E0 C1 83 06 0C 18 31 62 C5
8A 15 2B 56 AC 59 B3 66 CC 99 32 65 CB 97 2F 5F
BF 7E FD FB F7 EF DE BC 79 F3 E6 CD 9B 37 6E DD
BB 77 EE DC B9 72 E5 CA 95 2A 54 A9 52 A5 4A 94
28 51 A2 44 89 12 25 4B 96 2D 5A B4 68 D1 A3 46
8C 19 33 67 CE 9C 39 73 E7 CF 9E 3C 78 F1 E3 C6
8D 1B 36 6C D8 B0 61 C2 84 08 11 22 45 8B 17 2E
5D BA 75 EB D7 AF 5E BD 7B F6 ED DB B7 6F DF BE
7C F8 F0 E1 C3 86 0D 1A 34 69 D3 A6 4D 9A 35 6B
D6 AD 5B B6 6D DA B5 6A D4 A8 50 A0 41 82 04 09
13 27 4E 9D 3B 76 EC D9 B2 64 C9 92 24 49 93 26
4C 98 30 60 C0 81 03 07 0E 1D 3A 74 E9 D2 A4 48
91 23 47 8E 1C 38 71 E2 C4 88 10 20 40 80 01

と、255の周期となります。

もう少し改良

8Eではなく95をタップするとすれば、一つの加算命令による二つのビットのXORの計算が重ならないように一度で実行できるので、もうちょっと短くできます。

RND: EQU 1000
RANDOM:
3A 00 10       LDA RND
47             MOV B,A
E6 95          ANI 95
C6 73          ADI 73
F6 78          ORI 78
C6 04          ADI 04
17             RAL
78             MOV A,B
17             RAL
32 00 10       STA RND
C9             RET

初期値を1 として実行すると出力の列は、

03 07 0E 1D 3B 76 EC D8 B0 60 C0 81 02 04 09 13
26 4D 9A 34 68 D0 A0 41 83 06 0D 1A 35 6B D7 AE
5C B8 70 E1 C2 85 0B 17 2F 5E BC 79 F2 E4 C8 91
23 47 8E 1C 38 71 E2 C5 8B 16 2C 59 B2 64 C9 92
24 49 93 27 4E 9D 3A 75 EB D6 AD 5B B6 6D DA B4
69 D3 A7 4F 9E 3D 7B F6 ED DB B7 6E DD BA 74 E8
D1 A3 46 8D 1B 36 6C D9 B3 67 CE 9C 39 72 E5 CB
96 2D 5A B5 6A D4 A9 52 A5 4B 97 2E 5D BB 77 EF
DF BE 7D FB F7 EE DC B9 73 E6 CC 98 30 61 C3 86
0C 19 32 65 CA 95 2A 54 A8 51 A2 45 8A 15 2B 57
AF 5F BF 7E FC F9 F3 E7 CF 9F 3E 7C F8 F0 E0 C1
82 05 0A 14 28 50 A1 42 84 08 10 21 43 87 0F 1E
3C 78 F1 E3 C6 8C 18 31 62 C4 88 11 22 44 89 12
25 4A 94 29 53 A6 4C 99 33 66 CD 9B 37 6F DE BD
7A F5 EA D5 AA 55 AB 56 AC 58 B1 63 C7 8F 1F 3F
7F FF FE FD FA F4 E9 D2 A4 48 90 20 40 80 01

と、255の周期となります。

NeuGは擬似乱数ではありません

ところで、NeuGの乱数は、上述のような(内部状態から計算で求める)擬似乱数ではありません。

エントロピー源(ノイズ源)からの信号を元にしています。得られるエントロピー量を推定して、それより少ない量だけ、いわば「厳選して」、出力します。

NeuG 1.0 の場合、約70 [Kiバイト/秒] で出力できます。

一秒間に70Kiバイトの乱数というと一秒間にだいたい57万回コインを投げる、22万回サイコロを振るという感じでしょうか。

こう書くと、とても速い感じがしますが、物理乱数生成器で70 [Kiバイト/秒] というのは、そんなに高速というわけではありません。

よろしかったら、 NeuGの入ったFST-01を購入 して、遊んでみてください。