Bejeweled, Candy Crush and other match-three games are (NP-)hard.
Luciano GualàStefano LeucciEmanuele NatalePublished in: CIG (2014)
Keyphrases
- np hard
- optimal solution
- approximation algorithms
- special case
- video games
- lower bound
- nash equilibria
- branch and bound algorithm
- np complete
- game theory
- remains np hard
- data sets
- computer games
- computational complexity
- linear programming
- general game playing
- scheduling problem
- game tree search
- game play
- game playing
- game theoretic
- decision problems
- online game
- weighted majority
- monte carlo tree search
- greedy heuristic
- educational games
- nash equilibrium
- integer programming
- worst case
- constraint satisfaction problems
- closely related
- search algorithm
- stochastic games
- learning games
- false matches
- boolean variables