How to calculate best move in Match-3 game?

Question

I am having a hard time identifying how to approach this problem.

If you have a match 3 game and the objects can only be swapped horizontally and vertically, and only swapped if it will result in a match of 3 or more jewels, which will be removed, with each removed jewel adding +1 to the score.

How would I find the best possible move? I'm confused at where to start and been searching for a while now and getting nowhere.

• Board 6x6 or 8x8
• Matches = 3 or more of same kind
• write function to find best swap for maximum score.

Any help would be greatly appreciated !

EDIT: So I could iterate through the entire board with a nested for loop for the rows and columns, but im not sure what approach to take from here.

For example, say I start with top left which is "red" and I want to test if swapping this will result in a match. How would I go about searching and identifying all possibilities that would result in swapping this left equaling a match and score of 5.

**If I am being really unclear I apologies and will remove my question and possible reword.

Answer 1

Do you want the best move right now, or are you looking moves in advance?

If it's just the best move right now for the most points on this move, try every legal move and then pick the one with the highest value. Assume incoming gems during a chain reaction don't match with anything so you get the best you can calculate with no concern for what random gems might fall in to replace them.

If you want to look moves in advance, then you use the minimax algorithm on the above tactic. As you go more moves in advance, the unknown non-matching gems will take up more and more space, which mimics the inability to plan very far in advance in these games.

Answer 2

Another approach is to brute force it. (Basically what Almo wrote, I will just explain the steps a bit more if you want only the best single move)

1. Make a copy of your game board. You always only work with the copy, not the original board.
2. You start at the top left tile. We are iterating now over the board, always checking to the right and bottom. You don't need to compare it to the left/ top since it would be a duplicated check.
3. If your current tile is a valid move, check how many points you got for it. If it was your first valid move, save the tile and direction of your move and the score. If it is a second valid move, compare the score. If it is higher, replace your old saved tile/ direction/ score.
4. After each valid made move, you grab another copy from the board and continue from the tile you checked last.
5. You can also check multiple moves, like what is the max score you can make in 3 moves. All you need to to is change the copy you take in 1. from the result board you get after you made the move.

One thing you need to pay attention is, how are you generating new tiles. If you have some CreateRandomTile(), you should replace it by a list that gets prefilled by a few dozen tiles from your CreateRandomTile(). That way you guaranty that you always have the same board. (And it is easier compared to clone the random function). You won't be able to evaluate the absolut best for 10 moves ahead, but 3 moves ahead is all you need. When you find the best 3 next moves, just make the first of the three and reevaluate again the next 3.

Answer 3

I'm pretty sure this problem doesn't have a neat algorithm to it, so brute force is the way to go:

var optimalMove = {points: -1, x: null, y: null, direction: null}
for each (x) {
    for each (y) {
        for each (direction in [up, down, left, right]) {
            // Create identical copy of the board so we don't mess up the actual board
            var copy = realBoard.copy()
            copy.moveTile(x, y, direction)
            var points = copy.removeConnectedTiles()
            if (points > optimalMove.points)
                optimalMove = {points, x, y, direction}
        }
    }
}
realBoard.moveTile(optimalMove.x, optimalMove.y, optimalMove.direction)

Can be slightly optimized by not doing a move if the board would look identical, e.g:

if(tileAt(x, y).color == neighbor(x, y, direction).color) 
    continue

If you're having trouble finding which tiles are connected to which other tiles (so, finding the actual score) I would (off the top of my head...) look for the biggest Flood Fill. The algorithm is quite simple:

function floodFill(x, y, color = null, checked = []) {
    var tile = tileAt(x, y)
    if(color is null) 
        color = tile.color
    else if (tile.color is not color)
        return 0;
    
    var sum = 0
    if(checked does not contain {x + 1, y})
        sum += floodFill(x + 1, y, color, checked + {x + 1, y})
    if(checked does not contain {x - 1, y})
        sum += floodFill(x - 1, y, color, checked + {x - 1, y})
    if(checked does not contain {x, y + 1})
        sum += floodFill(x, y + 1, color, checked + {x, y + 1})
    if(checked does not contain {x, y - 1})
        sum += floodFill(x, y - 1, color, checked + {x, y - 1})
    return sum
}

var highest = {score: -1, x: null, y: null}
for each (x, y) {
    if (floodFill(x, y) > highest.score)
        highest = {score: floodFill(x, y), x, y}
}

My implementation might have some issues, check the linked wikipedia page. Can definitely be improved in performance (if a tile has already been checked, no need to check it again).