View Page Source

Every now and then, the idea comes up to TAS sections using __brute-force__: simply testing every input button combination and choosing the fastest one.

How many frames can we actually brute-force? Obviously, that depends on how long you let the bot running and how much CPU power you use.
But to get a feel for it, let's brute-force 3 situations and calculate how many frames we got out of it:
* 1 year + a modern CPU
* 100 years + many supercomputers
* Until heat death of the universe + every atom in the universe

Of course, not all buttons are important when brute-forcing, so let's assume the very simplest case: a NES game with only a single button.

%%TOC%%

!! Reasonable (1 year + a modern CPU)
! 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...
! Result: 52 frames
__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.
----
!! Absurd (100 years + many supercomputers)
! 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, a 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.
! Result: 80 frames
__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.
----
!! Physical Maximum (Until heat death of the universe + every atom in the universe)
! Calculation
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.
! Result: 654 frames ≈ 11 seconds
__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