"Bloq" is a simple but extremely challenging puzzle game.
Swipe blocks into empty spaces and connect blocks of the same color to make them disappear. You must clear the board in as few moves as possible.
Think you have what it takes to finish the game?
The game works like this: you start with a 4x4 grid of four colors and one open space. The goal is to slide blocks into empty spaces, and when two colors are touching, those blocks will disappear. You must clear the board in the minimum number of moves possible.
The AI, which can solve any configuration in the minimum number of moves (or tell you if a solution is impossible), deserves its own explanation.
I originally wrote the algorithm in Swift, but this took waaaay too long to solve games (Swift has a lot of overhead in its String class, and I was using Strings to represent game states). Since Objective-C and Swift are built off of C, and C is lightning fast, I ended up writing the algorithm in C.
If the Swift code requests a solution, it will convert the game board to a string (16 cells in the game → string of length 16 with ‘R’, ‘B’, ‘O’, ‘G’ or ‘.’ to represent blocks/blanks). This string is then passed to the C game-solver.
The AI considers all possible moves from a given state, and the resulting game state after each of those moves. The game is effectively played out thousands of thousands of ways, progressing using a breadth-first search (BFS). Think of a program which analyzes the best move to make in a Chess game, and it’s similar to that.
Once the BFS recognizes that it has an empty board, it stops. Due to the nature of BFS, the first blank board encountered is automatically reached in the minimum number of moves. Now another challenge: figuring out how to go backwards to find the moves made to get to the solution. This was accomplished using a Hashmap of preceding moves from a given move.
To create the 300 levels and 3 difficulty settings, I randomly generated boards and ran the algorithm on each board. With a list of each board and the minimum number of moves to solve it, I was able to sort the boards based on their minimum number of moves and classify them as “Easy” (7-8 moves), “Medium” (9-10 moves), or “Hard” (11+ moves). The app pulls from this list to generate the next board when you move to the next level:
There is another aspect to the AI as well, a preloaded table of common game boards and their solutions. This is loaded into the app as a Hashmap when it starts up, using a game state string representation as the key and a solution as the value:
The lookup table reduces the probability of the AI having to calculate a solution on-the-fly (although it can do this if no entry is found in the Hashmap), thereby improving user experience.
The ability to execute C code in this iPhone app is overall a somewhat interesting topic, and I'm sure there are more (malicious?) uses of embedding C in iOS.