## 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

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!

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Finding Good Moves In Bejeweled, and Variants

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

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

### Re: Finding Good Moves In Bejeweled, and Variants

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.
Ⓞⓞ◯

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Finding Good Moves In Bejeweled, and Variants

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

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

### Re: Finding Good Moves In Bejeweled, and Variants

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.