Is Bejeweled/Candy Crush Computer Solvable?

[Ahriman238]

First realize, despite my years using the computer and the web, my actual understanding isn't much more advanced than "magic box."

I was reading an article recently on how computers are programmed to win at tic-tac-toe, connect four, checkers, chess, go.... games with a fixed beginning state, and a finite number of possible moves. Shortly afterwards, I was watching someone play a Frozen-themed Bejeweled/Candy Crush-style swapping game, though this one apparently had a move limit. So naturally it made me wonder, can a computer be programmed to "solve" these kinds of games?

On the one hand, a randomized board that is filled in randomly as you play has to make things an order of magnitude more complex. On the other, the computer can already recognize and suggest valid moves. If it can't look forward to the potential moves created by certain moves that are possible now, the person I saw wasn't exactly playing to that level either.

Now that I think about it, Windows Mahjong works similarly. Random set-up, the computer suggests moves on request but they aren't always the best moves.

So is this possible? Or was it already done a while ago?

[Napoleon the Clown]

When an element of randomness is thrown in, it becomes substantially harder to solve. Think of a card game. You can increase your probability of making money if you know how to count cards, but it won't let you win every hand. Stuff like Candy Crush starts with a random set of pieces, and each new piece is randomly determined. How the randomization is determined, I can't say. Computers can't be well and truly random by their very nature, but they can be unpredictable enough for it to work.

I'm gonna say that a computer wouldn't be able to "solve" a game of Candy Crush 100% of the time. Play more efficiently than a human? Sure. But because the pieces you're going to get next are unknowable until they drop it won't be able to always win the game.

[Terralthra]

A computer can predict which pieces are going to drop just as well as a human will, which is to say, not really, but even given that constraint, a computer, properly programmed, will be able to always pick the optimal move in the situation that exists with information given.

Also, the pieces in Candy Crush et al. are not truly random, they're a normal distribution, which means the computer can keep track of which pieces have dropped more than others and guess at least what pieces will most likely come soon, if not their exact order.

[jwl]

Computers can be programmed to play poker and backgammon too.

[LaCroix]

Computers can be programmed to play poker and backgammon too.

That's a different topic. "Solveable" means that you can program them in a way they can win (or achieve a draw, in some games that can only be lost, not won) 100% of times. With enough calculation power, you can make a computer "not lose" at chess, but at poker, there is no way to do that. (Unless you cheat and let it know the card order but even then, it will lose hands due to drawing mechanics.) Backgammon is also not solveable, because dice rolls.

Any game that has a random component is not "solveable" by the strict definition. You can only try to make the best of the currently available picture, and reassess the strategy when a new component is added.

[Starglider]

"Solveable" means that you can program them in a way they can win (or achieve a draw, in some games that can only be lost, not won) 100% of times.

Although 'solveable' is usually discussed in terms of deterministic games with no hidden information, the concept of being able to fully predict outcomes applies to all discrete games, it's just that when there is hidden information the (provably) best possible prediction is necessarily a probability distribution. 'Solved' really means that we have a full description of the state tree such that a computer can trivially select the provably most optimal next move for any given state. Games with hidden information are definitely solvable in the general sense; the only criteria are that the states are discrete and the state tree can be computed within the time and space constraints of available hardware. Essentially what is happening is that you are traversing the true state tree of the game without knowing exactly where you are in that tree; the known state of the game (for any one player) is a union of all the possible states that it could currently be (with full knowledge). This reduces to a simple state tree with more transitions than usual. The difference is that with hidden information your opponent's choice of optimal move, given the information they have, may be different from what looks to you like their optimal move, given the information you have, even though you are both working from the same full solution of the game.

Fully solving the game of poker means that although we can't guarantee a win, we could prove which move is most likely to lead to a win for every hand and observed play sequence, and we could state and prove the probabilities for all possible outcomes if all players are playing optimally. Whether the hidden information is state you can't see (other people's hands, order of cards in a shuffled deck) or physically random events (dice throws) is not relevant. Of course this is the abstract game of poker, e.g. as played online with no chat and fixed timing, not the live game where humans reading each other's emotions is relevant.

Computers can't be well and truly random by their very nature, but they can be unpredictable enough for it to work.

Computers can absolutely be 'truly random' as much as anything in the universe is 'truly random', by introducing sufficient quantum sourced entropy into the 'random' sequence. The latest generation of Intel processors have a hardware random number generator (operating on quantum electronic effects) built in. Programmers frequently usually don't bother to make games 'truly random', since it's overkill for human players, but this is highly relevant for cryptography.

[Vendetta]

You could program a computer to make the best (ie. long term score maximising) move on a probabilistic basis but not in the way that perfect information games can be solved.

There are a few concepts to optimal play in a match-3 game like Bejeweled that your computer player needs to recognise:

The best probabilistic move would incorporate:

1. Matches available on the current board state.

2. The highest probability of future matches from infall.

3. Avoiding entropy.

The best move at any given time is the one which balances score output now with potential for score output in future (ie. not using an available match because it may potentially form a larger match or chain if another match is made instead) without drastically increasing the board entropy (leading to no more moves, matches close to the top of the board tend to generate less entropy because they do not disrupt matches below them, but matches at the bottom can disrupt those above)