Search the Community
Showing results for tags 'Video Games'.
-
Fess up. There was a Bulbasaurus on my coffee table!
-
It has been demonstrated that solving Bejeweled (or in my case, Bejeweled 2) is an NP-Complete problem, or that the solution is NP-Hard. This means, in computational theory, that it has been proven impossible for an algorithm (i.e., a computer, not a human) to solve this problem in Polynomial Time every single time. If you can prove just one instance where it can't (using proof by counterexample), the problem is deemed NP-Complete. When a problem is NP-Complete, it sometimes takes "n-to-the-n-power" computations to solve it, and there are many, many computational problems in this world where computer scientists cannot prove whether they're NP-Complete or not - they simply don't know (they *think* they are, in fact, they're instinctively certain they are, but they can't prove it (*)). However, Bejeweled is one of the problems where they *have* proven that it's NP-Hard (the 8-by-8 matrix has the same dimensions as a chessboard, and a lot of time and energy have been spent researching these types of problems). This is irrelevant, of course, as all of this is just a McGuffin for a humble brag as I announce my retirement from my brief foray into the world of playing Bejeweled after this game: There are now three games I've played in my life that I became *really* good at: Space Invaders, Tetris, and Bejeweled 2. To those who know me, it should come as no surprise that all three of these games are mathematical, "tile-matching" games - that's just kind of how I think. Oh, I was pretty good at a couple of others (Galaxian, for example, and I'm a pretty wicked Pinball player (I *love* playing pinball, and have always wanted to buy a machine)), but back in 1979, my friends and I would go to the arcade in Glenmont Shopping Center, and I'd play Space Invaders for over 30 minutes on a single quarter. Man, those were some fun times - in 9th grade (I think it was), I switched from years of bowling duckpins at White Oak, to being on a team with my friends at Glenmont. Part of me felt like a traitor, but one must move forward. When I first saw Dragon's Lair in college (the first "cartoon-based" video game I ever encountered, featuring Dirk the Daring), I knew the thrill was going to soon be gone for me - I played it about ten times (and this is back when a quarter meant something to me!), never made it beyond about thirty seconds, and turned my back on it, forever. Incidentally, along with Pong and Pac-Man, Dragon's Lair is one of only three arcade games in storage at the Smithsonian Institution. In writing this post (which nobody is going to give a *shit* about but me), I imagine how Joe H must sometimes feel when he pours out his reminisces - well, Joe, *I* appreciate them (as long as they don't become repetitive), and they'll be here for posterity so your descendents will find them. As a separate issue, I got *nineteen* red cubes, and couldn't make a line of four-in-a-row. That must be pretty close to the maximum possible number (I suspect that determining this number itself is an NP-Complete problem all by itself): Of course, there is Mike Leyde. Interestingly, 2,143,483,647 is a number very familiar to me: it's 2 to-the 31st power minus 1, or the largest number that can be stored in a 32-bit register. If it were just one higher, it would require a 64-bit processor). --- (*) Christopher Langan, supposedly having one of the highest IQs ever recorded, claims that he can solve the NP-Complete issue. This would be a Abel Prize-level accomplishment, and I'm betting that he won't be able to do it. Langan is an interesting character, and if you want some entertainment, you should read or watch about him - I've seen a fair amount, and I'm still not certain of how intelligent he is (or isn't):
- 4 replies
-
- Computational Theory
- NP-Complete Problems
-
(and 2 more)
Tagged with: