Submission #3767: bortreb's GBC Pokémon Yellow "Executes Arbitrary Code" in 12:51.87

Console Game Boy Color Emulator vba-rerecording 23.5
Game Version USA Frame Count 46312
ROM Filename Pokemon Yellow (U)[C][!].gbc Frame Rate 60
Branch Executes Arbitrary Code Rerecord Count 0
Unknown Authors bortreb
Game Pokémon: Yellow Version
Submitted by bortreb on 11/22/2012 5:13:13 AM

Submission Comments

Syntax Error

Syntax Error on line 85
  1. Pokemon Yellow Total Control Hack. Reprogramming the game from the inside!
  2.  
  3. !! Game objectives
  4. 
  5. * Emulator used: vba-rerecording 23.5
  6. * Reprogram the Game from the inside
  7. 
  8. !! Comments
  9. 
 10. [module:youtube|v=p5T81yHkHtI]
 11. 
 12. I've included a detailed writeup here:
 13. http://aurellem.org/vba-clojure/html/total-control.html
 14. 
 15. There is a video at:
 16. http://www.youtube.com/watch?v=p5T81yHkHtI with keypress visualizations
 17. 
 18. The following are the highlights:
 19. 
 20. ! Introduction
 21. 
 22. Think of pokemon yellow as creating a little universe with certain
 23. rules. Inside that universe, you can buy items, defeat rival trainers,
 24. and raise your pokemon. But within that universe, you are bound by the
 25. rules of pokemon. You can't build new buildings, or change the music,
 26. or change your clothes.. There are some games (like chess), where it
 27. is not possible to alter the rules of the game from within the
 28. game. No matter what moves you make in chess, you can never change the
 29. rules of the game so that it becomes checkers or basketball. The point
 30. of this run is to show that you CAN change the rules in pokemon
 31. yellow. There is a certain sequence of valid actions (like walking
 32. from one place to another or buying items) that will allow you to
 33. transform pokemon yellow into Pacman, or Tetris, or Pong, or a MIDI
 34. player, or anything else you can imagine.
 35. 
 36. 
 37. ! Background
 38. 
 39. The speedrun (http://tasvideos.org/2913S.html) by Felipe Lopes de
 40. Freitas (p4wn3r), beats pokemon yellow in only 1 minute and 36
 41. seconds. It does it by corrupting the in-game item list so that he can
 42. advance the list past its normal limit of 20 items. The memory
 43. immediately after the item list includes the warp points for the
 44. current map, and by treating that data as items and switching and
 45. dropping them, he can make the door from his house take him directly
 46. to the end of the game.
 47. 
 48. When I first saw that speedrun, I was amazed at how fast pokemon
 49. yellow could be beaten, and that it was possible to manipulate the
 50. game from the inside, using only the item list. I wondered how far I
 51. could extend the techniques found in p4wn3r's run.
 52. 
 53. The gameboy is an 8 bit computer. That means that ultimately, anything
 54. that happens in pokemon is a result of the gameboy's CPU reading a
 55. stream of 8 bit numbers and doing whatever those numbers mean. For
 56. example, in the gameboy, the numbers: 
 57. 
 58. 62 16 37 224 47 240 37 230 15 55
 59. 
 60. mean to check which buttons are currently pressed and copy that result
 61. into the "A" register. With enough numbers, you can spell out an
 62. interactive program that reads input from the buttons and allows you
 63. to write any program you want to the gameboy. Once you have assembled
 64. such a program and forced the game to run it, you have won, since you
 65. can use that program to write any other program (like Tetris or
 66. Pacman) over pokemon yellow's code. I call a program that allows you
 67. to write any other program a "bootstrapping program". So, the goal is
 68. to somehow get a bootstrapping program into pokemon yellow and then
 69. force yellow to run that program instead of its own.
 70. 
 71. How can we spell out such a program? Everything in the game is
 72. ultimately numbers, including all items, pokemon, levels, etc. In
 73. particular, the item list looks like:
 74. 
 75. 
 76.  item-one-id         (0-255)
 77.  item-one-quantity   (0-255)
 78.  item-two-id         (0-255)
 79.  item-two-quantity   (0-255)
 80.  .
 81.  .
 82.  .
 83.  
 84. 
 85. Let's consider the button measuring program  [Unexpected EOL parsing text in []37 62 16 37 224 37 240
 86. 37 230 15 55] from before. Interpreted as items and item quantities, it is 
 87. 
 88.  lemonade     x16
 89.  guard spec.  x224
 90.  leaf stone   x240
 91.  guard spec.  x230
 92.  parlyz heal  x55
 93. 
 94. So, if we can get the right items in the right quantities, we can
 95. spell out a bootstrapping program. Likewise, when writing the
 96. bootstrapping program, we must be careful to only use numbers that are
 97. also valid items and quantities. This is hard because there aren't
 98. many different items to work with, and many machine instructions
 99. actually take 2 or even 3 numbers in a row, which severely restricts
