1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/org/tas-submission.txt	Thu Nov 22 13:12:21 2012 -0600
     1.3 @@ -0,0 +1,287 @@
     1.4 +Pokemon Yellow Total Control Hack. Reprogramming the game from the inside!
     1.5 + 
     1.6 +!! Game objectives
     1.7 +
     1.8 +* Emulator used: vba-rerecording 23.5
     1.9 +* Reprogram the Game from the inside
    1.10 +
    1.11 +!! Comments
    1.12 +
    1.13 +I've included a detailed writeup here:
    1.14 +http://aurellem.org/vba-clojure/html/total-control.html
    1.15 +
    1.16 +There is a video at:
    1.17 +http://www.youtube.com/watch?v=p5T81yHkHtI with keypress visualizations
    1.18 +
    1.19 +The following are the highlights:
    1.20 +
    1.21 +! Introduction
    1.22 +
    1.23 +Think of pokemon yellow as creating a little universe with certain
    1.24 +rules. Inside that universe, you can buy items, defeat rival trainers,
    1.25 +and raise your pokemon. But within that universe, you are bound by the
    1.26 +rules of pokemon. You can't build new buildings, or change the music,
    1.27 +or change your clothes.. There are some games (like chess), where it
    1.28 +is not possible to alter the rules of the game from within the
    1.29 +game. No matter what moves you make in chess, you can never change the
    1.30 +rules of the game so that it becomes checkers or basketball. The point
    1.31 +of this run is to show that you CAN change the rules in pokemon
    1.32 +yellow. There is a certain sequence of valid actions (like walking
    1.33 +from one place to another or buying items) that will allow you to
    1.34 +transform pokemon yellow into Pacman, or Tetris, or Pong, or a MIDI
    1.35 +player, or anything else you can imagine.
    1.36 +
    1.37 +
    1.38 +! Background
    1.39 +
    1.40 +The speedrun (http://tasvideos.org/2913S.html) by Felipe Lopes de
    1.41 +Freitas (p4wn3r), beats pokemon yellow in only 1 minute and 36
    1.42 +seconds. It does it by corrupting the in-game item list so that he can
    1.43 +advance the list past its normal limit of 20 items. The memory
    1.44 +immediately after the item list includes the warp points for the
    1.45 +current map, and by treating that data as items and switching and
    1.46 +dropping them, he can make the door from his house take him directly
    1.47 +to the end of the game.
    1.48 +
    1.49 +When I first saw that speedrun, I was amazed at how fast pokemon
    1.50 +yellow could be beaten, and that it was possible to manipulate the
    1.51 +game from the inside, using only the item list. I wondered how far I
    1.52 +could extend the techniques found in p4wn3r's run.
    1.53 +
    1.54 +The gameboy is an 8 bit computer. That means that ultimately, anything
    1.55 +that happens in pokemon is a result of the gameboy's CPU reading a
    1.56 +stream of 8 bit numbers and doing whatever those numbers mean. For
    1.57 +example, in the gameboy, the numbers: 
    1.58 +
    1.59 +62 16 37 224 47 240 37 230 15 55
    1.60 +
    1.61 +mean to check which buttons are currently pressed and copy that result
    1.62 +into the "A" register. With enough numbers, you can spell out an
    1.63 +interactive program that reads input from the buttons and allows you
    1.64 +to write any program you want to the gameboy. Once you have assembled
    1.65 +such a program and forced the game to run it, you have won, since you
    1.66 +can use that program to write any other program (like Tetris or
    1.67 +Pacman) over pokemon yellow's code. I call a program that allows you
    1.68 +to write any other program a "bootstrapping program". So, the goal is
    1.69 +to somehow get a bootstrapping program into pokemon yellow and then
    1.70 +force yellow to run that program instead of its own.
    1.71 +
    1.72 +How can we spell out such a program? Everything in the game is
    1.73 +ultimately numbers, including all items, pokemon, levels, etc. In
    1.74 +particular, the item list looks like:
    1.75 +
    1.76 +
    1.77 + item-one-id         (0-255)
    1.78 + item-one-quantity   (0-255)
    1.79 + item-two-id         (0-255)
    1.80 + item-two-quantity   (0-255)
    1.81 + .
    1.82 + .
    1.83 + .
    1.84 + 
    1.85 +
    1.86 +Let's consider the button measuring program  [37 62 16 37 224 37 240
    1.87 +37 230 15 55] from before. Interpreted as items and item quantities, it is 
    1.88 +
    1.89 + lemonade     x16
    1.90 + guard spec.  x224
    1.91 + leaf stone   x240
    1.92 + guard spec.  x230
    1.93 + parlyz heal  x55
    1.94 +
    1.95 +So, if we can get the right items in the right quantities, we can
    1.96 +spell out a bootstrapping program. Likewise, when writing the
    1.97 +bootstrapping program, we must be careful to only use numbers that are
    1.98 +also valid items and quantities. This is hard because there aren't
    1.99 +many different items to work with, and many machine instructions
   1.100 +actually take 2 or even 3 numbers in a row, which severely restricts
   1.101 +the types of items you can use. I ended up needing about 92 numbers to
   1.102 +implement a bootstrap program. Half of those numbers were elaborate
   1.103 +ways of doing nothing and were just there so that the entire program
   1.104 +was also a valid item list.
   1.105 +
   1.106 +The final part of the hack is getting pokemon yellow to execute the
   1.107 +new program after it has been assembled with items. Fortunately,
   1.108 +pokemon keeps a number called a function pointer within easy reach of
   1.109 +the corrupted item list. This function pointer is the starting point
   1.110 +(address) of a program which the game runs every so often to check for
   1.111 +poison and do general maintenance. By shifting an item over this
   1.112 +function pointer, I can rewrite that address to point to the
   1.113 +bootstrapping program, and make the game execute it. Without this
   1.114 +function pointer, it would not be possible to take over the game.
   1.115 +
   1.116 +!! The Run
   1.117 +
   1.118 +! Pallet
   1.119 +
   1.120 +I start off and name my rival Lp/k. These characters will eventually be
   1.121 +treated as items and shifted over the function pointer, causing it to
   1.122 +execute the bootstrapping program that will soon be constructed. I
   1.123 +start the run the same as p4wn3r's and restart the game while saving,
   1.124 +so that the pokemon list is corrupted. By switching the 8th and 10th
   1.125 +pokemon, I corrupt the item list and can now scroll down past the 20th
   1.126 +item. I shift items around to increase the text speed to maximum and
   1.127 +rewrite the warp point of my house to Celadon Dept. Store. (p4wn3r
   1.128 +used this to go directly to the hall of fame and win the game in his
   1.129 +run.) I deposit many 0x00 glitch items into the PC from my corrupted
   1.130 +inventory for later use. Then, I withdraw the potion from the
   1.131 +PC. This repairs my item list by overflowing the item counter from
   1.132 +0xFF back to 0x00, though the potion is obliterated in the process. I
   1.133 +then take 255 glitch items with ID 0x00 from the computer into my
   1.134 +personal items.
   1.135 +
   1.136 +! Celadon Dept. Store
   1.137 +
   1.138 +Leaving my house takes me directly to Celadon Dept. store, where I
   1.139 +sell two 0x00 items for 414925 each, giving myself essentially max
   1.140 +money. I hit every floor of the department store, gathering the
   1.141 +following items:
   1.142 +
   1.143 + +-------------------+----------+
   1.144 + |##| Item           | Quantity |
   1.145 + +--+----------------+----------+
   1.146 + |1 | TM02           |  98      |
   1.147 + |2 | TM37           |  71      |
   1.148 + |3 | TM05           |   1      |
   1.149 + |4 | TM09           |   1      |
   1.150 + |5 | burn-heal      |  12      |
   1.151 + |6 | ice-heal       |  55      |
   1.152 + |7 | parlyz-heal    |  99      |
   1.153 + |8 | parlyz-heal    |  55      |
   1.154 + |9 | TM18           |   1      |
   1.155 + |10| fire-stone     |  23      |
   1.156 + |11| water-stone    |  29      |
   1.157 + |12| x-accuracy     |  58      |
   1.158 + |13| guard-spec     |  99      |
   1.159 + |14| guard-spec     |  24      |
   1.160 + |15| lemonade       |  16      |
   1.161 + |16| TM13           |   1      |
   1.162 + +--+----------------+----------+
   1.163 + 
   1.164 +
   1.165 +After gathering these items, I deposit them in the appropriate order
   1.166 +into the item PC to spell out my bootstrapping program. Writing a full
   1.167 +bootstrap program in one go using only items turned out to be too
   1.168 +hard, so I split the process up into three parts. The program that I
   1.169 +actually construct using items is very limited. It reads only from the
   1.170 +A, B, start, and select buttons, and writes 4 bits each frame starting
   1.171 +at a fixed point in memory. After it writes 200 or so bytes, it jumps
   1.172 +directly to what it just wrote. In my run, I use this program to write
   1.173 +another bootstrapping program that can write any number of bytes to
   1.174 +any location in memory, and then jump to any location in memory. This
   1.175 +new program also can write 8 bits per frame by using all the
   1.176 +buttons. Using this new bootstrap program, I write a final
   1.177 +bootstrapping program that does everything the previous bootstrapping
   1.178 +program does except it also displays the bytes it is writing to memory
   1.179 +on the screen.
   1.180 +
   1.181 +! Finale
   1.182 +
   1.183 +After completing this bootstrapping program, I go to the Celadon
   1.184 +mansion, because I find the metaness of that building to be
   1.185 +sufficiently high to serve as an exit point for the pokemon
   1.186 +universe. I corrupt my item list again by switching corrupted pokemon,
   1.187 +scroll down to my rival's name and discard until it is equal to the
   1.188 +address of my bootstrapping program, and then swap it with the
   1.189 +function pointer. Once the menu is closed, the bootstrapping program
   1.190 +takes over, and I write the payload....
   1.191 +
   1.192 +!! Other comments
   1.193 +
   1.194 +The entire video was played by the computer using bots. I used
   1.195 +functional programming to write search programs over different
   1.196 +possible game states to find the most efficient way of performing
   1.197 +general actions.  Some interesting things I developed but didn't use
   1.198 +were pretty printing functions to display the game's internal data
   1.199 +structures, and an "improbability drive" that forces improbable events
   1.200 +to happen automatically using search.
   1.201 +
   1.202 +Here are a few example scripts:
   1.203 +
   1.204 +
   1.205 + (defn-memo viridian-store->oaks-lab
   1.206 +   ([] (viridian-store->oaks-lab
   1.207 +        (get-oaks-parcel) ) )
   1.208 +   ([ script \]
   1.209 +      (->> script
   1.210 +           (walk [↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.211 +                  ← ← ← ← ← ← ← ← ← 
   1.212 +                  ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.213 +                  ← ←
   1.214 +                  ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.215 +                  ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.216 +                  → → → → → → → →
   1.217 +                  ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.218 +                  ← ← ← ← ←
   1.219 +                  ↓ ↓ ↓ ↓
   1.220 +                  ])
   1.221 +           (walk-thru-grass
   1.222 +            [↓ ↓ ↓ ↓ ↓ ↓ ↓])
   1.223 +           (walk [↓ ↓ ← ↓ ↓ ↓ ←
   1.224 +                  ↓ ↓ ↓ ↓ ↓ ↓
   1.225 +                  → → → ↑])
   1.226 +                 
   1.227 +           (do-nothing 1) ) ) )
   1.228 +
   1.229 + 
   1.230 +This script walks from the Viridian City pokemon store to Oak's
   1.231 +Lab in the most efficient way possible. The walk-thru-grass function
   1.232 +guarantees that no wild battles will happen by manipulating the game's
   1.233 +random number generator.
   1.234 +
   1.235 +
   1.236 + (defn-memo hacking-10
   1.237 +   ([] (hacking-10 (hacking-9) ) )
   1.238 +   ([ script \]
   1.239 +      (->> script
   1.240 +           begin-deposit
   1.241 +           (deposit-held-item 17 230)
   1.242 +           (deposit-held-item-named :parlyz-heal 55)
   1.243 +           (deposit-held-item 14 178)
   1.244 +           (deposit-held-item-named :water-stone 29)
   1.245 +           (deposit-held-item 14 32)
   1.246 +           (deposit-held-item-named :TM18 1)
   1.247 +           (deposit-held-item 13 1)
   1.248 +           (deposit-held-item 13 191)
   1.249 +           (deposit-held-item-named :TM02 98)
   1.250 +           (deposit-held-item-named :TM09 1)
   1.251 +           close-menu) ) ) 
   1.252 + 
   1.253 +
   1.254 +This script calculates the fastest sequence of key presses to deposit
   1.255 +the requested items into a PC, assuming that the character starts out
   1.256 +in front of a computer.
   1.257 +
   1.258 +!! Other Comments
   1.259 +
   1.260 +The final payload program is multiple programs. I created a reduced
   1.261 +form of MIDI and implemented it in gameboy machine language. Then I
   1.262 +translated a midi file from http://www.everyponysings.com/ into this
   1.263 +reduced MIDI language. The payload program contains both the music
   1.264 +data and the MIDI interpreter to play that data. The picture works in
   1.265 +a similar way. There is code to translate a png file into a form that
   1.266 +can be displayed on a gameboy, and other code to actually display that
   1.267 +image. Both the image and the display code are also written by the
   1.268 +final bootstrapping program.  Even though my final payload is rather
   1.269 +simple, you can write any program at all as the payload. The source
   1.270 +for the sound and image displaying code is at
   1.271 +http://hg.bortreb.com/vba-clojure.
   1.272 +
   1.273 +This entire project is open source and I encourage anyone who wants to
   1.274 +take the code and play around!
   1.275 +
   1.276 +
   1.277 +!! Suggested Screenshots
   1.278 +
   1.279 +* http://aurellem.org/pokemon-hack/code.png
   1.280 +* http://aurellem.org/pokemon-hack/code2.png
   1.281 +* http://aurellem.org/pokemon-hack/matrix.png
   1.282 +* http://aurellem.org/pokemon-hack/matrix2.png
   1.283 +* http://aurellem.org/pokemon-hack/pinkie-pie.png
   1.284 +
   1.285 +Or whatever you all think would be best.
   1.286 +
   1.287 +I encoded the video with/without button visualization here:
   1.288 +
   1.289 +* http://aurellem.org/pokemon-hack/rlm-yellow-hack.avi
   1.290 +* http://aurellem.org/pokemon-hack/rlm-yellow-hack-no-buttons.avi