Algorithm for puzzle game

Question

I am new in this community. I'd like to create an algorithm to solve puzzle games, for example I tried to start with Fish Fillets (see this, this and this for "How to play"). As you can see in the third site I mentioned, the main goal for the most of the levels is find a safe exit for two fishes and in such room the fishes have to find a safe exit for a special object. My algorithm must find the minimum number of moves needed to complete each level. I'd like to improve my very bad algorithm, that follows below

Algorithm:

1. In almost every level the first possible moves are 8, so 8 is the initial worst case. So, let's say $\mu_1$ is the first generic possible initial move, and create a tree that has mu_1 as its source.

2. Now it's as if we had a new level to solve in which the initial configuration is slightly modified, so we apply the algorithm recursively.

3. If a certain stratification of the tree, be it $\sigma$, makes it impossible to continue the level, the string "$\mu_1 \mu_{1i_1} \ldots \mu_{1i_k}$" must return FALSE, so we get a well. Furthermore, if every subtree coming out of $\sigma$ leads to a well, we say that $\sigma$ leads to a well and every string containing a move of $\sigma$ the algorithm must return FALSE, and so on.

4. If the algorithm reports that the first initial move was not $\mu_1$ but another, be it $\mu_i$, for such $i$, we say that $\mu_1$ leads to at least one well and therefore we repeat the algorithm for $\mu_i$ until all possible initial moves are exhausted.

5. Each level has already been solved with a certain number of moves. Considering the minimum found so far (see the first two sites), if the algorithm reports that the best known solution cannot be improved, then it must return TRUE, otherwise FALSE and in both cases it must also return the string of the best solution.

6. The algorithm terminates when all levels are solved.

Remark: The complexity of my algorithm is exponential, of the type 8ドル\cdot7^n$ and in the longest level, the algorithm would terminate after 5ドル.148\cdot10^{1643}$ years and in the shortest after 5ドル.534\cdot10^{18}$ years.

So I would need an algorithm that finds a time-efficient strategy to solve each level returning TRUE/FALSE and the strings containing the best solutions.

Thank you in advance Best regards PUCK

• Pseudonym: Just as a general comment, any puzzle game that involves movement towards a goal has a heuristic that is "safe" for $A^*$ search, namely the sum of the distances (presumably Manhattan distance in this case) of every object from its ultimate goal. This is especially effective if there are a lot of objects, such as the 16 puzzle. If there are mandatory "waypoints", incorporating that into the heuristic in a safe way is not difficult.
• D.W.: We need questions here to be self-contained. Unfortunately I don't think this question is answerable with only the information in the question itself.

Answer 1

As far as I understand rules, this game have much in common with Sokoban. Therefore the decision version of this problem is likely to be $\mathrm {NP}$-hard. It means that you are unlikely to find a polynomial algorithm and the development of an efficient exponential algorithm with provable time bounds would take much effort. So I can give you some basic recommendations which may give a better practical performance.

1. As far as I see by your time bound you already use the idea that a new move shouldn't roll back to the previous position. However you should take into account that moving a fish back makes sense if its previous movement shifted some block.
2. As @Pseudonym said in comments you may cut bad branches using trivial lower bound like sum of Manhattan distances to nearest exist for both fishes.
3. If two moves may be swapped, define the only allowed order. For example if both "up and left" and "left and up" are possible and don't push any block or push it to the same position then only the first is allowed. Or if both fishes should and can move then the first fish moves first.
4. You may additionally forbid short cycles like "up-left-down-right" returning to the same position, but this is the least promising optimization. For this purpose you may remember all visited positions or its hashes, but only for the current path from the root. It means that after returning from recursive call you need to remove corresponding position from memory. (If you try to remember the answers for all positions in all branches it could give much better performance, but requires exponential memory.) Note that this trick generalizes the 1st trick and makes it useless.

Every of this simple tricks reduces real number of visited branches exponentially. You may think about other optimizations that allow to avoid getting into the same position twice or allow to avoid considering useless positions. Just implement and play with these and other possible optimizations. It makes sense to create own smaller levels to estimate the performance of your algorithm and see how changes.

Also for solving big levels somehow it could make sense to find not the best possible, but at least some solution. However I don't see any heuristic that have any guarantee to find a solution.