You might be exaggerating just a wee bit. Oregon Trail is the epitome of an educational game with lasting popularity, having been around pretty much as long as PCs. There are others -- Carmen Sandiego comes quickly to mind, and arguably even Kerbal Space Program. I'm sure some actual searching could compile a decent list.

https://en.wikipedia.org/wiki/The_Oregon_Trail_(series)

Imagine playing within the parameters and finding a combination that brings unexpected results. It's probably harder to design than a standard game, but I think there's potential to have something pretty entertaining otherwise.

It taught me a lot of (simplified) country locations and population sizes.

Cue John Galt's 100-pages monologue at the end of Atlas Shrugged.

The protein folding games paved the way to AlphaFold.

You take that back, I loved educational games as a kid! There were indeed plenty of crappy ones out there, but some were really well-made. For example, Pink Panther's Passport to Peril was a charming point-and-click adventure that taught you about cultures in other countries.

There's a small cult following in the Netherlands for these types of edutainment games and a small group of people have set out to archive all of them: https://nationaalarchiefeducatievegames.nl/

All educational games and all PHENOMENAL.

I mean the first sentence about enumeration and efficiency just shows how shallow the discover article is; the whole area of optimization is about efficiently finding optimal solutions without enumerating all possibilities.

To be honest this is the kind of science journalism quote which hurts science journalism a lot. Not only is it plainly false, the explanation is even worse. Any normal person reading this paragraph can not possibly come away with a correct understanding of the issue involved.

>The number of possible combinations are beyond any reasonable method for enumeration, and thus algorithms alone can’t solve this problem efficiently.

The number of ways to go from city A to city B is also not enumerable by any computer. Yet efficient algorithms to find a good path exist. Clearly the size of the problem space is not the issue.

But being the completionist that I am, I stopped playing it once I got to a level I wasn’t able to perfectly optimize across all three measurements.

They are indeed "real," bonafide (though perhaps sophomoric) programming problems. There is an Exapunks puzzle that has you implement a form of binary tree search/traversal in assembly.

Have you considered reaching out to the existing tetris community and having them donate their 2-3h runs to science? There has been great progress lately in some godly players reaching and beating the kill stage that's been around as a show stopper for years.