Posted: 11/8/2015 2:30 AM
(Edited: 11/8/2015 5:02 PM)
Post subject: RNG Helper: Script idea
Quote
Beefster
He/Him
Joined: 8/16/2015
Posts: 19
Here's basically how it would work: You give it a frame to try all possible inputs on. (you would find the frame where input influences the RNG) It runs all possible inputs, advances n frames on each iteration, and takes a snapshot and/or savestate and/or outputs the value of a RAM address. You can then review all of the outcomes and their inputs and then choose the input you want. This solution is O(n^2) O(2^n) where n is the number of inputs you enable it to test. This is pretty feasible for a single frame, MAYBE 2 (though that wouldn't likely help), and you could reduce the number of possibilities as well by allowing the user to put constraints on the input. (such as make sure the Up input is on and the pause input is off) Obviously, this is a lot easier than doing it manually. I will probably make a proof of concept at some point and use it in my current WIP if it works well. If someone wants to beat me to it, you're more than welcome to do so. It might be a while until I get to it; I'm not on Windows super often.
Posted: 11/8/2015 2:58 AM
Post subject: This topic interests me. I will watch it.
Quote
Pokota
He/Him
Joined: 2/5/2014
Posts: 779
I have a PRNG Bot script for BizHawk that can be used as a starting point (mine works for all boolean-style inputs); I haven't played with savestating-via-lua yet. I presume, given the reference to your current WIP, that there's a specific game in mind? Might I ask what the game is and what domain/address the in-game RNG is at? E: There's also Basic Bot starting with BizHawk 1.11.2, though it may or may not be what you need since (1) it's also a PRNG Bot and (2) it's more designed for finding a highest-valued output rather than preserving changes in value outputs.
Adventures in Lua When did I get a vest?
Posted: 11/8/2015 3:36 AM
Quote
Beefster
He/Him
Joined: 8/16/2015
Posts: 19
The game I'm currently TASing is Golvellius for SMS. I figured out that at various specific frames, inputs influence enemy spawns, which turns out to be extremely helpful for the run. I haven't actually figured out where the RNG is in memory, but I have an idea of how to go about finding it. (Any tips BTW? My idea is to find one of those frames and then see what changes when I change inputs until it narrows down to one memory address)
Posted: 11/8/2015 9:09 AM
Post subject: Re: RNG Helper: Script idea
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Beefster wrote:
This solution is O(n^2)
I think you mean O(2^n). If you try n inputs on a frame, and then n inputs on each of the resulting frames and so on, the amount of combinations grows exponentially.
Posted: 11/8/2015 12:25 PM
Quote
BrunoVisnadi
Editor, Skilled player (1345)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
SNES TAS of 2020 TAS of 2015 SNES TAS of 2015
What is 'O'? Supposing it is the number of frames, it would be 2^(n*O), right? For instance, in SNES there are 16 inputs. If you use them all, there would be 2^16 = 65536 possibilities. If you try for 2 frames there would be 2^32 = 4294967296 possibilities, which might be too much.
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Posted: 11/8/2015 1:14 PM
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
BrunoVisnadi wrote:
What is 'O'?
https://en.wikipedia.org/wiki/Big_O_notation
Posted: 11/8/2015 3:11 PM
Quote
Pokota
He/Him
Joined: 2/5/2014
Posts: 779
What I have in mind is basically a brute-force with a whitelist (always on) and blacklist (always off) to constrain the explosion of possibilities. The general form should be O(cn), where n is the number of inputs not on either list and c is (max button states * number of frames). E: Here's the SMS table.
"P1 B1": "False"
"P1 B2": "False"
"P1 Down": "False"
"P1 Left": "False"
"P1 Right": "False"
"P1 Up": "False"
"P2 B1": "False"
"P2 B2": "False"
"P2 Down": "False"
"P2 Left": "False"
"P2 Right": "False"
"P2 Up": "False"
"Pause": "False"
"Reset": "False"
14 inputs, so for one frame's worth of bruting it's 214. In practice, it's only 13 inputs as the reset button is a BAD THING. Constraining to P1 only would instead yield this table.
"B1": "False"
"B2": "False"
"Down": "False"
"Left": "False"
"Right": "False"
"Up": "False"
6 inputs, so for one frame this would be 26 - 64 possible results before black/whitelisting. For two frames this would be 46 because then you have four possible state combinations for each button rather than two - off-off, on-off, off-on, or on-on. This is 4096 results before black/whitelisting, which is obstructively large. For that reason, it's best to both minimize input frames and maximize button locks - taking even one button out of the hypothetical 2-frame check brings it down to 45 - 1024 possibilities.
Adventures in Lua When did I get a vest?