#6347: Chef Stef's NES Arkanoid "warpless" in 11:11.18

Submission Text Full Submission Page
This TAS completes NES Arkanoid in 11:12.57. It aims to obsolete Baxter's 2007 run and therefore has the same goals:
  • Complete all 36 levels
  • Use the multiball powerup and no others
  • Never lose a ball
  • Complete in the shortest amount of time.
It beats said run by 1 minute and 13 seconds through the use of new strategies discovered by a brute-forcing bot. The entire movie was generated programmatically; no manual input was involved.
The engine I wrote for this project includes a game visualization mode. Originally this was just for debugging, but for April Fool's Day I expanded it to do a full-playback visualization of the TAS with some faked content on the starting and ending screens. You can find that encode here: https://youtu.be/pQY1jSkcCDQ

The concept behind this TAS

I've always been intrigued by brute forcing as an optimization strategy and tried to find a game where it might be possible without spending multiple lifetimes finishing it. After some research, I decided that NES Arkanoid was a good candidate.
At first glance, brute-forcing an 11-minute TAS might seem to be completely impossible, having 2^8^(60 * 60 * 11) possibilities to evaluate. But that assumes we actually want to try every combination of inputs; if we encode the rules of the game into the bot and don't bother looking for things like glitches or ACE exploits, we can actually get this into the realm of possibility. The input surface of the game is actually quite small: you only have to press left, right, and A, and never any of those at the same time. There also aren't all that many ways to bounce the ball around.
I started with about 1500 lines of Lua scripting on top of Bizhawk. This was useful and proved out a lot of my ideas, but the execution time wasn't where it needed to be. Evaluations were maxing out at thousands of paths per hour, when I needed it to be billions per hour to make any kind of headway.
The bottleneck was emulation speed. Could I improve performance within the emulator? I found a few settings (like disabling the display) that gave marginal improvements. But I was still a long way from the goal.
And then I realized something - what if I could simulate the game state instead of emulating it? There's a lot of overhead in running BizHawk, running the Lua engine, and emulating the NES internals that isn't necessary if we're just trying to make a ball bounce around. Could I instead write an optimized, bare-bones program that mimicked Arkanoid's mechanics and then run my brute force bot on that?
So I went back to the drawing board. I disassembled the game, analyzed its logic, pulled out the routines that mattered for gameplay, and rewrote them all in C++. Logic for graphics, sound, and such could be omitted since they don't affect the physics or any outcomes in the game.
With the replicated game engine in hand, the next step was proving it was equivalent to the original. I constructed a test harness that fed Baxter's TAS inputs into the engine and compared memory values against what BizHawk showed for any divergence. This uncovered many small issues and inconsistencies that I painstakingly fixed. Eventually I'd resolved everything and could "play back" Baxter's TAS perfectly.
Now I could finally move on to brute-forcing the game. I wrote an evaluation engine with a bunch of rules (discussed later) to go through levels and output BizHawk movies with their solutions. After about a year of execution time on six CPU cores, I'd finally evaluated everything to a satisfactory point to assemble and produce this TAS.
There's a lot of potential in this type of brute-forcing and I'd love to see this happen for more games. The principles discussed below are game-agnostic; the key is the complexity of the game.

Reducing the brute force search space: Decision Points and Outcomes

So how do we tackle the brute forcing problem? At first glance, with 8 buttons on the controller there are 2^8 input possibilities per frame, for an 11-minute movie - an almost unimaginable volume to evaluate. But it turns out it's not so bad as that if you just think about the game a little differently.
The trick is that we can reduce everything down to a simple execution model of Decision Points and Outcomes. Decision Points are the moments when we as the one holding the controller have a chance to change the future state of the game; choosing what angle to bounce the ball, for example. Outcomes are all of the possible branches that emanate from that decision point; using the previous example, it'd be the gameplay paths corresponding to each of the directions the ball bounced.
The evaluation algorithm, then, is straightforward:
  • Step 1: Grab a job from a queue (job = any game state we saved off earlier).
  • Step 2: "Run" the game from that state until we detect the next Decision Point.
    • If we beat the level, go see if it beats the best-known solution, and save it off.
    • If we hit a losing condition (e.g. lost a ball) give up and go back to step 1.
    • Otherwise, generate a game state for each possible Outcome of the Decision Point and append it to the queue.
For many games, Decision Points happen every frame, making this only marginally better than true brute forcing. For example, in Mario games there's a decision point every frame whether to start, stop, or keep running. But in a game like Arkanoid, the number of Decision points is much less, and lends itself much better to this algorithm. Let's take a look at why.
The first obvious shortcut is to assume loading screens and menus contain no hidden tricks, and we're only brute-forcing in-level content; that cuts out about three minutes of content. Yeah, it's possible we're missing out on stuff like glitches and ACE exploits, but those aren't in scope for this TAS anyway.
Next, let's try and figure out what we can actually do during gameplay to affect Arkanoid's state. We can:
  • Launch the ball with A if it's not already been launched.
  • Move the paddle left and right.
  • Pause and unpause the game with Start.
