Non-deterministic algorithms explained using Stadia State Share

 One of the big open questions in computer science is known as "P = NP", meaning the question of whether (the default deterministic) Polynomial algorithms can solve the same problems as Non-deterministic Polynomial algorithms. We computer scientists are lazy fuckers who compress 40 letters into 2. Countless hours has gone into not just the research on this, but also on just wrapping your head around what "non-deterministic algorithms" really means. An algorithm is just an extremely detailed recipe for doing stuff. Non-deterministic? Does that mean you get to throw dice? Or does it depend on there not being a predetermined fate known only to a higher being? Video games to the rescue!

Stadia has introduced a feature called "State Share", in which you can share not just a screenshot or a video clip, but the entire state of the game that you're playing. Other players who own that game can then pick up from there and keep playing. Maybe later they'll share their state back to you and you can pick it up again. This is of course not really new, copying save games has been a thing since the home computer era, and some games (like NetHack) even go to great lengths to make it impossible to share or even save your game. But making it easy and integrated and online just enables possibilities that were previously impractical. And that's where non-determinism enters the game (pun intended).

Say that you're playing a fiendishly difficult game and you're looking at a particular nasty spot that you don't think you can easily get through. If you were to just save the game and try over and over again, you'd probably eventually make it through, but it would take you forever. That's the deterministic approach, spend lots of time trying again and again. 

But say that instead you use State Share to upload your problem to Teh Internetz, and your game problem goes viral! Thousands, nay millions of gamers, many way better than you, throw their time at the foul boss monster and its drooling minions. Eventually, one of them make their way through and shares the result with you. How much time did you spend on this? Well, you had to get to that point in the game first - that's just setup. Then the game took some time to go viral and spread widely enough, that's overhead. And finally, there's necessarily the time that it took that one person to make it through and share it back, that's finding the solution. But the time spent by all those other people? Not your time. Essentially, you got the internet to try a gazillion different solutions and only had to spend the time it took to find the one right one (plus some overhead). 

That's how non-deterministic algorithms work, in essence. You have some step with many possible variations, typically exponentially many for the interesting problems like Travelling Salesman. But instead of having to try them all yourself, you magically try all of them in parallel and only have to consider the time it takes for the correct solution. Technically, there's also a step required to check that the solution is correct, which the State Share analogy doesn't capture, except perhaps in that you afterwards continue the game and may find that the successful player had used all your potions and now you can't get through the next part. But that's a detail. You've just harnessed the incredible power of the internet to implement a non-deterministic algorithm and thus get a bit further in your game. Congratulations, computer scientist gamer!

Comments

Post a Comment

Popular posts from this blog

My Ikea Hack Workbench

Image
I needed a new workbench. One where my printer could live, where tools and spare parts could be organized, but also where the work surface wouldn't get cluttered or take too much of the space in my room. I started looking around at secretaries and similar, which have the right concept, but never the right size. Eventually I realized I had to do it myself. These are my notes. I used an IKEA Hemnes side table, two Hemnes night stands, and the top part of the two-part Hemnes writing desk. The two night stands on top of the side table, and the writing desk part on top of them, like the cross slab of a megalith, done in wood plank furniture. That part was simple enough, except I didn't want the gaps under the night stands, so I cut a bit of the logs, but cut too much, so now I need to fill some gaps. I'll probably print something eventually. But here's the basic setup: Hemnes, Hemnes everywhere. But they are clearly not designed to go together like these, the sizes don
Read more

I made 1:1 bread, and it is de-leeecious!

Image
If you have celiac disease or an actual gluten sensitivity, then this post is not for you. If you avoid gluten solely because of some dieting fad, you're losing out. This is good bread. This is bread that's better for insulin-resistant people. This is... high-gluten bread! Disclaimer: I am neither a nutritionist nor a doctor, I just play around with bread. This is pretty much my standard bread recipe, but substituting part of the flour with pure gluten - available as "seitan base", for instance this one on Amazon . This is somewhat more expensive (the price/g of protein is about the same for flour and seitan base), but it has a 50:50 carb:protein balance. Normal bread is more like 7:1, bad news for anyone with insulin problems. If you want to try this with your own favorite bread recipe, substitute about 1/4th of the flour with the seitan base and another about 1/6th with flax flour. Other proportions will work, too, I'll show you how to calculate it belo
Read more

Almond flour isn't just almond flour

Image
Looking around on the internet for how much almond flour to use instead of regular flour, I kept finding big variations, from 1:1 replacement to 1:2. Since baking is fairly finicky with the amount of ingredients, this confused me. But when I grabbed an extra bag of almond flour at the local grocery store (yes, there are specialty flours at the grocery store here), I noticed a difference in consistency and decided to take a closer look. Here's a close-up of the two flours using a macro lens. On the left is MeaVita Mandelmehl, on the right Borchers Premium Mandelmehl. In both cases, I've used a blunt instrument to gently distribute the flour to better see the difference. The flour on the left, the MeaVita brand flour, is in much larger chunks than on the right. The MeaVita flour also feels more moist, though I don't know if that's a direct effect of the size or because more oil has been extracted from the Borchers flour. It is, however, obvious that the two flour
Read more