How the JSoko optimizer works

This article technical describes how the optimizer in JSoko works.

 

Understanding the inner workings of the optimizer may help to set better vicinity settings for optimizing a solution.

 

An optimizer tries to improve a given solution regarding moves and pushes.

In contrast to a solver, an optimizer has the advantage of already having a solution for the level so it just has to improve that solution.

 

A simple approach for searching for a better solution is a standard shortest path search that searches from the start board position to an end board position.

However, this isn't feasible for any but the very smallest levels.

 

Hence, the optimizer performs a "Local Search".

 

Local (neighborhood) searches take a solution to a problem and check its immediate neighbors (that is, solutions that are similar except for very few minor details) in the hope of finding an improved solution.

 

The local search in the JSoko optimizer is performed in two main steps:

  1. Generate neighbor box configurations
  2. Perform a standard shortest path search

A "box configuration" is simply a word for the positions of all boxes.  

Step 1: Generating neighbor box configurations

In step 1 the "neighborhood" of the solution is generated.

 

A solution containing 100 pushes is split into 101 box configurations, that is: the initial box configuration and the 100 box configurations after doing each of the box pushes.

 

Then the optimizer generates further box configurations by taking each box configuration of the solution and relocating some of the boxes.

 

Example level:

In this level the box is pushed along the marked squares to the goal to solve the level.

 

When the JSoko optimizer is started with a "vicinity setting of 4":

it will place a box at every position along the shown path and generate a neighborhood by repositioning the box from each square to one of the 4 nearest neighbor positions.

 

That means for the start box position it will reposition the box to every of the marked squares:

This is done for all positions the box is pushed to in the solution, that is: for all box configurations of the solution.
Hence, the box will be relocated to all these squares and for each of them a new box configuration will be saved:

Now the optimizer has finished step 1 since all box configurations of the "neighborhood" have been generated.

Step 2: Searching the best new solution

In this step the optimiizer performs a standard "shortest path" algorithm that searches the shortest path for the box to the goal WHILE ONLY VISITING ONE OF THE BOX CONFIGURATIONS GENERATED IN STEP 1.

In this example this means the box is only allowed to be pushed to any of the marked squares.

 

With the restriction of only visiting marked squares this means we "stay in the neighborhood of the initial solution".

 

In this example level and having a vicinity setting of 4, the optimizer finds the best possible solution while only pushing the box to the marked squares, that is the solution resulting in pushing the box along the red surrounded squares:

The optimizer can't find the best solution, that is: just pushing the box 5 times to the right because thta solution path is too far away from the initial solution. 

 

There are two possible solutions for this problem:

  • start the optimizer again with the new better found solutions => iterative optimizing
  • start the optimizer with higher vicinity settings like 20 instead of 4

Examples

This is an example level having two walls:

The whole solution used for optimizing is this: ruLdlUUUluRurrdrR

 

This means the first box is pushed around the wall on the left side.

 

This isn't optimal since the next box to be pushed is at the right side of the player now:

The player now has to walk around that box with causes extra moves.

 

When the optimizer generates a neighborhood (with again 4 neighbors as setting) these are the marked squares:
You can see that the optimizer won't find a better solution with a setting of 4, since not all squares at the right side of the walls have been marked.

Implementation details

When two boxes, both with a vicinity setting of 10, are used for optimizing a solution:
then in the current implementation this also allows one box to be repositioned 20 positions away from its current position.

The reason is that the generator is allowed to reposition the same box twice: 10 squares and then again 10 squares.

 

Another domain specific implementation detail is: when a neighbor is a simple deadlock, then in JSoko the square doesn't count as neighbor which results in another neighbor to be taken for repositioning.

In general using higher vicinity settings results in better optimier results, that is: shorter solutions.

However, this also means that the optimizer needs more time and memory.

 

Depending on the level it may be better to use only 1 box for repositioning but a high vicinity squares number like 999:

which means only one box is repositioned to any of its nearest 999 neighbor squares at a time,

or to use two boxes with a lower vicinity number:

Example level with 4 vicinity boxes

This is a level having 5 boxes:

This is a solution having 29 pushes:

 

Solution 34/29

lLLLLLLLLLLLLLLulldRRRRRRRRRRRRRRR

 

In this solution the box is pushed all the way to the left and then back to the goal resulting in the 29 pushes solution.

 

Now we like to use the optimizer to optimize the solution for pushes.

 

Now that we know how the optimizer works,

it may be easier to understand why this level is problematic for the optimizer.

 

Let's say we use 3 boxes for optimizing, each being allowed to be repositioned to any of the nearest 999 neighbors, which in fact means: each box may be repositioned to any other square in the level:

Will the optimizer find a better pushes solution?

 

The answer is no, because in order to find the better pushes solution the optimizer had to push four boxes differently at the same time.

 

In this small example level it's obvious that the lower box can only be pushed to the right immediately when all 4 other boxes are pushed down first.

However, in the original solution none of those boxes is pushed down.

 

That means: in order to find the better pushes solution the optimizer has to push all four boxes "differently" at the same time.

 

However, we have only allowed the optimizer to push 3 boxes differently at the same time since only 3 boxes may be repositioned at the same time.

 

 

This little example level shows that the optimizer has problems optimizing a solution when a lot of boxes have to be pushed differently at the same time.

In such cases it's a good idea to search for a "different" solution oneself and then optimizing that new solution instead.