Moving the paddle lets us do a few more specific things:
  • Bounce the ball in a specific direction
  • Manipulate what powerup will appear from a block
  • Collect powerups
  • Manipulate where enemies spawn
  • Manipulate where enemies move (in the rare cases when they move randomly)
  • Hit enemies (if they come close enough)
Now, if you think about how often these actually come up in a game of Arkanoid, it's not really that many. Well sure, for a human it seems like a lot; you have to hit the ball a bunch, grab the powerups, try and get the enemies, and it's all really quite hectic. But in the end these only happen once or twice a second; most of the time we're just waiting around for the ball to come back, or for something interesting to happen that we can manipulate. This is a huge improvement over having to decide on controller inputs every single frame!
This means for a 10-second level, instead of 2^8^600 possibilities, it's more like 10^15. Still large, but actually starting to look doable! What helps us even further is that we can prune branches that aren't useful to us, such as dead ends where we can't help but lose a ball, or branches where we've taken too long to accomplish anything.
Okay, enough talking in generalities. Here are the exact mechanics of Arkanoid's Decision Points:
  • Launching the ball: This amounts to where the ball should be launched from, and what frame to do it on. Sometimes we want to delay launching the ball so that enemies will be in a more favorable pattern, so in any level that has enemies we have to try all the launch-delay possibilities. Total possibilities: 4800 (48 launch positions x 100 possible frames of delay before launching the ball. It's possible to delay more than 100 frames but such a strategy is extremely unlikely to be faster than delaying less, so I've semi-arbitrarily drawn the line at 100.)
  • Manipulating a multiball powerup: When a powerup-containing block is broken, the game uses the paddle position (among other things) to determine which powerup should spawn. We always want a multiball powerup, of course. Total possibilities: 48 worst-case (48 paddle positions to check).
  • Collecting a powerup: There's a 10-frame window where the powerup is collect-able. Collecting it on different frames lets us manipulate when the single ball turns into a multiball, which affects how each ball can be bounced after that. Total possibilities: 10 (due to the available frame window).
  • Bouncing the ball with the paddle. There are a few scenarios:
    • Bouncing off the top: Six angles available (shallow / middle / steep going either left or right). Unlike most breakout games, the paddle speed doesn't matter, only the position of the paddle relative to the ball!
    • Bouncing off the side: Two angles available (shallow either left or right), but we can also manipulate the paddle position to make the ball take 1-4 extra frames to bounce, leading to a different result.
    • Bumping: This is where the ball would miss the paddle, but at the last second we shove the paddle back into the ball. Similar to side-bouncing, this results in one of two angles (shallow either left or right) and lets us manipulate when exactly the ball gets reflected back up.
    • Total possibilities: As many as 12, but often less (e.g. the wall can prevent us from moving the paddle to all of them).
  • Manipulating enemy spawns: An enemy is coming through one of the two gates. If the paddle is in the left half of the screen it'll come through the left one, otherwise through the right one. The act of stopping the paddle to manipulate an enemy can leave the paddle in a bad position to bounce the next ball, so there's a hidden third-possibility we have to consider, where we don't bother manipulating anything at all and just move on to the next Decision Point. Total possibilities: 3 (one for each gate, and a third for not doing any manipulation at all).
  • Manipulating enemy movement: In certain scenarios an enemy blocked in on multiple sides will use RNG to determine where to go next, which means manipulating it with the paddle position. Due to how random enemy movement works, the manipulation is always a choice between only two movement directions, but in the worst case we still have to check all 48 paddle positions. And like enemy spawn-manipulation, we also have to consider ignoring the manipulation to attend to more important actions. Total possibilities: 49 (all paddle positions + ignoring the manipulation).
  • Hitting enemies with the paddle: In very rare cases, enemies survive long enough to reach paddle height. Hitting them with the paddle destroys them and spawns a new enemy, so we can hit early or later to manipulate when the old enemy (hitbox) should disappear and when the new enemy should appear. Total possibilities: at least 100 (the frame window to hit an enemy before it goes below the paddle entirely).
Side note: Why care about enemies at all? There are two reasons. First, they have a hitbox, so they affect the path the ball takes through the level. Second, they give us points, and are the only way to manipulate the score (and by extension the RNG).
In addition, there are a few "end states" that result in the termination of a particular branch:
  • A ball being lost (i.e. unreachable by the paddle before it goes off the bottom): the branch is rejected, since one of the goals is to never lose a ball.
  • Frame count exceeding the current known-best time: the branch is rejected, since we're demonstrably slower than the current record.
  • All blocks broken: the level is complete, so the the branch is examined and possibly saved as a new record. The score is allowed to run up first since that's included in the level-completion time.
  • (Boss level only) Boss defeated: Same as all-blocks-broken, except input is simply ended on the final hit.
These are the Decision Points fed into the simple execution model described earlier. Each has rules for how to generate its respective Outcomes, which themselves become candidates for further evaluation as a new branch.
The rest is just CPU time!

Game Mechanics

Even in this simple block-breaking game there are many interesting mechanics that affect the strategy and had to be simulated.

Ball speed-up