100. the types of items you can use. I ended up needing about 92 numbers to
101. implement a bootstrap program. Half of those numbers were elaborate
102. ways of doing nothing and were just there so that the entire program
103. was also a valid item list.
104. 
105. The final part of the hack is getting pokemon yellow to execute the
106. new program after it has been assembled with items. Fortunately,
107. pokemon keeps a number called a function pointer within easy reach of
108. the corrupted item list. This function pointer is the starting point
109. (address) of a program which the game runs every so often to check for
110. poison and do general maintenance. By shifting an item over this
111. function pointer, I can rewrite that address to point to the
112. bootstrapping program, and make the game execute it. Without this
113. function pointer, it would not be possible to take over the game.
114. 
115. !! The Run
116. 
117. ! Pallet
118. 
119. I start off and name my rival Lp/k. These characters will eventually be
120. treated as items and shifted over the function pointer, causing it to
121. execute the bootstrapping program that will soon be constructed. I
122. start the run the same as p4wn3r's and restart the game while saving,
123. so that the pokemon list is corrupted. By switching the 8th and 10th
124. pokemon, I corrupt the item list and can now scroll down past the 20th
125. item. I shift items around to increase the text speed to maximum and
126. rewrite the warp point of my house to Celadon Dept. Store. (p4wn3r
127. used this to go directly to the hall of fame and win the game in his
128. run.) I deposit many 0x00 glitch items into the PC from my corrupted
129. inventory for later use. Then, I withdraw the potion from the
130. PC. This repairs my item list by overflowing the item counter from
131. 0xFF back to 0x00, though the potion is obliterated in the process. I
132. then take 255 glitch items with ID 0x00 from the computer into my
133. personal items.
134. 
135. ! Celadon Dept. Store
136. 
137. Leaving my house takes me directly to Celadon Dept. store, where I
138. sell two 0x00 items for 414925 each, giving myself essentially max
139. money. I hit every floor of the department store, gathering the
140. following items:
141. 
142.  +-------------------+----------+
143.  |##| Item           | Quantity |
144.  +--+----------------+----------+
145.  |1 | TM02           |  98      |
146.  |2 | TM37           |  71      |
147.  |3 | TM05           |   1      |
148.  |4 | TM09           |   1      |
149.  |5 | burn-heal      |  12      |
150.  |6 | ice-heal       |  55      |
151.  |7 | parlyz-heal    |  99      |
152.  |8 | parlyz-heal    |  55      |
153.  |9 | TM18           |   1      |
154.  |10| fire-stone     |  23      |
155.  |11| water-stone    |  29      |
156.  |12| x-accuracy     |  58      |
157.  |13| guard-spec     |  99      |
158.  |14| guard-spec     |  24      |
159.  |15| lemonade       |  16      |
160.  |16| TM13           |   1      |
161.  +--+----------------+----------+
162.  
163. 
164. After gathering these items, I deposit them in the appropriate order
165. into the item PC to spell out my bootstrapping program. Writing a full
166. bootstrap program in one go using only items turned out to be too
167. hard, so I split the process up into three parts. The program that I
168. actually construct using items is very limited. It reads only from the
169. A, B, start, and select buttons, and writes 4 bits each frame starting
170. at a fixed point in memory. After it writes 200 or so bytes, it jumps
171. directly to what it just wrote. In my run, I use this program to write
172. another bootstrapping program that can write any number of bytes to
173. any location in memory, and then jump to any location in memory. This
174. new program can also write 8 bits per frame by using all the
175. buttons. Using this new bootstrap program, I write a final
176. bootstrapping program that does everything the previous bootstrapping
177. program does except it also displays the bytes it is writing to memory
178. on the screen.
179. 
180. ! Finale
181. 
182. After completing this bootstrapping program, I go to the Celadon
183. mansion, because I find the metaness of that building to be
184. sufficiently high to serve as an exit point for the pokemon
185. universe. I corrupt my item list again by switching corrupted pokemon,
186. scroll down to my rival's name and discard until it is equal to the
187. address of my bootstrapping program, and then swap it with the
188. function pointer. Once the menu is closed, the bootstrapping program
189. takes over, and I write the payload....
190. 
191. !! Other comments
192. 
193. The entire video was played by the computer using bots. I used
194. functional programming to write search programs over different
195. possible game states to find the most efficient way of performing
196. general actions.  Some interesting things I developed but didn't use
197. were pretty printing functions to display the game's internal data
198. structures, and an "improbability drive" that forces improbable events
199. to happen automatically using search.
200. 
201. Here are a few example scripts:
202. 
203. 
204.  (defn-memo viridian-store->oaks-lab
205.    ([] (viridian-store->oaks-lab
206.         (get-oaks-parcel) ) )
207.    ([ script \]
208.       (->> script
209.            (walk [↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
210.                   ← ← ← ← ← ← ← ← ← 
211.                   ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
212.                   ← ←
213.                   ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
214.                   ↓ ↓ ↓ ↓ ↓ ↓ ↓
215.                   → → → → → → → →
216.                   ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
217.                   ← ← ← ← ←
218.                   ↓ ↓ ↓ ↓
219.                   ])
220.            (walk-thru-grass
221.             [↓ ↓ ↓ ↓ ↓ ↓ ↓])
222.            (walk [↓ ↓ ← ↓ ↓ ↓ ←
223.                   ↓ ↓ ↓ ↓ ↓ ↓
224.                   → → → ↑])
225.                  
226.            (do-nothing 1) ) ) )
227. 
228.  
229. This script walks from the Viridian City pokemon store to Oak's
230. Lab in the most efficient way possible. The walk-thru-grass function
231. guarantees that no wild battles will happen by manipulating the game's
232. random number generator.
233. 
234. 
235.  (defn-memo hacking-10
236.    ([] (hacking-10 (hacking-9) ) )
237.    ([ script \]
238.       (->> script
239.            begin-deposit
240.            (deposit-held-item 17 230)
241.            (deposit-held-item-named :parlyz-heal 55)
242.            (deposit-held-item 14 178)
243.            (deposit-held-item-named :water-stone 29)
244.            (deposit-held-item 14 32)
245.            (deposit-held-item-named :TM18 1)
246.            (deposit-held-item 13 1)
247.            (deposit-held-item 13 191)
248.            (deposit-held-item-named :TM02 98)
249.            (deposit-held-item-named :TM09 1)
250.            close-menu) ) ) 
251.  
252. 
253. This script calculates the fastest sequence of key presses to deposit
254. the requested items into a PC, assuming that the character starts out
255. in front of a computer.
256. 
257. !! Other Comments
258. 
259. The final payload program is multiple programs. I created a reduced
260. form of MIDI and implemented it in gameboy machine language. Then I
261. translated a midi file from http://www.everyponysings.com/ into this
262. reduced MIDI language. The payload program contains both the music
263. data and the MIDI interpreter to play that data. The picture works in
264. a similar way. There is code to translate a png file into a form that
265. can be displayed on a gameboy, and other code to actually display that
266. image. Both the image and the display code are also written by the
267. final bootstrapping program.  Even though my final payload is rather
268. simple, you can write any program at all as the payload. The source
269. for the sound and image displaying code is at
270. http://hg.bortreb.com/vba-clojure
271. 
272. This entire project is open source and I encourage anyone who wants to
273. take the code and play around!
274. 
275. 
276. !! Suggested Screenshots
277. 
278. * http://aurellem.org/pokemon-hack/code.png
279. * http://aurellem.org/pokemon-hack/code2.png
280. * http://aurellem.org/pokemon-hack/matrix.png
281. * http://aurellem.org/pokemon-hack/matrix2.png
282. * http://aurellem.org/pokemon-hack/pinkie-pie.png
283. 
284. Or whatever you all think would be best.
285. 
286. I encoded the video with/without button visualization here:
287. 
288. * http://aurellem.org/pokemon-hack/rlm-yellow-hack.avi
289. * http://aurellem.org/pokemon-hack/rlm-yellow-hack-no-buttons.avi
290. 
291. ----
292. 
293. [user:FractalFusion]: Replaced movie file to fix time (note that the parser works in such a way so that the time listed for a VBM can easily be faked).
294. 
295. [user:FractalFusion]: Response is well-received for the new concept. Accepting for publication.
296. 
297. [user:natt]: Processing...
298. 
299. [user:FractalFusion]: Changed branch to "Executes Arbitrary Code".

Last Edited by FractalFusion on 12/3/2012 8:28:42 PM
Page History Latest diff List Referrers