Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard.
Luciano GualàStefano LeucciEmanuele NatalePublished in: CoRR (2014)
Keyphrases
- np hard
- approximation algorithms
- optimal solution
- scheduling problem
- computer games
- integer programming
- special case
- closely related
- remains np hard
- np hardness
- game theoretic
- decision problems
- learning agents
- nash equilibria
- game theory
- np complete
- video games
- minimum cost
- nash equilibrium
- game design
- weighted majority
- lower bound
- worst case
- computationally hard
- educational games
- neural network
- board game
- reinforcement learning
- perfect information
- coalitional games
- game tree search
- data sets
- approximation ratio
- game development
- digital games
- objective function
- cooperative
- knapsack problem
- branch and bound algorithm
- linear programming