Revision (current)
Last Updated by Masterjun on 11/29/2023 9:56 PM
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.
%%TAB_START%%
%%TAB Reasonable (modern CPU + 1 year)%%
%%TAB_START%%
%%TAB Hide%%
%%TAB Show calculation%%
With an emulator you can check a Trace Logger and see how a game executes [https://i.imgur.com/OBER65W.png |~10,000 instructions per frame]. And since a game runs at roughly 60FPS, it's 600,000 Instructions Per Second (IPS).
On the [https://en.wikipedia.org/wiki/Instructions_per_second|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...
%%TAB_END%%
__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.
%%TAB Absurd (supercomputers + 100 years)%%
%%TAB_START%%
%%TAB Hide%%
%%TAB Show calculation%%
There is a list of the 500 most powerful computer systems in the world called ''[https://en.wikipedia.org/wiki/TOP500|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.
%%TAB_END%%
__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.
%%TAB Physical Maximum (universe CPUs + until heat death)%%
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.
>__Brute-force__%%%
>When the universe is just not enough
%%TAB_END%%