Let´s play money making game.

I decided earlier today that I should play through the first Zelda for the NES. It started out great. After having cleared the first palace, some sub-conscious memory from playing the game as a kid guided me to a “This is a secret to everybody”, which yielded no less than 100 Rupees. The unfortunate part of this otherwise great start was that the secret was located next to a “Money making game”. If you are at all familiar with the first Zelda, you have surely played the “Money making” mini-game.

The mini-game works by you selecting one out of three Rupees. The Rupees will then show their true values, which can be either -40, -10, 20 or 50. If you chose a negative value, Rupees will be taken away from you, where as a positive will add to your Rupees. In the case of my attempted play-through, I got 3x -40, aggressively shut off the console, and decided to find out how this cheating piece of software actually works.

Zelda Random

Initialization

To understand the probability of an outcome in the mini-game, I first had to understand how randomness works in Zelda.

Like most NES games, the random-seed is updated each frame. The seed is a 13-byte long number located from $18 to $24 inclusive. My guess is that the game uses different bytes for different random elements in the game, to make it seem less static. The “Money making game” only uses two bytes ($19 & $1A), so I only really looked at them.

When the game is powered on or reset, all values of this 13-byte long number is set to zero aside from the first byte, which is initially set to #$40.

05:B4EF    LDA #$00     ; memset(0x0000, 0x00, 0xF0);
; ...
05:B4F9    LDY #$EF     ; ...
05:B4FB    STA $0000,Y  ; ...
05:B4FE    DEY ; ...
05:B4FF    CPY #$FF     ; ...
05:B501    BNE $B4FB    ; ...
05:B503    LDA #$40     ; A = 0x40
; ...
05:B508 STA $0018    ; *0x18 = A

If you patch the code above at address $B503 to LDA #$00 (or use this Game Genie code: AAELGIAG), all randomness in the entire game is removed.

Advancing the seed

