Ms. Pacman Random Fruit Probabilities Explanation ------------------------------------------------- (c) Mark Spaeth 2002 A hotly contested issue on rgvac. here's an explanation of how the random fruit selection routine works in Ms. Pacman, and the probabilities associated with the routine: 875f 3a134e ld a,(#4e13) ; Load the board # (cherry = 0) 8762 fe07 cp #07 ; Compare it to 7 8764 380a jr c,#8770 ; If less than 7, use board # as fruit 8766 0607 ld b,#07 8768 ed5f ld a,r ; Load the DRAM refresh counter 876a e61f and #1f ; Mask off the bottom 5 bits ;; Compute ((R % 32) % 7) 876c 90 sub b ; Subtract 7 876d 30fd jr nc,#876c ; If >=0 loop 876f 80 add a,b ; Add 7 back 8770 219d87 ld hl,#879d ; Level / fruit data table 8773 47 ld b,a ; 3 * a -> a 8774 87 add a,a 8775 80 add a,b 8776 d7 rst #10 ; hl + a -> hl, (hl) -> a [table look] 8777 320c4c ld (#4c0c),a ; Write 3 fruit data bytes (shape code) 877a 23 inc hl 877b 7e ld a,(hl) 877c 320d4c ld (#4c0d),a ; Color code 877f 23 inc hl 8780 7e ld a,(hl) 8781 32d44d ld (#4dd4),a ; Score table offset . . . 879d 001406 ; Cherry = sprite 0, color 14, score table 06 87a0 010f07 ; Strawberry = sprite 1, color 0f, score table 07 87a3 021508 ; Orange = sprite 2, color 15, score table 08 87a6 030709 ; Pretzel = sprite 3, color 07, score table 09 87a9 04140a ; Apple = sprite 4, color 14, score table 0a 87ac 05150b ; Pear = sprite 5, color 15, score table 0b 87af 06160c ; Banana = sprite 6, color 16, score table 0c 87b2 07000d ; Junior! = sprite 7, color 00, score table 0d For reference, the score table is at 0x2b17 2b17 1000 ; dot = 10 2b19 5000 ; pellet = 50 2b1b 0002 ; ghost 1 = 200 2b1d 0004 ; ghost 2 = 400 2b1f 0008 ; ghost 3 = 800 2b21 0016 ; ghost 4 = 1600 2b23 0001 ; Cherry = 100 2b25 0002 ; Strawberry = 200 2b27 0005 ; Orange = 500 2b29 0007 ; Pretzel = 700 2b2b 0010 ; Apple = 1000 2b2d 0020 ; Pear = 2000 2b2f 0050 ; Banana = 5000 2b31 0050 ; Junior! = 5000 [The 8th fruit is a legacy thing from pacman, which used 8 bonus items. it is not used in mspac] ------------------------ So, a little more background... The 'R' register is the dram refresh address register that is not initalized on startup, so it has garbage in it. During every instruction fetch, the counter is incremented. Assume on average 4 clock cycles per instruction, with the clock running at 3.072 Mhz, this counter is incremented every 1.3us, so if you read it at any time, it's gonna be pretty damn random. Of course, it doesn't just get read at any time, since the fruit select routine is called during the vertical blank every 1/60sec, but since the the instruction counts between reads are not all the say, it's still random to better than 1/60 sec, which is still too fast for any player to count off. So, now, assuming that the counter is random, the bottom 5 bits are hacked off giving a number 0-31 (each with probability 1/32), and this number modulo 7 is used to determine which fruit appears... So... 0, 7,14,21,28 -> Cherry 100 pts @ 5/32 = 15.625 % 1, 8,15,22,29 -> Strawberry 200 pts @ 5/32 = 15.625 % 2, 9,16,23,30 -> Orange 500 pts @ 5/32 = 15.625 % 3,10,17,24,31 -> Pretzel 700 pts @ 5/32 = 15.625 % 4,11,18,25 -> Apple 1000 pts @ 4/32 = 12.5 % 5,12,19,26 -> Pear 2000 pts @ 4/32 = 12.5 % 6,13,20,27 -> Banana 5000 pts @ 4/32 = 12.5 % Also interesting to note is that the expected value of the random fruit is 1234.375 points, which is useful in determining a good estimate of what the killscreen score should be. The standard deviation of this distribution is 1532.891 / sqrt(n), where n is the number of random fruits eaten, so at the level 243 (?) killscreen, (243-7)*2 = 472 fruits have been eaten, and the SD falls to 21.726, so it should be pretty easy to tell if the fruit distribution has been tampered with. This SD across 472 fruits is +/- 10k from the mean, is approximaely the difference between the top 3 players in twin galaxies, but given the game crash issue, the number of levels the game lets you play is probably a more poingant indicator than the fruits given. How to cheat: ------------- Of course, if you want to be cutesy you can play with the distribution, by say changing 876b to 0x3f, thus doing 0-63 mod 7 to choose the fruit, bumping the average up to 1337.5, but at an extra 100 points a fruit, thats 47,200 points on average, and without a close statistical analysis like the one I've provided (which shows that this is almost 5 standard deviations above the mean), you could probably get away with it in competition. If you really wanted to be cheezy, you could change 0x876b to 0x06, so that only cherry, orange, apple, and banana come up, and all have equal probability. That would bump your fruit average up to 1650, but the absence of strawberries, pretzels, and pears would be pretty obvious. These changes would't require any other changes in the code, but it's also possible to completely rewrite the routine, in a different part of the code space to do something different, but that's an exercise left to the reader. (Perhaps the simplest would be to add 3 after the mod 32 operation, so that Pretzel-Banana are slightly more likely than Cherry-Orange). If you really want to be lame, you can edit the scoring table at 0x2b17 (many pacman bootlegs did this). Seriously, you could probably add 10 points to each value, and the 'judges' couldn't tell whether or not you were eating a dot while eating the fruit in many situations, and you could get almost 5000 extra points over the entire game ;) One other 'cool' thing to do would be to chage 0x8763 to 0x08, which would utilize the 8th fruit on the 8th board, and subsequently would give you even odds on all of the fruit, but since the junior icon and the banana are both 5000, the average skews WAY up to 1812.5 points. [To keep things fair, though, note that the junior fruit uses color code 0x00, which is to say, all black, so you'd have to find the invisible fruit. Since the fruit patterns are pretty well known, that's probably not that big of a deal for top players.] References: My own rom disassemblies: http://rgvac.978.org/asm Ms. Pacman disassembly: http://www.cis.rit.edu/~jerry/Software/pengo/mspac/mspac.asm