Post subject: Value optimization search
Former player
Joined: 3/8/2004
Posts: 1107
Yeah, I came up with another crazy idea for making TASing more efficient. As we all know, the game keeps tracks of lots of different values at different addresses, and in SNES for example, it's a number from 0 to 255. You can view all those values in Snes9x's cheat search. For an example, I'll use collecting coins since the address would be easy to find. In this example, I want to get lots of coins quickly, so there are 2 possibilities. Either I search for how to get some number of coins in as little time as possible, or I search for how to get as many coins as possible in a certain amount of time. Let's say I want to get as many coins as possible in 1 seconds, or 60 frames, so here are the steps I would need to do: 1. Find the frame where you start having many choices of which buttons to press and pause the emulator. 2. Find the address where the game keeps track of how many coins I have. 3. Press a shortcut key to open up the "value optimization search" window. 4. Enter the address that I found. 5. Check one of 3 boxes to determine whether I want to minimize or maximize the value of the address in a certain amount of time, or minimize time to reach a certain value. In this case I'd want to maximize the value, and I'd enter 1 second in another box. If I chose to minimize time then I'd enter a maximum amount of time to search through. 6. Check or uncheck another box to determine if looping of the value is allowed. For coins, there's likely to be more than one address that keeps track of it, so this is how to tell it to assume that values lower than the starting value are really higher, and that the starting value is the lowest. Now for the most important part, the part where you put some restrictions on the search so it doesn't just search everything... 7. Check 1 or more boxes to determine which buttons you want to allow it to toggle on or off. For this case, you might choose left, and A, probably not B unless it's like SMB2 where letting go of B lets you slow down faster. 8. For each button that you checked for it to search, type in the maximum number of times that it's allowed to toggle on or off that button. For example, you know that you won't be jumping 10 times. You also know that unless you're jumping very low, there's gonna be a good amount of frames in a row that you press A, and then lots of frames in a row when you don't press A, so the number of switches between pressing and not pressing will be pretty low. 9. Optional step: Select the order that you want each button to be toggled on or off during the 1 second (or you can tell it if 2 of the toggles are going to be at the same time), or just tell it part of the sequence. For example, you might know that 3 of the toggles in a row are going to be press A, then let go of A, and then press left. 10. Click the search button, and a progress window comes up that shows you the button sequence that yields the highest value for the address that keeps track of the number of coins, or it could possibly show you the top 5 sequences. Then you click on the sequence of button presses that you wants, and it plays those and pauses at the end of the 1 second. In summary, this new feature would take advantage of the fact that you often know the general structure of the sequence of button presses you want to do and you just need to find the best frame to press or unpress a few buttons, so the emulator would follow the guidelines you give it and then test all the limited possibilities very quickly. This feature could be used to maximize coins, to find the fastest way to enter a door, to find the fastest way for an enemy to lose it's life, or possibly even the fastest way to travel a certain distance to the right.
Editor, Active player (296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
The problem is the number of different inputs. It is the core of it all. You really need a clever method to describe what are all the possible different inputs to try. In Rockman, I resorted to random-tries, because brute-forcing each possibility is just going to take too much time (in the scale of days or months). Fortunately, many different inputs lead to the same result, and thus the random-try method works very well. The method you described for describing the different inputs to try, is one way, but probably doesn't fit for all situations. To quote DeHackEd: the programming of restrictions on buttons is basically what reduces this from "eons" to "centuries" of CPU power
Former player
Joined: 3/8/2004
Posts: 1107
The method you described for describing the different inputs to try, is one way, but probably doesn't fit for all situations. So what if it doesn't fit for all situations? It fits for some situations so it'll save time for those situations it fits for and make the overall process of making a TAS more efficient.
Joined: 3/25/2004
Posts: 459
Alright. Let's agree that it would make a TAS more efficient, but this tool could only be useful for short time frames, because after too many frames the sheer number of combinations would take too long to calculate. Also, there are usually more factors to consider. Imagine that the top five coin-collecting methods involved Mario getting hit, but you need Mario to stay big for some reason. You would need to find more RAM addresses and put more parameters on your search. This type of technology would be beneficial in bonus rounds of games where you're required to collect as many of something as possible in a given time.
Joined: 4/3/2005
Posts: 575
Location: Spain
This may look weird, but some days ago I had a dream in which I was trying to solve this very problem. In the dream, I discovered that the problem of beating some games can be seen as a problem of solving a maze. I also realized then that mazes can be solved by using Divide & Conquer, a detail that I wasn't aware of until then. This could lead to an "efficient" algorythm to beat games, but I still have to experiment more with the idea.
No.
Former player
Joined: 3/8/2004
Posts: 1107
Here's another another idea to make the search shorter: Have an option that makes it automatically look for a pattern, and it pays attention to whether moving each toggle forwards or backwards helps or not. Also have an option to give it a button sequence that's an approximation of the perfect button sequence and then it starts searching for sequences similar to that one. Another useful thing would be a feature that lets you find the correct address faster. A way to do that would be to give it a sequence of button presses, then choose 2 frames, and then have it automatically search for addresses that either changed value between those 2 frames and didn't change before or after, or didn't change value between those 2 frames and did change before and after. To make it more specific you could use increased or decreased instead of just changed. For example, you could set the 2 frames around the part where you enter a door, then search for an address that changes between those 2 frames.
Joined: 3/25/2004
Posts: 459
A new age is upon us.