Finding Good Moves In Bejeweled, and Variants

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Unparallelogram
Posts: 336
Joined: Mon Jul 28, 2008 4:16 am UTC

Finding Good Moves In Bejeweled, and Variants

Postby Unparallelogram » Fri Mar 19, 2010 9:51 pm UTC

If you haven't played Bejeweled before, it may be easier to just link you the game rather than explaining it.
http://zone.msn.com/en/bejeweled/

I'm interested in figuring out some algorithmic strategies for Bejeweled and related puzzles. Here's what I figure so far.

1. The number of possible moves is pretty small. Searching a few ply isn't too bad.
2. You don't know what new pieces you'll get. I would like to find a heuristic for evaluating a position with unknown pieces.
3. The results of a combination are pretty apparent.

But, now consider a new variant. (There are other flash games of this. I forget the name(s).) This time, you're allowed to make any move you want, regardless of whether it removes any pieces. Each move has some cost, however, and it would only be worthwhile making moves that did not remove pieces if it led to removing a large number of pieces later on.

Here's what I figure.

1. The number of possible moves just got bigger. Searching a few ply is still okay. Anything further is fail.
2. If a combination is in your searching horizon, you'll see it. If not, you should probably get a heuristic.

Suppose that making combinations is really valuable. If you get multiple clears directly from a move, or from blocks falling into place after, it multiplies that move's score.

I'm kind of interested on what you guys have to say about doing this algorithmically.

Thanks!

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Finding Good Moves In Bejeweled, and Variants

Postby Xanthir » Fri Mar 19, 2010 11:24 pm UTC

In my experience, another good rule of thumb is to search near the top of the playfield first. Leave the lower combinations alone unless you absolutely need to use them, as they (a) tend to change the board more fundamentally, and thus are useful to shake things up when you start to get stuck, and (b) are difficult to regenerate once you've used them up, while combinations near the top reappear frequently.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
TaintedDeity
Posts: 4003
Joined: Sun Feb 10, 2008 7:22 pm UTC
Location: England;

Re: Finding Good Moves In Bejeweled, and Variants

Postby TaintedDeity » Fri Mar 19, 2010 11:38 pm UTC

As a noncoder but a regular bejeweled player I'd say that finding moves at the top of the board relies on you waiting for new pieces to fall down, whereas doing moves at the bottom or middle allows you to predict and chain moves even before the first move has finished fully.
I play on facebook where you are given a minute to get the highest possible score so speed is important.
A program could keep up that speed indefinitely, given enough moves.
Ⓞⓞ◯

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Finding Good Moves In Bejeweled, and Variants

Postby Xanthir » Sat Mar 20, 2010 1:10 am UTC

TaintedDeity wrote:As a noncoder but a regular bejeweled player I'd say that finding moves at the top of the board relies on you waiting for new pieces to fall down, whereas doing moves at the bottom or middle allows you to predict and chain moves even before the first move has finished fully.
I play on facebook where you are given a minute to get the highest possible score so speed is important.
A program could keep up that speed indefinitely, given enough moves.

Ah, that could be true. I was talking from my experience in zen modes, where time has no importance, only the number of moves you can keep it going.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Kow
Posts: 195
Joined: Sat Apr 19, 2008 12:37 pm UTC

Re: Finding Good Moves In Bejeweled, and Variants

Postby Kow » Wed Apr 07, 2010 4:16 am UTC

TaintedDeity wrote:As a noncoder but a regular bejeweled player I'd say that finding moves at the top of the board relies on you waiting for new pieces to fall down, whereas doing moves at the bottom or middle allows you to predict and chain moves even before the first move has finished fully.
I play on facebook where you are given a minute to get the highest possible score so speed is important.
A program could keep up that speed indefinitely, given enough moves.

I agree wholeheartedly (as does my mother, an avid bejeweled player).

Every bejeweled I've played has a timer left that you increase by gaining points, so working at the bottom of the board often allows for greater chaining and therefore a longer time to work.
Image


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 8 guests