1
\$\begingroup\$

Is there a known good way to have a "computer" opponent play a Match 3 game? It doesn't have to be fancy, or even considered fair. If the AI always takes the best move on the board that would be OK with me. Note that a valid move is one that doesn't make a match.

Edit: What I am currently doing is a brute force approach. I look at every tile on the board, and see what the best move that tile can do. I add it to a collection and give it a score (based on how many it will match 3 or 4). Once I have traversed the entire board I use the move with the best score. In the event of a tie I pick one.

If a 5 match combo is found I short circuit out to that one. 5 is the highest combo you can get)

I may not be able to improve it, but it feels like this should have been solved already.

\$\endgroup\$
2
  • \$\begingroup\$ This type of game is known as "Match 3". That might help you find more results. \$\endgroup\$ Commented Jul 21, 2011 at 1:44
  • \$\begingroup\$ awesome. thanks for that :) "bejewled-like" doesn't help much \$\endgroup\$ Commented Jul 21, 2011 at 2:55

2 Answers 2

Reset to default
4
\$\begingroup\$

One approach would be a simple tree-search algorithm, similar to the methods used for many deterministic puzzles.

The first problem is that the new gems added with each move are non-deterministic. One way to handle that is to consider all the possibilities for each new gem. This gives a way to estimate probabilities.

The big problem is that the number of combinations to consider would be immense, even a small number of moves into the future. The solution to that is to use heuristics to prune the tree, and to guide the search. For the random gems, only consider a small random selection of the possibilities.

For more tips and more detail, Google for tree search nondeterministic games.

http://www.google.com/search?q=tree+search+nondeterministic+games

On second thoughts, try tree search nondeterministic puzzles.

http://www.google.com/search?q=tree+search+nondeterministic+puzzles

Also, remember to keep it simple - there's probably very rapidly diminishing returns in Bejewelled, either for deeper searching or for more sophisticated heuristics.

\$\endgroup\$
4
\$\begingroup\$

Considering Bejeweled doesn't allow you to make a move that doesn't involve a match, couldn't you just figure out all subset of legal moves (you should already have this functionality if you prevent the player from making non-matching moves) and just pick the one that would give you the most points? From my understanding there isn't a ton of skill in Bejeweled as you're mostly at the whim of what the random number generator picks for your filler blocks.

Are you trying to design something more complicated like Puzzle Quest where looking ahead actually matters?

\$\endgroup\$
5
  • 3
    \$\begingroup\$ +1 - but there is some room for lookahead-based strategy in bejeweled. First, you get some new random gems with each move, but they don't replace all existing gems - some of the next few states is predictable. Second, where there's a choice of moves, some will result in more new random gems than others - depending on the current state, perhaps more randomizing is better, or perhaps preserving more is better. Finally, there may be heuristic-based ways of increasing the chances of creating higher scoring opportunities in the future, though many players heuristics probably don't really work. \$\endgroup\$ Commented Jul 21, 2011 at 1:51
  • \$\begingroup\$ Yes, you can make moves that do not form a match. \$\endgroup\$ Commented Jul 21, 2011 at 2:55
  • 1
    \$\begingroup\$ If you can make moves that don't form a match then it's not very Bejeweled-like, and the mechanisms for determining what you can do are going to be a lot more complicated. \$\endgroup\$ Commented Jul 21, 2011 at 3:12
  • 1
    \$\begingroup\$ @Joe: So, it's basically my favorite game of all time, Tetris Attack? \$\endgroup\$ Commented Jul 21, 2011 at 4:27
  • \$\begingroup\$ to an extent. It is really a mini game in an RPG I'm working on. (think of the card games in the FF series). You and the computer share a board and take turns making moves (3 per turn). you get points for matching the items, and combos. \$\endgroup\$ Commented Jul 28, 2011 at 18:23

You must log in to answer this question.