Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver
From Sokoban Wiki
"Scribbles" about Sokoban solver programming by Florent Diedler, in particular about the Sokolution solver.
Sokolution overall structure
Sokolution is written in C++, use STL library / C++14 concepts and build with MinGW 5.1 under WIndows 7 / 10. I choose C++ because it is a low-level language really fast and we can have the full control of the memory thanks to pointers.
The only limit for my solver is the number of floor squares for a given level. Sokolution can solve *only* levels wih less than 256 floor squares (walls does not count). This implies that the maximum number of boxes is 255. Then, Sokolution can solve levels up to 100 for width and 100 for height. I choose this compromise because it is a limitation of bitsets, a binary structure in C++. It also allows to store all positions in only one byte and that is great for the memory.
Sokolution is compatible with host programs like Sokoban++ or YASC. The plugin version is just a DLL file that we need to place in the "Plugin" folder of the host program. There is no external dependencies.
Sokolution is the best solver because everything is really optimized in memory and for speed. It took for me almost one year to profile and optimize all bottlenecks. All areas are "binarized" that means each square is represented as a bit in memory. Because I use one byte to store the player position, the position can only vary from 0 to 255 included. This is the main drawback of my solver but that seems worthwhile.
Search algorithms
Sokolution can use several algorithms according to your needs :
- Optimal algorithms : BFS, IDDFS, A* and IDA
- Non-optimal algorithms : Greedy, DFS
Each algorithm can use the FORWARD mode or the BACKWARD mode and some special modes can be used.
The forward mode consists to start from the initial state and try to find a sequence of pushes to put all boxes on goals. This is the natural mode for solving Sokoban problems.
The backward mode is the opposite of the forward mode. We start from the solution (all boxes are on goals) and we pull boxes in order to find the initial position. Note that the final player position should be able to reach its initial position.
The bidirectional mode is a combination of forward and backward modes. A thread will perform a forward search and another thread will perform the backward search. There is no check when the two searches overlaps.
By default, Sokolution uses a bidirectional search with greedy algorithm in both side. This is the best combination for finding a solution quickly.
If you want to find optimal solutions, use a bidirectional search with A* algorithm in both side.
Heuristic score
All algorithms that needs an heuristic use the bipartite matching. It is a long computation that uses the Hungarian algorithm in O(n^4) in time complexity. The Hunguarian has been modified a bit in order to be optimized in O(n^3).
For solving sublevels, the heuristic uses the nearest goal for each box and it is really fast.
Heuristic update
Assuming that the basic heuristic is enough for solving a Sokoban level is an error. Even if we use a really accurate method the find a perfect bi-partite matching between boxes and goals, there are lots of situations where the basic heuristic is not sufficient. The basic heuristic is defined as the heuristic that takes no other boxes into account.
During the main search, we will find new frozen boxes on goals (otherwise it is a deadlock). Sometimes, these areas may change the heuristic score and affect the reachability of unfilled goals. To solve this problem, I recompute the heuristic after finding a frozen area. It is a long computation and we have to be smart to optimize this computation.
With this enhancement, just computing the heuristic score can lead to detect new deadlocks due to a goal that is no more accessible. It helps a lot when we have no goal ordering available.
Transposition table and hash function
A custom transposition table is created specialy for the solver. It is an open-addressing hashtable with linear probing. The memory is fully controled in order to set a memory limit for this solver without the risk of having an overflow memory.
After having implement plenty of hash functions, I finally use the default hash function for bitset and I do a XOR with the player normalized position.
Open queue
Depending of the algorithm choosen, the open queue can be :
- FIFO queue for BFS
- LIFO stack for DFS and IDDFS
- Priority queue for Greedy, A* and IDA
The tie-breaking for the priority queue is :
- If a F-cost is defined, sort by minimum F-cost
- If a H-cost is defined, sort by minimum H-cost
- For same F or H costs, sort by newest node first
NB : F-cost is defined as the sum of G-cost and H-cost (F = G + H)
Goal room packing
Contrary to YASS solver, Sokolution does not use a "goal room packing" method. So it is impossible to solve XSokoban #50, XSokoban #66 and Xsokoban #69 levels that needed these powerful algorithms. I think YASS shines in this domain.
However, Sokolution has an algorithm to find goal room when there is a single entrance (like many of XSokoban levels). If we are able to find an order of filling goal without created deadlocks, Sokolution will create macro moves to respect the ordering of the goal area. This mechanism speed up a lot levels with a "goal room theme".
Goal partial ordering
I think it is a real improvement for finding a non-optimal solution. It is quite impossible to guarantee optimality with a pre-calculated partial goal ordering.
The aims is to find a subset of goals that we should always ordered before other goals. This subset of goals need also to be filled in a particular order.