After a certain number of block hits, the ball goes faster. Golden blocks (which are unbreakable) also count. The starting speed of the ball varies level to level, and the speed can be increased more than once. Some levels have so many blocks that the ball ends up going super fast by the end. Importantly, the game also increases the ball speed the first time a ball hits the ceiling of the level. This means we have two interesting strategies that can save time: 1. Hit golden blocks extra times to force the ball to go faster sooner. (Example: level 20.) 2. Get the ball to the ceiling earlier to get an early speedup. (Example: level 1.) Naturally, the bot exploits these organically as it evaluates the branches, rather than them being a part of the coded strategy logic.

Enemy spawning

The first three enemies spawn at set intervals that vary from level to level. While some levels seem to have no enemies (like level 1), they in fact just have very large intervals set and will eventually spawn enemies if you waste enough time not completing the level. Only three enemies can be around at once, but if any of them are destroyed then the game will keep spawning new ones until it's back to the full number. There are two gates from which an enemy can spawn. The decision is very simple: if the paddle is on the left side, the enemy will spawn from the left gate, and if the paddle is on the right then the right gate. Manipulating enemy spawn locations with the paddle is an important action in the simulation, since differently-placed enemies can lead to the ball bouncing in completely different ways.

Enemy movement

There are three phases to enemy movement: initial descent and wandering, circling, and final descent and exit. Enemies start by descending out of a gate and turning when they hit a block or wall. The movement pattern is mostly deterministic, but an enemy blocked on multiple sides (which can only happen by being boxed in by another enemy) can randomly choose its next direction to move. When the enemy's moved sufficiently far below the lowest row of remaining blocks, it switches to the circling pattern. It'll loop around a few times, gradually descending in the process. Interestingly, due to a bug with 2s complement and the movement tables, circling enemies will also gradually move to the right as well. Enemies no longer collide with blocks when circling. When the enemy gets sufficiently far down the screen, it switches to its final descent pattern of movement. All it does is move straight down; if it hits the paddle it'll get destroyed, otherwise it goes all the way off screen and despawns.

RNG

The RNG function in this game relies on a few deterministic values. The ones we can manipulate are the 100s digit of the score, and the paddle position. Manipulating the paddle position is obviously the easiest way to change the RNG, but sometimes it's necessary to manipulate the score too to get a better result. Blocks always give the same score when broken, so the only way to manipulate the score RNG is to kill a different number of enemies. This means it's sometimes advantageous to use a slower solution for a level so that a different number of enemies can be destroyed, and thus produce a better result for a subsequent level. It turns out to be faster to do this twice in the TAS (levels 16 and 29).

Other Pointless Stuff

These mechanics aren't really important for the TAS, but I found them interesting, so I'll say a few words about them here.

Powerup Spawning

When the game decides to spawn a powerup, it first generates a one-byte random number (RN). It checks that RN against a special table of six arbitrary values. If it matches one of the first three, the powerup is an extra life; if it matches one of the last three, it's a warp powerup. This means warps and extra lives have a 3/256 chance of spawning, each. If the game didn't spawn one of these rare powerups, it moves on to the common powerup logic. The game then looks at the lowest three bits of the RN and maps it to the common powerups like this:
 0 = Large Paddle
 1 = Slow
 2 = Sticky
 3 = Large Paddle
 4 = Multiball
 5 = Laser
 6 = Multiball
If you're wondering why Large Paddle and Multiball are on there twice, that's because 0 and 6 would normally correspond to the Extra Live and Warp powerups, but the game doesn't want those to be common, so it fills their slots with copies of other powerups. So if Slow, Sticky, and Laser powerups have always seemed a bit rarer to you, that's why! Finally, if the game finishes all this and you already have the powerup it rolled, it starts the process all over again until it gets one you don't have.

Ball movement after bumping

When a ball is below the height of paddle top, and is moving upwards, it moves at double speed until it's above the paddle. The only time this comes up is when bumping the ball off the side of the paddle. The behavior is seemingly pointless, but is probably to enhance the look of the ball "bumping" off the paddle. Or maybe the developers wanted the ball overlapping the paddle as little as possible and hurry the ball up to get it away... who knows!

Enemy Types

Despite how they look, every single enemy in the game behaves the same! All of those graphics are just for show, I guess.

Silver Blocks

Silver blocks take multiple hits to destroy, and the number of hits depends on the level. In level 1 they only take two hits, but by level 25 they take 5 hits. Many of the solutions for later levels center around silver blocks and how quickly to run the ball into them a lot. Interestingly, silver blocks also give a different number of points when broken, again depending on the level. The number of points is simply the level number times 50. So level 1's silver blocks give only 50 points, but level 33's silver blocks give a whopping 1650!

Starting ball speed

We've already discussed how the ball speed can change during a level. But there's also a starting speed for the ball in each level, too. Most levels start the ball at a "standard" speed, but several levels (8, 10, 14, 16, 23, 27, and 29) start it a little faster than usual, and a handful of levels (11, 13, 17, and 28) where it starts out slower than usual. This was probably done for a bit of variety, or perhaps to influence the difficulty of those levels.

Improvements over the previous TAS

