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

Bullet Journals Without the Pastels

Image
Late last year,  +Riona MacNamara  introduced me to the idea of  bullet journals , and I decided to give it a try over Christmas. It worked out for me and has seriously helped me getting shit done, without a snowfall of post-it notes to keep track of things (I have graphs and data to back this claim up, see the Statistics section). There are  many   pages   describing   bullet   journals , most of them showing intricately decorated journals done in pastels. If you're allergic to pastels, or don't have time to decorate your planner, here's my explanation. Guaranteed no florals - hell, I can't even do a straight line. Task Tracking Here are the three parts of my bullet journal I use the most, the task tracking parts. It has three levels: generic future tasks roughly by month, tasks for the current month, and tasks for today. The  future tracker  is where you keep tasks that you want to get around to eventually, but either don't have t...
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