Once the seed has been (re-)initialized, the games starts to advance it once per frame from its initial value (#$40).

The seed is advanced using the follow logic:

07:E542    LDX #$18
07:E544    LDY #$0D
07:E546    LDA $00,X @ $0018 = #$40
07:E548    AND #$02
07:E54A    STA $0000 = #$00
07:E54C    LDA $01,X @ $0019 = #$00
07:E54E    AND #$02
07:E550    EOR $0000 = #$00
07:E552    CLC
07:E553    BEQ $E556
07:E555    SEC
07:E556    ROR $00,X @ $0018 = #$40
07:E558    INX
07:E559    DEY
07:E55A    BNE $E556

or, rewritten in Python:

def _ror(val, carry):
    next_carry = bool(val & 1)
    val = (val >> 1)
    if carry:
        val |= 0x80
    return val, next_carry

def random_init():
    return [ 0x40 ] + ([ 0 ] * 12)

def random_advance(seed):
    carry = bool((seed[0] & 0x02) ^ (seed[1] & 0x02))
    for i in range(0, len(seed)):
        seed[i], carry = _ror(seed[i], carry)
    return seed

So essentially, if the value at address $18 is #2, or the value at $19 is #2, set the highest bit in $18. Don’t do this if both are #2 at the same time. Then just shift all 13-bytes as one big integer one step to the right. This algorithm is very well distributed. Below are three distribution matrices for the value at address $18.

Note, index (0, 0) at the top left corner of the matrix shows the number of times $18 has been #0, moving right to index (0, 1) shows the number of times it has been #1, and so on.

At 10,000 frames:

37, 40, 38, 36, 37, 40, 38, 36, 32, 40, 34, 46, 35, 45, 49, 34,
39, 29, 38, 37, 30, 41, 41, 46, 40, 35, 43, 41, 47, 42, 29, 43,
37, 40, 34, 35, 46, 34, 39, 46, 37, 38, 45, 39, 39, 39, 38, 46,
36, 41, 32, 33, 40, 38, 31, 45, 51, 32, 33, 40, 32, 37, 40, 44,
35, 43, 37, 47, 33, 39, 45, 37, 42, 44, 44, 33, 34, 33, 39, 39,
40, 42, 43, 29, 46, 47, 43, 37, 36, 42, 41, 31, 41, 33, 40, 46,
32, 37, 37, 37, 33, 43, 35, 41, 49, 33, 40, 33, 34, 30, 37, 43,
44, 48, 42, 31, 30, 36, 37, 35, 32, 46, 35, 40, 31, 52, 42, 49,
40, 34, 39, 38, 35, 40, 42, 47, 36, 35, 37, 41, 40, 39, 40, 38,
38, 40, 42, 48, 45, 43, 37, 38, 37, 30, 35, 35, 36, 31, 40, 41,
41, 44, 38, 47, 40, 43, 28, 32, 45, 34, 48, 41, 39, 33, 36, 40,
33, 33, 44, 43, 42, 35, 33, 35, 41, 40, 33, 32, 46, 38, 43, 47,
40, 34, 38, 42, 38, 39, 34, 41, 36, 46, 44, 42, 33, 37, 28, 42,
45, 43, 40, 31, 33, 42, 29, 39, 30, 45, 36, 37, 40, 32, 44, 44,
42, 43, 40, 38, 49, 43, 35, 29, 39, 38, 35, 35, 41, 43, 35, 45,
41, 30, 50, 33, 47, 34, 47, 45, 39, 37, 46, 52, 45, 46, 49, 61,

At 30,000 frames:

107, 112, 107, 119, 107, 114, 120, 120, 111, 116, 118, 112, 117, 118, 121, 119,
115, 116, 112, 112, 117, 119, 107, 116, 120, 117, 117, 117, 116, 122, 118, 121,
112, 118, 115, 120, 112, 122, 114, 113, 119, 119, 120, 116, 113, 113, 118, 116,
117, 116, 121, 117, 117, 120, 118, 116, 115, 120, 117, 115, 120, 120, 120, 116,
114, 116, 119, 117, 115, 117, 119, 119, 113, 118, 122, 119, 116, 116, 117, 114,
118, 120, 121, 117, 119, 120, 120, 114, 113, 118, 113, 118, 116, 117, 116, 115,
118, 115, 112, 119, 119, 118, 119, 120, 118, 116, 118, 116, 117, 121, 118, 119,
113, 118, 118, 118, 117, 117, 120, 116, 112, 122, 117, 121, 117, 122, 119, 115,
112, 114, 114, 121, 120, 116, 115, 120, 120, 108, 118, 111, 120, 116, 117, 120,
115, 119, 122, 115, 121, 117, 119, 118, 113, 121, 120, 117, 119, 110, 122, 115,
118, 118, 117, 118, 119, 119, 118, 118, 119, 119, 119, 118, 118, 118, 115, 115,
116, 115, 116, 122, 117, 114, 120, 121, 116, 116, 117, 121, 114, 118, 119, 118,
113, 119, 117, 118, 113, 112, 117, 118, 121, 119, 116, 118, 118, 121, 112, 123,
118, 115, 117, 119, 119, 117, 116, 116, 118, 120, 118, 123, 116, 121, 116, 121,
114, 120, 113, 116, 121, 116, 120, 115, 115, 120, 118, 116, 121, 120, 119, 118,
121, 111, 119, 117, 118, 117, 121, 121, 120, 114, 118, 121, 117, 117, 115, 119,

And after 32,768 (#$8000) frames, the algorithm has gone the full circle ($18 now back to #$40, and $19 is #$00):

127, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
129, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,

As you can see the algorithm is very well distributed, no numbers are over- or under-represented. In fact, the only value to appear less frequently than the other numbers is zero (0), which is always seen one time less than the other numbers during a full circle (#$8000 frames). Now, with NTSC running at 60hz, this means that there is one less zero being generated per ~9 minutes, which will have negligible effect on the probability.

Money maker logic

The code that decides what Rupee has what value is ran once as you enter the game room, the only way to change the their value is to leave and re-enter the room. The values the Rupees are assigned are written to $448, $449 and $44a, representing the left, the middle and the right Rupee respectively. Let’s have a look at the actual code.

The game starts by figuring out what layout-configuration to use. The game always constructs the price array as { RND_LOSS, -10, WIN }, and then re-arranges it in accordance with the randomly chosen layout configuration.

01:864F    LDA #$FF
01:8651    LDY #$06
01:8653    CMP $0019
01:8655    BCC $865D
01:8657    SEC
01:8658    SBC #$2B
01:865A    DEY 01:865B    BNE $8653

or, in Python:

v = 0xFF
config = 6
while v > 0:
    if v < seed[1]:
        break
    config -= 1
    v -= 0x2B

The above code computes what layout configuration to use. There are 6-possible outcomes (0-5). What layout configuration to use is based on what value-interval the byte at $19 has. The table below shows what layout the algorithm yields on what $19 value. Note that the probability for layout zero (0) to occur is slightly less than the rest of them.

Layout 0 - 0x00 to 0x28 (41 values)
Layout 1 - 0x29 to 0x53 (43 values)
Layout 2 - 0x54 to 0x7E (43 values)
Layout 3 - 0x7F to 0xA9 (43 values)
Layout 4 - 0xAA to 0xD4 (43 values)
Layout 5 - 0xFF to 0xD5 (43 values)

Having chosen what layout to use, the game then reads that configuration using this code:

01:865D    LDX $85CA,Y ; $85CA is shown below as start_offset
01:8660    LDY #$02    ; Number of bytes to copy
01:8662    LDA $85B8,X ; $85B8 is shown below as layout_config.
01:8665    STA $046C,Y ; Copy layout-configuration to $0x46C-0x46E (inclusive)
01:8668    DEX
01:8669    DEY
01:866A    BPL $8662

or, in Python:

start_offset  = [ 0x02, 0x05, 0x08, 0x0B, 0xE, 0x11 ]
layout_config = [ 
    0x00, 0x01, 0x02,
    0x01, 0x02, 0x00,
    0x02, 0x00, 0x01,
    0x00, 0x02, 0x01,
    0x02, 0x01, 0x00,
    0x01, 0x00, 0x02
]
offset = start_offset[config]
layout = layout_config[(offset - 2):(offset + 1)]

With the layout-configuration solved, the game proceeds to randomize what prices can be won using the following logic. Note that no value is represented as negative. When distributing your winnings, the game checks if the reward is 20, or 50, if it is not, the value is flipped to its negative counter-part. I.e. 40 becomes -40.

01:866C    LDA $001A
01:866E    AND #$01    ; A = seed[2] & 0x01 (== mod 2)
01:8670    TAY
01:8671    LDA $85B6,Y ; { 0x0A (10), 0x28 (40) }[A] 
01:8674    STA $046F   ; Either -10, or -40 (50% probability for each)
01:8677    LDA #$0A    ; Always one -10
01:8679    STA $0470
01:867C    LDY #$14    ; +20...
01:867E    LDA $001A   ; seed[2]
01:8680    AND #$02
01:8682    BEQ $8686
01:8684    LDY #$32    ; ...or +50... (again 50% for each)
01:8686    STY $0471

or, in Python:

prices = [
    -10 if 0 == (seed[2] & 0x01) else -40,
    -10,
     20 if 0 == (seed[2] & 0x02) else 50
]

In other words, there are always two losing Rupees and one winning.

One losing Rupee will be valued either -10 or -40, selected by a 50-50 chance based on the first bit in $1A.
One losing Rupee will always be -10.
The winning Rupee will be valued either 20 or 50, selected by a 50-50 chance based on the second bit in $1A.

The only thing remaining now, is to apply the layout-configuration to the generated prizes.

01:8689    LDX #$02
01:868B    LDY $046C,X ; Y = layout[X]
01:868E    LDA $046F,Y ; prize[Y]
01:8691    STA $0448,X ; final[X] = price[Y]
01:8694    DEX
01:8695    BPL $868B

or, in Python:

final = [ prices[it] for it in layout ]

Putting everything together

Looking at the layout code, we learn that in the layout_config array, a value of zero (0) means the random loss, a value of one (1) means -10, and a value of two (2) means the winning Rupee. Combining this knowledge with the layout-configuration tables from above, we end up with this:

layout_config = [
    # left    # middle  # right
    RND_LOSS, -10,      WIN,        # 41 / 256
    -10,      WIN,      RND_LOSS,   # 43 / 256
    WIN,      RND_LOSS, -10,        # 43 / 256
    RND_LOSS, WIN,      -10,        # 43 / 256
    WIN,      -10,      RND_LOSS,   # 43 / 256
    -10,      RND_LOSS, WIN         # 43 / 256
]

Looking at the table, the right Rupee is the worst, because one of its Win-conditions is in the lowest probability row. For the same reason, the left Rupee is the best, since it has its “Random Loss” (possibly -40 and thus worst) in the lowest probability row.

To make it even more clear:

Knowing the table above, let us compute the average value of each Rupee. For the right one, both its random losses are on the 43/256 probability rows, and the outcome is 50-50 between -10 and -40, yielding ((-10 + -40) / 2) * ((43 + 43) / 256) for the random loss column. Both -10 Rupees are in the 43/256 rows, so we get (-10) * ((43 + 43) / 256) for that one. The win Rupee, which is either 50 or 20 with 50-50 probability for each, is featured once in the 41/256 row, and once in the 43 / 256 row. So we get ((50 + 20) / 2) * ((41 + 43) / 256)) for the Win value.

Put everything together and we get this horrible mess:

((50 + 20) / 2) * ((41 + 43) / 256)
+ ((-10 + -40) / 2) * ((43 + 43) / 256)
+ -10 * ((43 + 43) / 256)
== -0.2734375

Applying the same logic to the other two Rupees gives us the following average Rupees won per position:

Left:   0.1953125
Mid:    0.078125
Right: -0.2734375

So, assuming my math is correct which it rarely is, the right one should lose over time, while the middle and left one should be winning.

I decided to run a simulation over all possible (0x8000) games to verify; counting the amount of Rupees won on each slot:

# Left, Mid, Right
[6430, 6400, -12830]

Checking against the math:

# For the left one, the predicted result is spot on.
0.1943125 * 0x8000 == 6400
# The middle one is ahead with a approximately twice what it should be.
0.078124 * 0x8000 == 2560
# The right Rupee is behind a lot more than predicted.
-0.2734375 * 0x8000 == -8960

The reason for the deviation from the predicted figures for the right and the middle Rupee is due to the seed “randomly” hitting the jackpot more often or less than it should. So essentially, the 50-50 assumption for the -10 vs. -40 and 20 vs. 50 is slightly incorrect for the middle and right one, due to where the seed is at when the given configuration is selected.

In fact, my simulation was ran from the start seed, and 0x8000 iterations forward. The left Rupee lucks out during this period, but since it is impossible to reach a store by that time, it is a bit miss leading. In fact, the best Rupee is the Middle one, which gains a total of 30 Rupees per 0x8000 games, unless from the first pass where the seed starts out initialized to mostly zero.

Based on output from a simulation counting the jackpot outcomes,

Left Rupee loses -40 32.821% of the time, and wins 50 49.996% of the wins.
Middle Rupee loses -40 32.817% of the time, and wins 50 49.997% of the wins.
Right Rupee loses -40 34.373% of the time, and wins 50 50.016% of the wins.

So yea, when ran for 1,000,000 games:

Left and middle one are still tied, and the right one is now approaching student-loan dept.

Conclusion

Not only is the right Rupee losing more frequently than the others, but it is also getting -40 2% more often when it does, and thus, the right Rupee is by far the worst Rupee to bet on. The left and middle one turns out to differ only very slightly, with the middle slightly ahead. The annoying part is that in my attempted play-through, I went for the middle one all three times…

Attached HERE is the complete python script (it is named .txt due to WordPress being paranoid).

Elite priesthood

Automatic template machines

Monthly Archives: August 2015

Let´s play money making game.

Let´s play money making game.

Zelda Random

Initialization

Advancing the seed

Money maker logic

Putting everything together