KlickKlacker 2 Solver

The general idea of this game is that areas that are connected by having the same color are removable, and the objective is to remove areas in a strategic way until no further moves are possible. Cells will fall down if there is empty space below them and will be pushed together if there are empty columns. The game ends if there are no possible moves or if all the cells are gone.

My idea was to write a solver that builds a game tree where each leaf contains the final score from making a particular sequence of moves. As one quickly realizes there is a huge number of possible solutions. In order to speed things up, pruning of the game tree can be deployed. However, it is very likely (although unproven for this particular problem, but proven for similar but simpler problems) that the problem of optimally solving this game is NP-complete. This means that pruning won’t really help, because all leaves have to be visited in order to guarantee an optimal solution. However, a few obviously strategically flawed paths can be skipped. As with most pruning, evaluation functions must trade greediness and speed for optimal solutions.

A more failsafe optimization would be to implement a transposition table, because it is likely that by following different sequences of moves (in some cases simply changing the order of the moves) we arrive at the same game position, albeit with a different score. However, this involves checking for existens of a game position before solving at each node. This requires a fast hash-function for computing unique ID’s for game positions, which is non-trivial to design. In these cases we can terminate the paths where the same position was achieved with a lower score.

Currently, I can solve small grids (5×5) using a brute force approach. I also have a playable version of the game, for verifying the suggested moves (and for fun). The solver and the game are built on the same core-library developed by me.

Images