In-level timing is from the first frame of control to the final frame of score tally.
Why time the score tally? Because the level doesn't advance until the score has finished tallying up, so if there were a lot of points queued up (meaning a lot of bricks were broken at the last second) the level will wait until they're all counted. This means that sometimes a solution that breaks all of the bricks sooner can actually be slower than one that finishes by breaking just one or two. The brute-force bot accounts for this so all levels are ultimately completed in the fastest real time.
Once the score has finished tallying up there's a constant 198 frames of loading screen and intro until the next level. There is no lag in the loading screen or anywhere else so the movie length is completely deterministic.
All times are in frames.
LevelBaxter's TASThis TASFrames SavedNotes
11207988219
21081825256It turns out breaking the wall of blocks from below is best, since there's a bigger gap from the ceiling to the blocks than from our paddle to the blocks. This principle applies in several other levels.
370360499
483275874
513121026286
6619488131The bot found a strategy producing this very short result. I like how the pattern of scattered blocks gets suddenly taken down in the last couple of seconds.
7807621186
82482480One of two levels where no time was saved; the previous TAS was already optimal. This is the shortest level in the set.
9627507120
10810696114I was quite surprised this much time could be saved considering how good Baxter's version looked. A good example of why waiting before launching the ball can be a good idea.
1116881477211This is one of my favorite solutions because of the crazy bouncing around and use of enemies. I was sure the original TAS had the best early strategy but was surprised when the bot found something even better.
1270762483
1349247418
1481874672
1517491352397The level with the most time saved, probably because of all the possibilities. It turns out to be much faster to break from the bottom up instead of sending the ball to the top as soon as possible.
1665857880This is one of only two levels where time had to be sacrificed to manipulate the score. It can be completed 7 frames faster (link) but the resulting score is unfavorable for later levels.
17829693136
1867262547
1972067050
2055452034The solution here abuses the golden blocks to increase the ball speed really quickly.
214484435Baxter's solution was almost optimal, but it turns out that waiting to launch the ball leads to a slightly better solution due to the enemy location.
22639535104
231304126539
24991891100
251193118013
267317310This is the other level where no time was saved. The original TAS's strategy of abusing enemies and keeping the ball in the top area turns out to be the fastest.
2715861456130
28926771155
2916391447192Like level 16, some time was lost to manipulate a better score. The best-known time is 5 frames faster (link).
3014401258182
311066101254
3281676353The initial bounces let us spawn a powerup from the side of the leftmost block instead of having to send the ball up and around, saving a lot of time.
3314371112325
34947702245
35818611207
Boss732763-31This TAS optimizes for last-hit rather than last-input. It defeats the boss 158 frames faster but due to ending input later it loses 31 frames compared to the published TAS. Note that this strategy is also 98 frames faster than the published warps TAS, which does aim for last-hit timing.
In addition, one frame was saved on the title screen by pressing Start sooner, one frame was lost on the title screen due to better startup emulation with NesHawk, and one frame was saved in level 1 by starting as soon as control is gained (the previous TAS waited a frame before starting).
This adds up to 4387 frames saved over the entire TAS (1:13.12).

A Word on Optimality

Even with all of the reductions and simplifications, some levels were still too complex to evaluate exhaustively with the bot. For those levels I added branch-pruning metrics and heuristics to bring the execution time within the realm of possibility. For example, if the current attempt is too far behind the published TAS (e.g. 20 fewer blocks broken with only 3 seconds to go) it's pretty safe to eliminate it and move on to more useful ones.
So which levels were exhaustively evaluated? I'll divide the levels into three groups:
 A. Level 8, 12, 13, 21, 26, 36 (boss)
 B. Level 1, 6, 10, 17, 19, 20, 23, 24, 28, 32, 34
 C. Level 2, 3, 4, 5, 7, 9, 11, 14, 15, 16, 18, 21, 22, 25, 27, 29, 30, 31, 33
Levels in group A were exhaustively evaluated; barring a mistake in the bot or game engine, these levels are optimal.
Levels in group B were evaluated with very basic assumptions that are unlikely to be wrong. For example, level 6 was shown to be optimal unless there's a solution that breaks 18 blocks in the last 88 frames. This almost certainly doesn't exist, so we can assume the solution is optimal, even if we didn't prove it.
Levels in group C were evaluated with bigger assumptions that could possibly be hiding better solutions. For example, level 4 assumes that launching the ball on the first frame (rather than waiting a few frames to bounce the ball off enemies differently) will lead to an optimal result. This was done because actually evaluating all of those extra ball-launch timings would take years, and enemies appear to have a minimal effect in this level. But a better solution may very well be out there.

Special Thanks

While I came up with the idea of simulating the Arkanoid engine on my own, I happily acknowledge that I'm not the first to implement something like this. I'd like to recognize MrWint's work on Super Mario Bros, Dragster, and Barnstorming as a predecessor to this TAS. This proved how powerful the technique can be and gave me more confidence it would work for Arkanoid. Thanks to MrWint for all of your awesome and innovative advancements in TAS tech.
I also took inspiration from Bisqwit's Lunar Ball TASes as an early example of bot-generated movies and brute forcing techniques. Without Bisqwit's TASes I probably wouldn't have even thought of making this. Thanks to Bisqwit for all of your work.
Thanks to Kiwisauce and cheetah7071 for being a sounding board for my ideas and having great suggestions of their own. This TAS would have been many seconds slower without their help. Cheetah7071 in particular suggested a branch-pruning technique that led to several levels' solutions actually being computable within my lifetime. Many thanks to both of them for their contributions.
Finally, thanks to Baxter for making the fantastic 3-ball TAS back in 2007. Many of Baxter's solutions were within a second of the optimal time already, no small feat for a game this complex. After doing this TAS I've gained a new appreciation for the work involved.
On to the next project!

