Candy Crush: Beating the Odds
For anyone who doesn’t know, Candy Crush Saga is the reigning mobile gaming king. Candy Crush is essentially Bejeweled’s distant cousin in that you have to move adjacent candies to make combinations of 3 or more. The game’s addictive qualities has gained it such a staggering number of users that it nets roughly $633,000 a day between in-app purchases and ad revenue. I was recently stuck on a level that was a 9×9 board consisting of all 6 kinds of candies (red, orange, yellow, green, blue, purple). I was stuck on it for so long, I discovered an exploit where you could exit to the main menu from within a game and not lose a life as long as you haven’t made a move yet. With this knowledge, I began resetting the board every time I didn’t like the beginning candy layout and this got me curious as to what are the chances of starting with a good board. “Sprinkled” candies are the result of a 5 candy combo and are arguably the best single candy in the game. In order to make a one, you need two candies in a row of the same color, an offset candy of the same color, followed by two more candies of the same color. When you move the offset candy between the two pairs of same colored candies, a sprinkled candy appears. One of the best ways to start a game is being able to make a sprinkled candy on the first move, so I decided this would be my criteria for a “good” starting board.
(An example of a 5-combo on the first move)
I went about finding the probability for a “good” starting board (as defined by being able to make a sprinkle candy on the first move) by both statistical analysis and computer simulation. Let’s begin with the statistical analysis. Before we begin, I’d like to note that I’m not 100% sure on the accuracy of these calculations. Probability and independent events can often be a tricky subject and until I verify my calculations with a statistics professor while I’m still at the University of Georgia, I’m more trusting in the results of my simulation. Regardless, we start the calculations based on a large assumption that the probability of having a given candy at each location is 1/6. This is a large assumption because it is unknown whether or not Candy Crush levels favor certain colors to be more prominent level to level. Now, we have 6 key candies we need to be concerned about: the two pairs of consecutive candies, the offset candy of the same color, and the candy between the pairs. These are assumed to be independent events (the probability of having a candy at one location doesn’t affect the probability of having a certain candy at the next location). For a visual representation, look at the figure below:
In this drawing, we are looking to create a sprinkled candy out of reds. The chance of getting a red is 1/6, and we have 5 candies that we need to be red. Additionally, the middle candy needs to not be red (a 5/6 probability). To find the probability of consecutive independent events, you multiply them. So, the probability of starting with this specific red combination would be (1/6)*(1/6)*(1/6)*(1/6)*(1/6)*(5/6). This comes out to .01072%. However, this is the probability of a red combination. There are 6 total colors we need to account for, therefore multiply .01072 by 6. This gives us a probability of .0643% to have a potential sprinkled candy at any given location on the board. In order to find the probability across the entire board (because .0643% only accounts for one possible location) you need to find how many possible locations there are in the board. The math from here on out will change depending on the size of the board, but I’ll calculate it based on the actual level I was stuck on (9×9 board). You should notice that there are 4 different orientations this combo can have:
Because we are dealing with a square board, in order to find the total number of possible ways this combo can be represented in the board, we just need to find the number of ways it can be represented in one orientation and multiply that by 4. If our board was rectangular, we’d have to do additional calculations. Take the original orientation in my drawing and imagine placing this in the bottom left corner of the 9×9 board. The width of the board is 9, and the width of the combo is 5. In addition to the original placement, the combo can only move 4 more spaces before candies go out of bounds in the board. Vertically, our combo is two spaces tall. In a 9×9 board, it can be placed an 8 additional spaces up. By multiplying these, we get 5×8=40 different places in the board for this orientation. Multiply again by 4 to get all possible positions for this combination and you get 40×4=160. This means we have 160 locations at a .0643% chance per location. 160x.0643= 10.288%. This means that you have a 10.288% chance of starting a 9×9 board with the opportunity to make a sprinkled candy on the first move.
Probability By Simulation
I wrote the simulation in java because it’s one of my more proficient languages and it has garbage collection so as long as I structured it correctly, I wouldn’t run out of memory by running the simulation 10,000,000 times. I had a class to create the simulation board, a class to check the board, and a main class to run everything. On the board itself, I represented each color of candy with a number from 0-5. Using a random generator, I filled the board with random candies. Because Candy Crush accepts combos of 3 or higher, I had to check adjacent locations before placing a candy so that my simulation wouldn’t create any boards that were impossible to start with (by containing 3+ candies in a row of the same color). With a generated board, I had a method to loop through all locations in the board and check the 4 possible orientations of the desired combo. In order to save time/efficiency, I decided that after a 5 combo was found, I would break out of all loops and end that current simulation. Having just one 5-combo off the start meets the criteria of a “good” starting board, so there would be no need to check for any additional 5-combos in the board. After the simulation has run all it’s trials (generating a new board per trial), it computes and prints the ratio of “good” starting boards to the total number of simulations. By running my simulator on a 9×9 board 10 million times, it found 974576 “good” starting boards- thus giving a 9.746% chance of starting with a 5-combo on the first move.
While the expected value (statistical analysis) and actual value (computer simulation) aren’t incredibly far apart, I feel they should be a lot closer. The percent error for my experiment is (9.746-10.288)/10.288*100 = 5.2683% error. One possible source for that could be attributed to my random number generator that creates my boards. Upon revising this project in the future, I may try and use either a different generator or try and ensure a non-repeating seed. Another possible source of error could be attributed to my rusty knowledge of statistics. Until I get my calculations verified by a statistics professor (or someone with equal qualifications) I’m going to leave this source of error on the table. As for Candy Crush itself, I’m amazed that I was stuck on the level to inspire all of this for so long that I’d reset the board roughly 10 times before I made a move. Maybe if I had actually played every board instead of trying to reset boards I didn’t like, I would’ve beaten it a lot sooner. To anybody who has gotten to level 140 and is stuck like I was, good luck to you. According to my simulations, the odds really aren’t in your favor from the start.