The twenty-first century has seen the rise of a new type of video games targeted at a mass audience of “casual” gamers. Many of these games require the player to swap items in order to form matches of three and are collectively known as tile-matching match-three games. Among these, the most influential one is arguably Bejeweled in which the matched items (gems) pop and the above gems fall in their place. Bejeweled has been ported to many different platforms and influenced an incredible number of similar games. Very recently one of them, named Candy Crush Saga enjoyed a huge popularity and quickly went viral on social networks. We generalize this kind of games by only parameterizing the size of the board, while all the other elements (such as the rules or the number of gems) remain unchanged. Then, we prove that answering many natural questions regarding such games is actually NP-Hard. These questions include determining if the player can reach a certain score, play for a certain number of turns, and others. We also provide a playable web-based implementation of our reduction, which is accessible at http://candycrush.isnphard.com.

Guala', L., Leucci, S., Natale, E. (2014). Bejeweled, Candy Crush and other match-three games are (NP-)hard. In 2014 IEEE Conference on Computational Intelligence and Games (CIG), (pp.1-8). IEEE [10.1109/CIG.2014.6932866].

Bejeweled, Candy Crush and other match-three games are (NP-)hard

GUALA', LUCIANO;
2014-01-01

Abstract

The twenty-first century has seen the rise of a new type of video games targeted at a mass audience of “casual” gamers. Many of these games require the player to swap items in order to form matches of three and are collectively known as tile-matching match-three games. Among these, the most influential one is arguably Bejeweled in which the matched items (gems) pop and the above gems fall in their place. Bejeweled has been ported to many different platforms and influenced an incredible number of similar games. Very recently one of them, named Candy Crush Saga enjoyed a huge popularity and quickly went viral on social networks. We generalize this kind of games by only parameterizing the size of the board, while all the other elements (such as the rules or the number of gems) remain unchanged. Then, we prove that answering many natural questions regarding such games is actually NP-Hard. These questions include determining if the player can reach a certain score, play for a certain number of turns, and others. We also provide a playable web-based implementation of our reduction, which is accessible at http://candycrush.isnphard.com.
Conference on Computational Intelligence and Games (CIG),
Dortmund
2014
Rilevanza internazionale
contributo
2014
2014
Settore INF/01 - INFORMATICA
English
Intervento a convegno
Guala', L., Leucci, S., Natale, E. (2014). Bejeweled, Candy Crush and other match-three games are (NP-)hard. In 2014 IEEE Conference on Computational Intelligence and Games (CIG), (pp.1-8). IEEE [10.1109/CIG.2014.6932866].
Guala', L; Leucci, S; Natale, E
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/118479
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 32
  • ???jsp.display-item.citation.isi??? ND
social impact