Candy Crush network

King Digital, the creators of the popular smartphone game Candy Crush Saga were listed on the New York Stock Exchange two days after this game was shown to be NP-hard [1]. Could these two events be somehow related? Anyway, although the King Digital shares are not doing well, the NP-hardness proof still stands. A different NP-hardness proof for Candy Crush actually appeared on the arXiv a few weeks earlier [2], but was based on rules that are slightly different from the usual rules of Candy Crush.

So what is Candy Crush? It is a smartphone / tablet game having a rectangular board filled with different types of candies. A player can score points by swapping two adjacent candies in order to match three or more candies of the same type. This seems to be even more addictive than eating candies, which made the game the most popular game of Facebook, and led to a 568 million dollar profit for King Digital in 2013.

Interestingly, Candy Crush Saga is one of a large family of games that are all based on matching objects. These games all seem to be closely related. Moreover, their genealogy is not tree-like at all, as shown below. Many modern games have been derived by combining ideas from different older games. In other words, the genealogy of such games can best be described by a phylogenetic network.

A phylogenetic network for Bejeweled-type games, taken from [1], which was in turn taken (after modification) from [3].

This network is clearly a rooted, genealogical phylogenetic network (although it does not have a unique root).

So what does the NP-hardness of Candy Crush tell us? Nothing, of course, except that the 97 million people daily playing Candy Crush are pouring all their energy into solving a frivolous, but nevertheless intrinsically hard, problem. This is a pity because, since Candy Crush is NP-hard, one can (at least in theory) encode any NP-complete problem as a Candy Crush episode. This could be used to let all these 97 million people solve more useful NP-complete problems every day. For example, we could encode massive phylogenetic network reconstruction problems as Candy Crush episodes, and use this to construct the Web of Life in a few days!

References

[1] Luciano Gualà, Stefano Leucci, Emanuele Natale. Bejeweled, Candy Crush and other match-three games are (NP-)hard, http://arxiv.org/abs/1403.5830 (24 March 2014)

[2] Toby Walsh. Candy Crush is NP-hard, http://arxiv.org/abs/1403.1911 (8 March 2014)

[3] Jesper Juul. A casual revolution: reinventing video games and their players. The MIT Press, 2012.


Later note:
It turns out that the figure shown above is not actually taken from [3], in spite of the claim made in [1]. The figure in [3] is re-drawn from [4], and the genealogy as shown in [1] is edited directly from [4], not [3]. The editing consists of deleting all of the many other descendants of Tetris. The original complete figure is available here.

[4] Jesper Juul. Swap adjacent gems to make sets of three: a history of matching tile games. Artifact 1: 205-216, 2007.