Matthias Meger: /* Search algorithm */

2017-01-28T23:27:16Z

Search algorithm

New page

'''JSoko solver'''

----

This article is a technical description of my solver.

The JSoko solver is part of my program [http://www.sokoban-online.de JSoko].

It's written in Java. The source code is available as the whole JSoko project is open source.

== Limits of the solver ==
The solver inherits the [[Feature_list_:_General_Information#Limits|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.

JSoko Solver - Revision history

Matthias Meger: /* Search algorithm */