Post subject: When to stop the search for optimal RNG
Player (67)
Joined: 4/19/2014
Posts: 16
Hi there, We're currently working with VicoV on another TAS of Saturn Bomberman, now that we're done with this one. This time we're going for the Normal mode. The main difference (apart from having two players to control) seems to be the additional randomness involved: each level's destructible blocks and items layout is RNG-dependent. RNG in this game is influenced by two things AFAICT:
  • The number of frames before Start is inputted at the "Press START" item in the menu determines the initial RNG.
  • Every time an action requiring RNG is taken (map generation, random item drop, most enemy movements) it is cycled.
With this in mind, what we've tried as of yet can be summed up this way:
  • For the first level, we've added wait frames before pressing Start at that first menu item until we got a 'decent' level configuration, that is one that looks close to the best we could get.
  • To prepare for the next level, before taking the exit we've 'played' with enemy movements until they left the RNG in a good state. This can be achieved by having one player standing one pixel away from the exit, and the other standing at various positions close to the enemies when they're altering course. The effects on the next level layout are drastic.
TL;DR: both the initial state of the RNG and its state at level layout creation can be altered, but in a very chaotic way (definitely no obvious way of fine-tuning level layout). In this circumstances, when is it OK to stop optimizing ? I've thought about writing a Lua script to parse the level layout and test it for good pathing patterns, even maybe have it make the players move randomly at the previous level's end to completely automate the research process. That sounds like a lot of work though, both writing it and letting it run on every level's end. Would that be overkill ? Would you say testing a number of RNG states and going for a nice-looking one (satisfying a number of pathing constraints) is enough ?
Samsara
She/They
Senior Judge, Site Admin, Expert player (2123)
Joined: 11/13/2006
Posts: 2794
Location: Northern California
You stop the search when you have the absolute best RNG you can get. "Good enough" should only be in the vocabulary of console speedrunners. "Overkill" in the TASing world is almost expected at this point.
TASvideos Admin and acting Senior Judge 💙 | Cohost
warmCabin wrote:
You shouldn't need a degree in computer science to get into this hobby.
Patashu
He/Him
Joined: 10/2/2005
Posts: 4017
If you have ideas for how to bot/script assist finding the best RNG you can, you may as well follow through. It will be great practice!
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
Warepire
He/Him
Editor
Joined: 3/2/2010
Posts: 2174
Location: A little to the left of nowhere (Sweden)
Keep in mind that the most optimal RNG pattern may not be the one that is most optimal for the TAS. It all comes down to: "Much much time will I need to beat this layout?" combined with "How much time does it take to get the layout?" A less optimal pattern may be faster in the end because it would take too long to get the most optimal pattern. It's a bit of a tricky area. I wish you good luck.
Post subject: Re: When to stop the search for optimal RNG
Tub
Joined: 6/25/2005
Posts: 1377
As those above me said, for optimal results, you don't stop searching until it's perfect. Though it's understandable if you don't want to invest the time required. A good starting point would be to dissect the RNG. Which memory locations are related? What's the algorithm, what's the periodicity? If, say, there's only 256 RNG states (which isn't really uncommon in games), you can write a LUA script to generate the next level based on each of the 256 states, pick the best one and make it happen. (or, for the first level, pick the best ones and compare RNG waiting time to level time). With just 256 states, you could just make a screenshot of each layout and manually pick the best. If there are more than 256 RNG states, you'd need an algorithm for determining which layouts are good, then manually compare the best ones. As you noted, such an algorithm is nontrivial to write. Minimum number of blocks between start and goal is a good metric. Items on the path is a good metric, the closer to the start the better. And so on. A way to deal with different conflicting metrics, when one lacks a total cost function over all metrics, is to use a skyline filter. Example: Layout A requires bombing 10 blocks and yields 3 flame powerups on the way. Layout B requires bombing 9 blocks and yields 4 flame powerups. Layout C requires bombing 8 blocks and yields 2 flame powerups. Since layout B is better or equal to A in every single metric, layout A can be discarded. With layouts B and C, either has its advantages, so neither can be discarded. While this will still leave a bunch of possible layouts to manually check, it can remove a lot of obviously inferior levels.
m00
Editor, Skilled player (1405)
Joined: 3/31/2010
Posts: 2086
'Good enough' is when people don't realize anymore it could be better.
Post subject: Re: When to stop the search for optimal RNG
Editor, Expert player (2460)
Joined: 4/8/2005
Posts: 1573
Location: Gone for a year, just for varietyyyyyyyyy!!
th2o wrote:
In this circumstances, when is it OK to stop optimizing?
Here are some possible answers: 1. Whenever you feel like it. If you feel bad, stop. If you feel good about what you're doing, don't stop. 2. You should stop when you have a crystal clear mental image of what the optimal result would look like. Then just cherish the idea in your head and move on to other things. (This will save lots of work, but will leave the audience disappointed.) 3. The amount of work required for each additional frame saved will increase exponentially. In some sense the cost of optimization will approach infinity while the number of frames saved will approach zero, so stopping at any point can be a rational choice. 4. Never.