Optimal Arkanoid
May 17, 2019 8:13 PM Subscribe
The new glitchless, tool-assisted speedrun of the NES version of Taito's classic arcade hit Breakout clone Arkanoid is 10% faster than the previous record. It was done in an interesting way: the runner simulated the game on a frame-by-frame level in a C++ reimplementation, then used it to brute force a solution to each level, which required a year's worth of CPU effort (split across six cores) to accomplish. Here are full details, including video (12m) of the result played back in an emulator. For extra fun, he made an ASCII-art version of the run!
It is disgusting, perverse, and incredible to do this by brute force.
(I mean, it sounds like there's some memoization going on so it's not pure raw brute force search, which makes it less disgusting but no less incredible.)
posted by vogon_poet at 8:37 PM on May 17, 2019 [5 favorites]
(I mean, it sounds like there's some memoization going on so it's not pure raw brute force search, which makes it less disgusting but no less incredible.)
posted by vogon_poet at 8:37 PM on May 17, 2019 [5 favorites]
This is, in a very real sense, beating a game into submission.
posted by NoxAeternum at 8:47 PM on May 17, 2019 [7 favorites]
posted by NoxAeternum at 8:47 PM on May 17, 2019 [7 favorites]
For Doh has been destroyed, and time now flow reversely!
posted by skewed at 8:58 PM on May 17, 2019 [4 favorites]
posted by skewed at 8:58 PM on May 17, 2019 [4 favorites]
Niiiiiice.
On a slightly different note, I love how in this sort of game they kind of stick to the outer space theme for a while and then in upper levels they're like OH WE'LL JUST MAKE THE BLOCKS LOOK LIKE AN ICE CREAM CONE WHO CARES if you make it up here you surely appreciate our artistry.
And then the boss is a moai head.
posted by Rush-That-Speaks at 9:02 PM on May 17, 2019 [10 favorites]
On a slightly different note, I love how in this sort of game they kind of stick to the outer space theme for a while and then in upper levels they're like OH WE'LL JUST MAKE THE BLOCKS LOOK LIKE AN ICE CREAM CONE WHO CARES if you make it up here you surely appreciate our artistry.
And then the boss is a moai head.
posted by Rush-That-Speaks at 9:02 PM on May 17, 2019 [10 favorites]
Oh man, that was awesome. My thoughts while watching, in chronological order:
Now this — this — is worth a year of CPU time!
Yeah, go, go, go!
Oh man, three balls and speeding up — holy cow it’s returning all of them!
I could never get past this level...
*pant, pant*
Yes! My teenaged arcade-lurking self is avenged — take that you quarter-sucker!!
Jeez...this is really inhuman performance. How could anyone ever get this far...?
I...you know, we humans created a machine as a nemesis, and then many decades later created a machine to defeat it. There’s something profound in that.
Wow. This reminds me of that video of the computer-controlled Zerg rush that takes out a whole field of tanks.
If we ever get in a real war with an AI, we are so screwed. We’re all going to become paperclips.
Hah! A flower and clouds!
Oooh, moai head. I would have never, ever seen this screen, had it not been for this video.
YAY VAUS! FREEDOM!
Thanks for the awesome link JHarris!
posted by darkstar at 9:38 PM on May 17, 2019 [10 favorites]
Now this — this — is worth a year of CPU time!
Yeah, go, go, go!
Oh man, three balls and speeding up — holy cow it’s returning all of them!
I could never get past this level...
*pant, pant*
Yes! My teenaged arcade-lurking self is avenged — take that you quarter-sucker!!
Jeez...this is really inhuman performance. How could anyone ever get this far...?
I...you know, we humans created a machine as a nemesis, and then many decades later created a machine to defeat it. There’s something profound in that.
Wow. This reminds me of that video of the computer-controlled Zerg rush that takes out a whole field of tanks.
If we ever get in a real war with an AI, we are so screwed. We’re all going to become paperclips.
Hah! A flower and clouds!
Oooh, moai head. I would have never, ever seen this screen, had it not been for this video.
YAY VAUS! FREEDOM!
Thanks for the awesome link JHarris!
posted by darkstar at 9:38 PM on May 17, 2019 [10 favorites]
Arkanoid II for the Apple IIGS was the first actual honest to God commercial, not pirated from Apple //e-owning friends, game I ever had access to. I used to have dreams about the perfect release and then the perfect bounce so that you could angle your ball and get every single block in the fortress of unbreakable gold bricks in one shot. This video is a fulfillment of actual dreams I’ve had for over 30 years
posted by Space Coyote at 10:05 PM on May 17, 2019 [9 favorites]
posted by Space Coyote at 10:05 PM on May 17, 2019 [9 favorites]
I had to watch quite a while to see one that didn't start with "first get the triple-ball powerup"
One of his stated constraints was to use only the multiball powerup. The one where he didn't get it is level 11 which is composed entirely of silver bricks, which never drop powerups.
posted by swr at 10:12 PM on May 17, 2019 [2 favorites]
One of his stated constraints was to use only the multiball powerup. The one where he didn't get it is level 11 which is composed entirely of silver bricks, which never drop powerups.
posted by swr at 10:12 PM on May 17, 2019 [2 favorites]
silver bricks
After Johnny Wallflower, my second most loved/hated enemy.
posted by Fizz at 4:16 AM on May 18, 2019 [2 favorites]
After Johnny Wallflower, my second most loved/hated enemy.
posted by Fizz at 4:16 AM on May 18, 2019 [2 favorites]
To use all that time, ingenuity and likely more than a megawatt hour of energy to develop this solution to a retro game is peak kidult. The planet's fucked but we've got a perfect score at Arkanoid. Good job.
posted by scruss at 4:27 AM on May 18, 2019 [6 favorites]
posted by scruss at 4:27 AM on May 18, 2019 [6 favorites]
This is porn
posted by duffell at 4:32 AM on May 18, 2019 [1 favorite]
posted by duffell at 4:32 AM on May 18, 2019 [1 favorite]
This is how our robot overlords conquer us: create a computer that will play an olde timey computer game and just let that computer play its computer game. Us lousy human beings will be enthralled in all its bouncy ball glory.
posted by NoMich at 5:30 AM on May 18, 2019
posted by NoMich at 5:30 AM on May 18, 2019
Cool! I love this part: "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". I'd naively assumed a game like Arkanoid had a 100% random unpredictable RNG for things like which powerup drops. Or rather, a deterministic pRNG but with some hidden state like system time or temperature or whatever that mean it was unmanipulable. The fact that the RNG really depends on fully deterministic known state makes this possible. From what I've read of TAS runs, a lot of early games are like this. It's a surprise to me.
posted by Nelson at 5:45 AM on May 18, 2019 [2 favorites]
posted by Nelson at 5:45 AM on May 18, 2019 [2 favorites]
I’ve played and watched enough ‘noid that this was instantly obviously not human. Not necessarily because it was too good (at least in earlier levels) but just the economy and utterly static rests. Almost as obvious as fighting a computer compared to a real human in a fighting game.
posted by SaltySalticid at 6:01 AM on May 18, 2019
posted by SaltySalticid at 6:01 AM on May 18, 2019
I don’t understand how the first brick is always a multiball and then no other power-ups are triggered afterwards. Were the levels recreated with a construction kit for purpose of efficiency?
posted by furtive at 6:57 AM on May 18, 2019
posted by furtive at 6:57 AM on May 18, 2019
I dig the subtle flex towards the end where they give a Note On Optimization:
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.
Basically, they're saying that for the levels in Group A or B, not only is this the fastest current time, but claims that these are the fastest possible times, having been mathematically optimized, and that no one can ever do it faster.
Like Checkers and Tic-Tac-Toe before it, Arkanoid is now solved.
posted by The Pluto Gangsta at 6:58 AM on May 18, 2019 [7 favorites]
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.
Basically, they're saying that for the levels in Group A or B, not only is this the fastest current time, but claims that these are the fastest possible times, having been mathematically optimized, and that no one can ever do it faster.
Like Checkers and Tic-Tac-Toe before it, Arkanoid is now solved.
posted by The Pluto Gangsta at 6:58 AM on May 18, 2019 [7 favorites]
I don’t understand how the first brick is always a multiball and then no other power-ups are triggered afterwards.
They explain it in the document. Basically, the timing and nature of the power-ups is determined by a psuedo-random number generated by, among other things, the score and the position of the paddle. Since the TAS has total control over these things, it controls the powerup spawning.
posted by The Pluto Gangsta at 7:23 AM on May 18, 2019 [2 favorites]
They explain it in the document. Basically, the timing and nature of the power-ups is determined by a psuedo-random number generated by, among other things, the score and the position of the paddle. Since the TAS has total control over these things, it controls the powerup spawning.
posted by The Pluto Gangsta at 7:23 AM on May 18, 2019 [2 favorites]
Round 26, wow. If I ever managed to pull that off in real life I'd be like, 'well, I guess I'm retired from Arkanoid.'
posted by box at 8:33 AM on May 18, 2019
posted by box at 8:33 AM on May 18, 2019
The music smells like bowling alley hamburgers.
posted by amanda at 8:51 AM on May 18, 2019 [10 favorites]
posted by amanda at 8:51 AM on May 18, 2019 [10 favorites]
Also, if anyone is lurking and needs a cool MetaFilter handle: Optimal Arkanoid
You're welcome.
posted by Fizz at 9:59 AM on May 18, 2019 [5 favorites]
You're welcome.
posted by Fizz at 9:59 AM on May 18, 2019 [5 favorites]
/boggles
/boggles again
Arkanoid?! Somehow, I remember it (erroneously) as Araknoid.
I'm on the correct side of Berenstain Bears, though.
posted by porpoise at 10:48 AM on May 18, 2019 [1 favorite]
/boggles again
Arkanoid?! Somehow, I remember it (erroneously) as Araknoid.
I'm on the correct side of Berenstain Bears, though.
posted by porpoise at 10:48 AM on May 18, 2019 [1 favorite]
I heard a guy in Jersey beat it. Twice.
posted by Jessica Savitch's Coke Spoon at 11:50 AM on May 18, 2019 [1 favorite]
posted by Jessica Savitch's Coke Spoon at 11:50 AM on May 18, 2019 [1 favorite]
> I don’t understand how the first brick is always a multiball and then no other power-ups are triggered afterwards. Were the levels recreated with a construction kit for purpose of efficiency?
I was curious too so I looked it up. Basically for a machine-assisted run, the multiball is the only powerup worth anything to a robotic player. The others are:
I was curious too so I looked it up. Basically for a machine-assisted run, the multiball is the only powerup worth anything to a robotic player. The others are:
- Slow: Counterproductive for a speed run.
- Catch: Unnecessary when the ball can already be aimed with perfect precision; time spent not bouncing the ball is time wasted not hitting blocks.
- Expand: Makes the Vaus wider. Unnecessary since a ball will never be missed.
- Player: Hah, not gonna need a 1up for this.
- Laser: Lets the Vaus gun down blocks. Unlike the previous, this one isn't sporting. Or, at least, would change the dynamics of an automated playthrough enough to be better justified as a separate type of speedrun.
- Break: Even more of a cheat since it lets the player avoid completing a level.
Not truly brute force:
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.
I feel like there is a lesson here but too distracted by the inhuman all you need is kill-ness of the playing.
posted by q*ben at 6:39 PM on May 18, 2019 [1 favorite]
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.
I feel like there is a lesson here but too distracted by the inhuman all you need is kill-ness of the playing.
posted by q*ben at 6:39 PM on May 18, 2019 [1 favorite]
Crap. I was planning to challenge the humans to this game for the survival of their species. I guess I'll go the alternate plan, Rally X.
posted by RobotVoodooPower at 8:26 PM on May 18, 2019 [1 favorite]
posted by RobotVoodooPower at 8:26 PM on May 18, 2019 [1 favorite]
Yes, q*ben, but the post text was already entering the fifth line and Metafilter has started giving "maybe this is too long?" warnings if there's too much before the fold.
If you want to be completely pedantic, it's worth noting that NES Arkanoid can be played in two different ways, with the (included) paddle controller, or with a gamepad. The game is much more difficult with a gamepad, because the Vaus has a limited speed and sometimes it'll just be impossible to return a ball in time. Simulating a paddle-style controller, on the other hand, making a TAS would be relatively easy, since the script could just put the paddle wherever it needs to be to return a ball. This TAS simulates a gamepad.
posted by JHarris at 7:53 PM on May 20, 2019 [1 favorite]
If you want to be completely pedantic, it's worth noting that NES Arkanoid can be played in two different ways, with the (included) paddle controller, or with a gamepad. The game is much more difficult with a gamepad, because the Vaus has a limited speed and sometimes it'll just be impossible to return a ball in time. Simulating a paddle-style controller, on the other hand, making a TAS would be relatively easy, since the script could just put the paddle wherever it needs to be to return a ball. This TAS simulates a gamepad.
posted by JHarris at 7:53 PM on May 20, 2019 [1 favorite]
« Older Virtual Angkor: Visualising the Medieval Cambodian... | Choo-choo, here comes the coffee train! Newer »
This thread has been archived and is closed to new comments
posted by traveler_ at 8:25 PM on May 17, 2019 [2 favorites]