Jump to content

DonRocks

Recommended Posts

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:

post-2-0-10627300-1455376115_thumb.png post-2-0-47385900-1455376159_thumb.png

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.

post-2-0-07150000-1455378630_thumb.png

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):

post-2-0-78786400-1455376257_thumb.png

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):

Link to comment
Share on other sites

It's late and I'm tired, but I don't think I can get a special cube using my red cubes in this situation:

post-2-0-41653900-1456381378_thumb.png

There are *eleven* red cubes in rows 2-4, plus an extra red cube in the top row, and even with this layout, I don't see how it's possible.

For those who don't know, you can get a "special cube" in 1 of 4 ways:

1) Lining up 4 cubes in a row creates a flaming cube

2) Using 5 cubes in a T-formation or an L-formation creates a star cube

3) Lining up 5 cubes in a row creates a hypercube

I can't believe that neither 2) nor 3) appear possible, but it's *incredible* that I can't even make a move that creates 1). Does anyone see anything that I'm missing? Assuming a special cube isn't possible, what move would you make here? I'm not touching this thing until I've had some sleep, but off the top of my head, I don't see one single "good" move to make.

Also, given the current configuration (which was a natural situation occurring in a game - a game in which I was kicking some major-league tuchas), I don't believe it's possible to change any-other colored cube to red in rows 2-4, and not have the ability to make a special cube. Is this correct? (I don't need a mathematical proof; an eyeball test by someone who knows how to play wouldl be perfectly adequate.) Whether or not my situation is the most robust possible that doesn't facilitate making a special cube probably *would* require a proof, but I certainly don't expect anyone to do that unless they're tremendously bored. :) Still, I'd love to see one, proving it one way or the other.

I'm a loser baby, so why don't you kill me.

(Brasserie) Beck

Link to comment
Share on other sites

And yeah, baby, I had six hypercubes going on at once!

post-2-0-73340700-1456685971_thumb.png

I know I'm a total zero, but there's something zen-like about playing this game, and this, too, shall pass (my time is better spent in more productive endeavors - once I walk away from these things, it's usually without looking back, and I don't think I can improve any more, so I'm about done).

Unless someone gives me reason to continue. :)

  • Like 1
Link to comment
Share on other sites

Well, it just now happened for the second - and *final* - time: I just set a personal record in Bejeweled, took a screen shot to have some proof, and ... *Poof!* ... it disappeared in Chrome. Gone into thin air. As if the game had never happened.

I had been playing the same game for about *five days*, and had just broken 4 million points - almost double my previous high score - and I even had a hypercube on the screen, so I could have kept going for awhile longer. At Level 23, you get 1,150 points for every single three-cube explosion - that's 23-times as many points as you get on Level 1 (it increases 50 points per 3-cube explosion, per level). Blowing up 3 cubes at Level 23 is the equivalent of blowing up 3 cubes *23 different times* at Level 1. This is a game where the rich get richer.

I will never know how high I could have scored, I will never know the statistics for the game, I will never know how many cubes I blew up, or how many hours I played.

All I have as a momento of my *last ever* game of Bejeweled is this one, lone, screenshot, and thank *goodness* I took it, although taking it is what caused the game to disappear:

post-2-0-17610000-1457478699_thumb.png

Damn. Well, who knows, I could have lost ten minutes later. Or not.

Either way, I'm done - it would take *so long* to get back to this position, that it's just not worth my time to try.

Farewell, Bejeweled - you were a fun little addiction, but now it's time to move on and get back to work.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...