Every now and then, the idea comes up to find the fastest way through whole video games, levels, or even just small sections by using brute-force: emulating every input button combination and choosing the fastest one.
This page is dedicated to giving an overview to prevent repetitions of the same discussion. Here we will do a calculation with several assumptions. The end result will be the number of gameplay frames you'll be able to brute-force with the given assumptions.
Game
- A simple NES game.
- Only one single button of input. (More will be added later.)
Resources
Not everyone has the same hardware to brute-force on. At this point I split the assumptions and provide 3 hardware and time constraints:
- One is a reasonable setup consisting of a modern CPU and one year of computing.
- The next one is an absurd setup consisting of the top supercomputers connected in a distributed system, and a whole lifetime - 100 years - of computing.
- The final one is the physical maximum consisting of atoms in the universe and computation until the heat death of the universe.
With an emulator you can check a Trace Logger and see how a game executes ~10,000 instructions per frame. And since a game runs at roughly 60FPS, it's 600,000 Instructions Per Second (IPS).
On the Instructions Per Second Wikipedia page the currently fastest CPU is an AMD Ryzen Threadripper 3990X at 2,356,230,000,000 IPS.
Dividing those results in a factor of 3,927,050. This is without the emulation overhead, but that can be ignored with proper optimizing and parallelization. It means we can emulate 3,927,050 seconds of gameplay each second (that's 45 days of gameplay... every second!).
There are 60*60*24*365 = 31,536,000 seconds in a year, so that gives us a total of 3,927,050*31,536,000 = 123,843,448,800,000 seconds of gameplay.
This means a grand total of 7,430,606,928,000,000 emulatable frames in this scenario.
It's a known formula that if you want to brute-force N input frames with 2 buttons states (= either on or off), you need to emulate 2^N frames. To reverse the formula we use the logarithm with base 2.
We have log_2(7,430,606,928,000,000) = 52.722...
We can only brute-force 52 frames of a single button. From here, if you have more than one button, just divide by the number of buttons. So two button halves it to 26 frames, three button to just 17 frames.
Note: We only computed 1 year. Increase it to 3 years (either by waiting longer, or by having 2 friends who help out during that year) and you get 54 frames. Just 2 more. That's the nature of logarithmic growth.
There is a list of the 500 most powerful computer systems in the world called TOP500. The list shows that the added performance of them all is 2,430,000,000,000,000,000 FLOPS (FLoating point Operations Per Second). Incidentally, the most powerful already existing distributed computing project also reached 2,430,000,000,000,000,000 FLOPS. Now let's connect them and reach 5,000,000,000,000,000,000 FLOPS.
As mentioned in the "Reasonable" section, an NES runs at roughly 600,000 Instructions Per Second (IPS). Nowadays most systems rely a lot on non-integer math so they are measured in FLOPS. With tests you can see those are usually not too far from IPS values, so it should be reasonable to equate them here.
Our factor is 8,333,333,333,333 and having 100 years we arrive at a grand total of 1,576,800,000,000,000,000,000,000 emulatable frames in this scenario.
And you get 80 frames. That's 28 frames more than a single person can do in a year. That's it. That's all you can brute-force. And you only have one button. Two buttons make it 40 frames. Three buttons make it 26 frames.
We have roughly 10^80 atoms in the universe, convert those into 12-atom transistors and get 10^79 transistors with a clock rate of 10^14 Hz. Now assign every transistor to an instruction and you have a CPU with 10^93 IPS. With the NES being 600,000 IPS, you get a factor of 10^88.
The heat death of the universe occurs in 10^100 years so we get a grand total of 10^197 emulatable frames. Now put that into the base-2 logarithm and fear the power of logarithms.
The universe gives us 654 frames of brute-force when it's about to die. That's just about 11 seconds. And we only have one button. Take two buttons and you only have 327 frames (5.5 seconds), or with three buttons you have 218 frames (3.6 seconds).
That's all the universe has.
Nothing more.
That's all the universe has.
Nothing more.
Brute-force
When the universe is just not enough