Have you played Candy Crush Saga for hours on end? You’re not by yourself. It has been one of the most played games on Facebook and mobile devices since its introduction in 2012. The app became the second most downloaded game app during the first half of 2023, with over 106 million downloads (behind a game named Subway Surfers).
The game’s basic idea is to try to make horizontal or vertical chains of at least three similar sweets by switching nearby candies with one another on a grid covered with different colored ones. The candies in such a chain eventually fade out, and the ones above them descend. The game’s goals vary depending on the level. One objective, for instance, is to use a maximum number of swaps to build at least a minimal number of chains. The success of the game is partly due to its simplicity. It could be a little too well-liked. Candy Crush has been criticism for its great potential for addiction, maybe not limited to its users.
Toby Walsh, a computer scientist at the University of New South Wales in Australia, argued in an essay for American Scientist that “looking at Candy Crush as a math problem can be as addictive as playing it, at least for mathematicians.” In 2014, he fell victim to the Candy Crush virus. He didn’t, however, attempt to become an expert player like the majority of other admirers. Rather, his goal was to comprehend Candy Crush’s mathematical complexity. Put otherwise, given a certain maximum number of candy swaps, how hard is it for a computer to create a specific number of three-candy chains?
To what extent may games become complex?
Theoretical computer scientists have developed the idea of so-called complexity classes to categorize mathematical assignments into varying degrees of difficulty. In certain computational problems, for instance, it is uncertain if a computer will ever find a solution; it may continue to calculate indefinitely without doing so. In a way, these are the hardest duties of all. It turns out that Magic: The Gathering, a card game, falls into this category: even under the best of circumstances, there are times when it is impossible to predict which player will win.
You must ascertain whether a suggested solution can be promptly verified in order to assess the complexity of a game. For instance, you may easily verify whether the answer is right if you are shown a finished Sudoku problem. The issue falls into the nondeterministic polynomial time (NP) class, which characterizes the complexity of some mathematical problems, if the computing time required by a computer to verify the answer only rises polynomially with the task size. This is also the case with Candy Crush: you may rapidly determine whether the displayed result (the number of candy chains that were destroyed) is accurate by following the different swaps that are meant to generate candy chains step-by-step.
However, the fact that an issue is inside NP does not indicate how simple or complex the solution is. This is due to the fact that NP also includes easy problems in the polynomial time (P) category, another complexity class. The computing time a computer requires to solve a P issue only increases polynomially with the problem’s magnitude. This statement first seems a lot like the definition for NP, with the primary exception being that we are discussing the computing time required to solve a job rather than verifying its solution. Thus, issues in P may be effectively resolved and verified. One example of these “simple” challenges is sorting a list. In the worst scenario, however, the computing time increases as the list size squares. You must thus wait four times as long to sort the list if the number of entries doubles. From the perspective of a computer scientist, this is not much of an issue, even if it seems like a lot of time. As a result, projects that fall within P are regarded as easy as they often need little computational work to complete.
On the other hand, NP has challenging difficulties. The more complex the problem, the more computing time it takes to solve it. “I have software on my desktop computer that takes a few hours to determine the optimum route for ten trucks and to show that this was the greatest option available. However, the identical procedure would take longer than the universe’s lifespan for 100 trucks, Walsh clarified in his post. One of the best examples of “NP-hard” problems—tasks that are at least as challenging to complete as the most challenging NP problems—is optimal routing.
In light of these criteria, it is reasonable to assume that evaluating a game’s complexity nearly always requires looking at generalizations about it. After all, the scale of games like Candy Crush, Go, and chess depends on the playing space that is accessible. In these situations, theoretical computer scientists frequently research imaginary game extensions in which the board and the quantity of pieces, stones, or candies might be arbitrary.
How Is Candy Crush Related to Logical Statements?
Which complexity class does Candy Crush fall within, according to Walsh? Is it possible for a computer to effortlessly identify an effective strategy for the game? Candy Crush would be in P if this were true. Or does a computer also have trouble determining which candies to exchange? Walsh used a popular computer science method known as “reduction” to investigate this query. One must demonstrate that every other problem in NP can be reduced to a given problem in order to establish that it is NP-hard. In other words, if an algorithm for solving issue A can also solve every other NP problem, then problem A is NP-hard.
According to Walsh, what complexity class does Candy Crush belong to? Is it feasible for a computer to recognize a successful gaming strategy with ease? If this were the case, Candy Crush would be in P. Does a computer similarly struggle to decide which candies to swap? Walsh looked into this question using the “reduction” technique, which is widely utilized in computer science. To prove that a given problem is NP-hard, one must show that all other problems in NP can be reduced to it. Stated differently, problem A is NP-hard if the method used to solve it can also solve all other NP problems.
3-SAT is a logic job that requires you to determine if a connected sequence, or “concatenation,” of logical statements is right or results in a contradiction. x ∧ ¬x is an example of such a concatenation. On the surface, this appears to be complex. However, if you know that “∧” means “and at the same time” and that “¬” is a negative, you can interpret the phrase fast. As a result, the assertion may be expressed as both x and not x. The variable x must now be assigned the value “true” or “false” in order for the statement as a whole to be true (that is, without creating a contradiction). That is not feasible in this case as you obtain either true and simultaneously not true (for x = true) or false and simultaneously not false (for x = false). Since anything cannot be both true and wrong at the same time, neither sentence makes sense. As a result, this expression concatenation is not acceptable.
In 3-SAT problems, three variables are directly linked by chained sentences, such as (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧… ∧ (an ∨ bn ∨ cn). Here, “or” is denoted by the symbol “∨.” For the statement as a whole to be true, a computer must try to give truth values to the variables. Furthermore, this work turns out to be NP-hard. The amount of calculation time needed grows exponentially with job duration.
It was now up to Walsh to demonstrate that any 3-SAT problem could be represented in Candy Crush and that resolving Candy Crush solved the corresponding 3-SAT problem. To achieve this, he used variables and logical linkages in the 3-SAT problem to match candy configurations from the Candy Crush game, making a particular candy pattern represent a variable. He demonstrated that every logical statement in the form of 3-SAT may be represented by a suitable Candy Crush candy distribution in this fashion.
This is how it operates: Walsh reads a specific swap made by a player as giving a variable a truth value, such as “Variable 1 is false.” The field of play is altered with each switch. Moreover, it can form a chain of three sweets that vanishes instantly, enabling additional candies to go down the board. They may determine if the related 3-SAT statement is true or untrue by looking at the remaining candies on the board after making as many swaps as the relevant 3-SAT issue has variables. For instance, the phrase “true” is represented if, following all swaps, the square in the third row and second column has a yellow lemon drop.
The Candy Crush mission has been successfully completed since Walsh has already dispersed the candy on the playing field so that the yellow lemon drop only falls here if the bare minimum of three candy chains have been constructed.
In March 2014, Walsh used this technique to demonstrate that Candy Crush is NP-hard and, thus, mathematically complex. If you lose at another Candy Crush level, it can be comforting. However, there are benefits to the intricacy as well. “That trait may be part of what makes the game so addictive; if it were as easy to solve as tic tac toe, for instance, it wouldn’t be nearly as engaging,” Walsh wrote in American Scientist.