JSoko Solver
From Sokoban Wiki
(First few words to describe the JSoko solver) |
(→Search algorithm) |
||
| (6 intermediate revisions not shown) | |||
| Line 20: | Line 20: | ||
=== Search algorithm === | === Search algorithm === | ||
The main search is an A* search. The solver only uses forward searching. | The main search is an A* search. The solver only uses forward searching. | ||
| - | However, if the level is considered a ''goal room level'' then a packing order algorithm calculates a packing | + | However, if the level is considered a ''goal room level'' then a packing order algorithm calculates a packing sequence for filling the goals first. |
| - | + | ||
=== Heuristic score === | === Heuristic score === | ||
| Line 35: | Line 34: | ||
=== Deadlock detection === | === Deadlock detection === | ||
JSoko can detect all deadlocks described in the [[Deadlocks]] article. | JSoko can detect all deadlocks described in the [[Deadlocks]] article. | ||
| + | Neither a precalculation of deadlocks nor a deadlock database is used. | ||
=== PI-Corral pruning === | === PI-Corral pruning === | ||
The solver uses the PI-Corral pruning developed by Brian Damgaard and me to reduce the search tree. | The solver uses the PI-Corral pruning developed by Brian Damgaard and me to reduce the search tree. | ||
| + | |||
| + | |||
| + | === Packing sequence === | ||
| + | A packing sequence is calculated for some levels:<br> | ||
| + | The solver counts the "connected goals". The definition of "connected goal" is: | ||
| + | #The goal has one or more neighboring goals | ||
| + | #When the neighboring goal is located at one axis, there must be a neighboring position along the other axis, which either is a goal too, or a wall | ||
| + | <br> | ||
| + | If the number of connected goals is higher than 8 the level is classified as packing sequence level. | ||
| + | <br> | ||
| + | The packing sequence is calculated by performing a backward search:<br> | ||
| + | all boxes are placed on goals and the search tries to remove one box at a time. | ||
| + | The box positions at the start of the level are considered ''backward goals'' during the search.<br> | ||
| + | If a box can be pulled to a backward goal then it is removed from the board.<br> | ||
| + | If none of the boxes can be pulled to any backward goal anymore the boxes are pulled one position to any direction and then it's checked again if any of the boxes can now reach a backward goal.<br> | ||
| + | if all boxes have reached a goal then a packing sequence has been found.<br> | ||
| + | This push sequence is then used by the forward search to push the boxes to the goals. | ||
Current revision as of 23:27, 28 January 2017
JSoko solver
This article is a technical description of my solver.
The JSoko solver is part of my program JSoko.
It's written in Java. The source code is available as the whole JSoko project is open source.
Contents |
Limits of the solver
The solver inherits the limits of JSoko.
This means in can only be used for levels not larger than 70*70 squares.
The solver only tries to find any solution regardless of the number of moves or pushes needed to solve the level.
The solver can only be used as part of JSoko, since there is no stand-alone version.
JSoko overall structure
Search algorithm
The main search is an A* search. The solver only uses forward searching. However, if the level is considered a goal room level then a packing order algorithm calculates a packing sequence for filling the goals first.
Heuristic score
The A* search calculates the minimum perfect bipartite matching of the boxes' distances to the goals after every push. This pushes lower bound is enhanced by adding a penalty for simple linear conflicts.
Transposition table
All board positions are stored in a hash table. The player player is normalized to the top-left position reachable in the current board position before the board positions are stored in the hash table.
Deadlock detection
JSoko can detect all deadlocks described in the Deadlocks article. Neither a precalculation of deadlocks nor a deadlock database is used.
PI-Corral pruning
The solver uses the PI-Corral pruning developed by Brian Damgaard and me to reduce the search tree.
Packing sequence
A packing sequence is calculated for some levels:
The solver counts the "connected goals". The definition of "connected goal" is:
- The goal has one or more neighboring goals
- When the neighboring goal is located at one axis, there must be a neighboring position along the other axis, which either is a goal too, or a wall
If the number of connected goals is higher than 8 the level is classified as packing sequence level.
The packing sequence is calculated by performing a backward search:
all boxes are placed on goals and the search tries to remove one box at a time.
The box positions at the start of the level are considered backward goals during the search.
If a box can be pulled to a backward goal then it is removed from the board.
If none of the boxes can be pulled to any backward goal anymore the boxes are pulled one position to any direction and then it's checked again if any of the boxes can now reach a backward goal.
if all boxes have reached a goal then a packing sequence has been found.
This push sequence is then used by the forward search to push the boxes to the goals.