feos: Amazing job in every regard, accepting to obsolete [961]NES Arkanoid "warpless" by Baxter in 12:26.80!
PS: Mister Windows NT is a cool guy indeed, almost as awesome as MrWint!
fsvgm777: Waiting on Chef Stef's thoughts on the movie file feos posted. After that, I will process it.
feos: Replacing the movie with a file without blank input at the end, and a few frames "saved" by tweaking the last input. The game ends at the same frame, so it's not a gameplay improvement, just a cleanup.
fsvgm777: All right, processing for real.

TASVideoAgent
They/Them
Experienced Forum User, Moderator
Joined: 8/3/2004
Posts: 11809
Location: 127.0.0.1
This topic is for the purpose of discussing #6347: Chef Stef's NES Arkanoid "warpless" in 11:11.18
Experienced Forum User
Joined: 6/4/2009
Posts: 893
round 33... heh
Experienced Forum User, Published Author (38)
Joined: 8/29/2011
Posts: 1160
Location: Amsterdam
Challenger
He/Him
Experienced Forum User, Published Author (2752)
Joined: 2/23/2016
Posts: 916
Sega TASer of 2017TASer of 2017NES TAS of 2017
This was totally surprising when I saw this submission. Initially, I thought that could be an April Fools joke... But I watched it. Man, how much time you improved for every round? This game is a nightmare for testing and optimization (seeing how the previous run is very solid optimization), so I never even considered that would be improvable so much! Yes vote.
My homepage --Currently not much motived for TASing as before...-- But I'm still working.
Editor, Experienced Forum User, Published Author (908)
Joined: 5/23/2006
Posts: 361
Location: Washington, United States
NES TAS of 2019Lucky TAS of 2019Funny TAS of 2013
All right, it's no longer April Fool's Day, so I've gone ahead and revealed a few things in the submission text...
Experienced Forum User
Joined: 6/4/2009
Posts: 893
ok, now that it's over, i still vote yes (and want the april fool video to be side by side with the original and use the Doh' video as a sound effect ) but also i'm wandering : why no laser ? it should save time to have the multi ball AND triple lazer doesn't it ? also shouldn't this caterogy technicaly be called 100% or warpless% ?
Experienced Forum User, Published Author (1842)
Joined: 5/31/2004
Posts: 1821
TAS of 2013SNES TAS of 2013Speedy TAS of 2007Innovative TAS of 2007
Wow, this is an amazing TAS! Congrats on getting this to work! Very fun to watch too :) I always knew that it was impossible for me to try out all options, so I kept going until I reached a solution was satisfactory. Someone improving my TAS would need to spend a lot of effort for a relatively small improvement. Turns out that evaluating this many options makes for a rather substantial improvement (but one I could not ever hope to have achieved by doing this manually). A bot was actually also used in the warps TAS of Arkanoid. Bisqwit helped me out with his bot for the part with the laser at the start of the warps TAS. Pressing the A button was the only available button for that part.
Chef Stef wrote:
Note that this strategy is also 98 frames faster than the published warps TAS, which does aim for last-hit timing.
I wonder if I should make this improvement to the existing warps TAS. Or do you think other improvements are possible?
Nicos wrote:
but also i'm wandering : why no laser ? it should save time to have the multi ball AND triple lazer doesn't it ?
No upgrades drop while having more than 1 ball in play. The choice for 3-ball only for this all-level TAS was for entertainment reasons. Using the laser in a TAS would not look vert different from a human player using it, while focussing on 3 balls at the same time at this speed is absolutely impossible for a human player.
GJTASer2018
He/Him
Experienced Forum User
Joined: 1/24/2018
Posts: 168
Location: Stafford, NY
Baxter wrote:
Chef Stef wrote:
Note that this strategy is also 98 frames faster than the published warps TAS, which does aim for last-hit timing.
I wonder if I should make this improvement to the existing warps TAS. Or do you think other improvements are possible?
I imagine that Chef Stef's bot could be fairly easily (by anyone well-versed in Lua scripting) tweaked to prioritize getting a warp powerup instead of a multiball. Then once you get through the demo glitch as in the current warps submission, the bot is set running. The task would both be easier (fewer levels to check and less stuff to keep track of in each level) and harder (RNG manipulation to get a warp powerup in the first place) than the warpless run.
c-square wrote:
Yes, standard runs are needed and very appreciated here too
Dylon Stejakoski wrote:
Me and the boys starting over our games of choice for the infinityieth time in a row because of just-found optimizations
<- Why I don't have any submissions despite being on the forums for years now...
Experienced Forum User
Joined: 6/4/2009
Posts: 893
Baxter wrote:
No upgrades drop while having more than 1 ball in play. The choice for 3-ball only for this all-level TAS was for entertainment reasons. Using the laser in a TAS would not look vert different from a human player using it, while focussing on 3 balls at the same time at this speed is absolutely impossible for a human player.
thanks didn't know that subtility also i found surprising to learn how much bruteforcing was involved when it's basicaly a big geometry formula for each shot...
Experienced Forum User, Moderator
Joined: 8/4/2005
Posts: 5745
Location: Moscow, Russia
Breathtaking. Some solutions even seemed a little counterintuitive, such as in level 30 where I would expect significantly more time for the balls to be spent in the upper half of the screen. But very entertaining throughout. Going into this, I knew it was (semi-)bruteforced, but it wasn't until I finished watching that I read the text entirely and realized what it was exactly that you did with the game to achieve it. Recreating the logic perfectly AND spending a year of CPU time running the simulation? Jesus almighty, that is some insane dedication. Certainly a TAS of the year contender in my opinion. Submissions like this are a real gift, and I'm continuously impressed by the quality of works that pop up here on April 1st, of all days. But you know what? One of the best takeaways from this, for me personally, was that Baxter wasn't far behind the optimal solutions to a set of incredibly hard problems. What a lad!
Warp wrote:
Edit: I think I understand now: It's my avatar, isn't it? It makes me look angry.
Experienced Forum User, Published Author, Senior Judge, Senior Publisher (1423)
Joined: 4/17/2010
Posts: 10321
Location: RU
NES TAS of 2011
Comparison (no frame diffs since it's already written, and no time is lost): Link to video
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting. If TASing is meta-play, TASVideos Movie Rules are meta-meta-play!
Editor, Experienced Forum User, Published Author (2799)
Joined: 5/15/2007
Posts: 3821
Location: Germany
Gameboy TASer of 2015NES TAS of 2013Gameboy TASer of 2011Gameboy TASer of 2010
This is absolutely insane!
Editor, Experienced Forum User, Published Author (908)
Joined: 5/23/2006
Posts: 361
Location: Washington, United States
NES TAS of 2019Lucky TAS of 2019Funny TAS of 2013
Feos, thanks for the comparison encode! Very interesting seeing the two side by side. One trend I noticed was that Baxter's TAS often had to spend a lot of time clearing the last few silver blocks, whereas the bot-generated run tended to get these as it went. Later in the game the silver blocks take a lot of hits and run up the score a lot for even more delays, so it seems the takeaway is to try and clear these sooner rather than later. The comparison also makes it clear the boss strategy is faster because the ball is moving faster, which is because the bot sends it to the ceiling as soon as possible. The first time the ball hits the ceiling it gets an automatic boost in speed, if it hasn't already sped up from block-breaking. Answering a few questions from the thread:
Baxter wrote:
Chef Stef wrote:
Note that this strategy is also 98 frames faster than the published warps TAS, which does aim for last-hit timing.
I wonder if I should make this improvement to the existing warps TAS. Or do you think other improvements are possible?
Discounting the demo glitch, the warps TAS is really straightforward so I don't think many other improvements are possible. It basically comes down to whether the warp powerups can be manipulated and collected any faster. The only thing I can think of is manipulating the score in a previous level to get a more favorable powerup manipulation in a later one. But overall things have been pretty well optimized by human TASers already. Then again, I thought the boss level wasn't improvable until I ran the bot on it, so who knows?
GJTASer2018 wrote:
I imagine that Chef Stef's bot could be fairly easily (by anyone well-versed in Lua scripting) tweaked to prioritize getting a warp powerup instead of a multiball. Then once you get through the demo glitch as in the current warps submission, the bot is set running. The task would both be easier (fewer levels to check and less stuff to keep track of in each level) and harder (RNG manipulation to get a warp powerup in the first place) than the warpless run.
It's worth noting that I didn't replicate anything into the game engine except the bare minimum needed to make this TAS, so no title screen, demo, or warp powerup (or any powerup besides 3-ball, for that matter). It wouldn't be that bad to add logic for those things, but it's effort I didn't spend. Side note, I intend to release the source code for the engine + bot, I just haven't found the time yet to make it happen. It's actually a standalone C++ program, not a Lua script.
nicos wrote:
also i found surprising to learn how much bruteforcing was involved when it's basicaly a big geometry formula for each shot...
Yeah, at the beginning I thought the same, that I could just calculate angles or something and simulate it that way. But there's a lot of annoying stuff in the game to prevent that. For starters, there aren't any subpixels in the game, everything is done with whole pixels and lookup tables to "fake" the angled movement of the ball, so the math immediately breaks down. Then there's rules baked into the game about how the ball snaps to a brick position when it hits it, enemy behavior, bumping the ball with the paddle, timing changes when you collect the powerup on different frames, and so on. In the end simulating it all was the only way to make it happen.
Experienced Forum User, Moderator
Joined: 8/4/2005
Posts: 5745
Location: Moscow, Russia
Chef Stef wrote:
Feos, thanks for the comparison encode! Very interesting seeing the two side by side. One trend I noticed was that Baxter's TAS often had to spend a lot of time clearing the last few silver blocks, whereas the bot-generated run tended to get these as it went.
It also spent a lot more time actually using the paddle instead of the wall and ceiling bounces, leading to e.g. less shallow angles—even more consistently so than I'd thought. You can clearly tell how Baxter was almost always going for a more human-intuitive strategy which nevertheless led to accumulation of time loss closer to the end of level: even when the balls spent more time closer to the blocks, they almost always spent less time actually hitting them. For instance, in level 11 which is comprised entirely of silver blocks with no multiball power-up, the strategies used in both runs were largely similar, but Baxter opted to eliminate more blocks as soon as the opportunity arose instead of spreading them out like the bot did. His approach ended up concentrating unbroken blocks at the edges which required a lot of idle time to get in the end—whereas the bot solved the last dozen of blocks by cleverly ricocheting the ball between 3–4 at a time because they were conveniently spread out. It's almost magical. Level 15 is an even better illustration of Baxter underusing of the paddle in favor of sending the balls to the ceiling gap. IMO this comparison video should be linked in the description to demonstrate the differences in optimized human and nonhuman approaches.
Warp wrote:
Edit: I think I understand now: It's my avatar, isn't it? It makes me look angry.
Experienced Forum User, Published Author, Senior Judge, Senior Publisher (1423)
Joined: 4/17/2010
Posts: 10321
Location: RU
NES TAS of 2011
This movie has some blank frames at the end, we usually don't leave those in because they give false impression about input length. While checking this I found that the very last input can end sooner too. Haven't tested earlier ones. Here's the movie. http://tasvideos.org/userfiles/info/54530816263675334 Chef Stef, what do you think?
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting. If TASing is meta-play, TASVideos Movie Rules are meta-meta-play!
Experienced Forum User, Published Author (38)
Joined: 8/29/2011
Posts: 1160
Location: Amsterdam
You spent a year solving Arkanoid via brute force? That is utterly incredible. This indeed deserves an award.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Many times it has been discussed what exactly it means for the two categories for rating TASes, entertainment and technical quality, and what their difference is. This TAS showcases absolutely marvelously what technical quality means.
Experienced Forum User, Published Author (38)
Joined: 8/29/2011
Posts: 1160
Location: Amsterdam
Warp wrote:
Many times it has been discussed what exactly it means for the two categories for rating TASes, entertainment and technical quality, and what their difference is. This TAS showcases absolutely marvelously what technical quality means.
Whoops, now this thread is no longer warpless! :D
Experienced Forum User, Published Author (2045)
Joined: 9/17/2009
Posts: 4871
Location: ̶C̶a̶n̶a̶d̶a̶ "Kanatah"
GBA TASer of 2010
For the submission text, the "(link)" appears to not exist:
This is one of only two levels where time had to be sacrificed to manipulate the score. It can be completed 7 frames faster (link) but the resulting score is unfavorable for later levels.
Like level 16, some time was lost to manipulate a better score. The best-known time is 5 frames faster (link).
Also is it correct to say the reason why some stages had a delayed start (10 for instance) was due to NPCs, or is it some other reason? Great improvement btw. Are you planning to brute force like this for any other games?
Yeah, at the beginning I thought the same, that I could just calculate angles or something and simulate it that way. But there's a lot of annoying stuff in the game to prevent that. For starters, there aren't any subpixels in the game, everything is done with whole pixels and lookup tables to "fake" the angled movement of the ball, so the math immediately breaks down. Then there's rules baked into the game about how the ball snaps to a brick position when it hits it, enemy behavior, bumping the ball with the paddle, timing changes when you collect the powerup on different frames, and so on. In the end simulating it all was the only way to make it happen.
Can you please elaborate on this? Would be very interested in how the game does the angles.
Experienced Forum User, Moderator
Joined: 8/4/2005
Posts: 5745
Location: Moscow, Russia
What it usually means is that the game doesn't calculate a trajectory for a ball (that would require processing quite a bit of floating point math which NES is extremely bad at); instead it has a table that contains data like "for this angle and speed, move the ball X pixels to the right and Y pixels up next frame until a collision happens". That way it bypasses the need to do complex calculations by having the number of variations boiled down to a reasonable minimum and having immediate access to the result of those calculations. It's the math equivalent of prerendered 3D sprites: instead of processing the entire geometry of a 3D model, store a 2D image of it at 4/8/16 different angles and replace them as needed.
Warp wrote:
Edit: I think I understand now: It's my avatar, isn't it? It makes me look angry.
Experienced Forum User, Published Author (1709)
Joined: 10/27/2004
Posts: 1968
Location: Making an escape
How tricky would it be to adapt this script to other Arkanoid like games?
A hundred years from now, they will gaze upon my work and marvel at my skills but never know my name. And that will be good enough for me.
Editor, Experienced Forum User, Published Author (908)
Joined: 5/23/2006
Posts: 361
Location: Washington, United States
NES TAS of 2019Lucky TAS of 2019Funny TAS of 2013
feos wrote:
This movie has some blank frames at the end, we usually don't leave those in because they give false impression about input length. While checking this I found that the very last input can end sooner too. Haven't tested earlier ones. Here's the movie. http://tasvideos.org/userfiles/info/54530816263675334 Chef Stef, what do you think?
If you just want to trim the input I don't see any reason why not. I thought it'd be fine to end on last-hit since the time gap is small, but I don't care much either way. Not sure I care about trying to optimize input length, since it doesn't make a difference for last-hit timing, though I won't complain if you want to adjust things.
jlun2 wrote:
For the submission text, the "(link)" appears to not exist:
Thanks, I've fixed that. Forgot to actually link in the movie files.
Also is it correct to say the reason why some stages had a delayed start (10 for instance) was due to NPCs, or is it some other reason?
If by NPCs you mean the enemies, yeah, that's it. They are in fact the only reason that waiting to launch the ball makes a difference.
Great improvement btw. Are you planning to brute force like this for any other games?
Ferret Warlord wrote:
How tricky would it be to adapt this script to other Arkanoid like games?
No plans but I'm sure this kind of thing is useful on games other than Arkanoid. The main issue is writing the game simulation engine, since that obviously has to be done from scratch for each game. But the brute-forcing concept would certainly work on other things, it'd just take work to generalize it properly.
Can you please elaborate on this? Would be very interested in how the game does the angles.
It's pretty much like moozooh said. Since you asked for it, here's one of the movement tables:
    std::vector<SpeedTableRow> SteepSpeedTable = 
    {
        { 1, 1, 5, 0, { 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
        { 1, 1, 4, 0, { 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
        { 1, 1, 3, 0, { 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
        { 1, 1, 2, 0, { 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
        { 1, 1, 1, 0, { 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
        { 2, 1, 0, 0, { 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
        { 1, 1, 0, 0, { 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
        { 4, 1, 0, 0, { 2, 1, 2, 1, 3, 1, 3, 2, 0, 0, 0, 0 } },
        { 2, 1, 0, 0, { 3, 1, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0 } },
        { 1, 2, 0, 0, { 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0 } },
        { 2, 2, 0, 0, { 2, 1, 2, 1, 2, 1, 3, 1, 0, 0, 0, 0 } },
        { 2, 2, 0, 0, { 2, 1, 2, 1, 3, 1, 3, 2, 0, 0, 0, 0 } },
        { 2, 2, 0, 0, { 3, 1, 3, 2, 2, 1, 3, 2, 0, 0, 0, 0 } },
        { 1, 3, 0, 0, { 2, 1, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0 } },
        { 2, 3, 0, 0, { 2, 1, 3, 1, 3, 2, 2, 1, 2, 1, 2, 1 } },
        { 2, 3, 0, 0, { 2, 1, 3, 1, 3, 2, 2, 1, 2, 1, 2, 1 } }
    };
It's essentially a precalculated table saying how the ball should move over multiple frames to simulate a smooth angle that's not one of the 8 basic ones (cardinal directions + diagonals). Each row corresponds to (what I've been calling) a "speed stage", i.e. how fast the ball is generally moving, where the speed stage increases as blocks are destroyed. (There are deterministic rules for that but I'll skip the discussion here.) The right section of the row is a set of vy-vx pairs that indicate how many pixels the ball should move that frame. 0, 0 entries are just padding and are unused. You'll notice that some rows have just one pair, while others have a varying sequence. The four numbers on the left are metadata for the ball movement. The first value is simply the number of vy-vx pairs in the row; it represents the cycle length, or period, of movement the ball goes through. The second value is how many times the ball should move per frame; the game does fast movement this way (rather than just increasing the vy-vx numbers) so that collision detection still works properly, e.g. so the ball can't just completely phase through a block. The third value is how many frames to delay before moving the ball once, and only comes into play if you've slowed the ball with the Slow powerup. The final value is unused (probably just padding for the table).
Experienced Forum User, Published Author (2045)
Joined: 9/17/2009
Posts: 4871
Location: ̶C̶a̶n̶a̶d̶a̶ "Kanatah"
GBA TASer of 2010
Thanks for the explanation!
moozooh wrote:
Level 15 is an even better illustration of Baxter underusing of the paddle in favor of sending the balls to the ceiling gap. IMO this comparison video should be linked in the description to demonstrate the differences in optimized human and nonhuman approaches.
I would love a console verified version to be showcased on AGDQ or some other event in the TAS block; it would definitely at least surprise people regarding the optimal solution, even if it wasn't an ACE.
Post subject: Movie published
TASVideoAgent
They/Them
Experienced Forum User, Moderator
Joined: 8/3/2004
Posts: 11809
Location: 127.0.0.1
This movie has been published. The posts before this message apply to the submission, and posts after this message apply to the published movie. ---- [3943] NES Arkanoid "warpless" by Chef Stef in 11:11.18
Experienced Forum User, Published Author (3565)
Joined: 5/25/2007
Posts: 386
Location: New England
NES TAS of 2018NES TASer of 2016NES TAS of 2016Funny TAS of 2016Glitchy TAS of 2016NES TAS of 2014TASer of 2009NES TASer of 2009
Cool! I used a similar simulation approach for River Raid. That game's logic is obviously simpler; I imagine on current hardware I could run my simulation for decent quality in close to real time. I've always been a fan of this Arkanoid category and had it in mind for something similar. The quality looks great; glad you did this!