Want better solvers ?

Info

 

 

 

 

 

 

 

            Here you can find extra information about moves, rules, properties and technical info.

 

 Rules :

 

            Telling a rule to a computer is not easy. As every game, Sokoban has some rules too.

 

            - First degree rules are so simple ;

 

               . Sokoban can move up,down,left and right,

               . Sokoban can't pass through walls,

               . If Sokoban wants to move towards a block it tries to push it,

               . If a block has a wall or another block in pushing direction, Sokoban cannot move it,

               . Every block should be pushed onto a target zone.

 

            These rules can be satisfied easily. But with these rules, some properties make finding solution extremely hard. Some of these properties are ;

 

               . Algorithm that finds solution is unknown. (Like Chess)

               . Order of pushing blocks and its direction are unknown.

               . In How many depth that there is a solution, is unknown.

 

            But a method to find a solution can be found. SPS uses combination method (v2.0 - Generate and Test Approach, v3.0 - Bidirectional Generate and Test Approach -- Generating and Testing with strategy of Breadth-First search algorithm). Combination method is simply calculating possible moves for current position and pushing them into a queue (A stack can be used but it will find first solution, not shortest solution). A pushed entry is popped and method loops. But needed storing device space for storing and evaluating such a queue, is not acceptable. Because probably, space and time will not be enough to reach a solution since a solution does not come in few moves (depths). It is impossible to apply such a method in a simple computer environment.

 

            Only way is to ignore some of moves. I call the ignored moves as 'bad move'.

             Ignore operation contains simple steps :

 

               . Ignore repeated moves.

               . Ignore impossible moves. (Impossible moves are moves that will lead no solution)

 

            SPS has an ignoring repeated moves system (using binary tree). In Sokoban game, repeated moves are a lot when we look at combinations. For example, a position in 9th depth, can be exactly same as a position in 3th depth. In this situation, there is no meaning for looking combinations of the position in 9th depth. Because that situation is already reached in 3th depth.

This system eliminates most of the combinations. For example if the number of all combinations in 70th depth is 1.39 x 10 42, the number of unrepeated moves is only about 8 million (70th depth). Now it seems possible to apply it in a simple computer environment. But this is not enough. Because computer calculates much more moves to in this method to reach 70th depth. There is an example for understanding that clearly :

 

            1st move : There is 4 unrepeated moves

            2nd move : There is 3 unrepeated moves for each 4 moves in 1st move. (4x3 = 12 unrepeated)

            3rd move : There is 3 unrepeated moves for each 12 moves in 2nd move. (12x3 = 36 unrepeated)

            4th move : There is 3 unrepeated moves for each 36 moves in 3rd move. (36x3 = 108 unrepeated)

              ..  ...   ...   ..

            69th move : There is 2 unrepeated moves for each move in 68th move, that is 4 million total.

            70th move : There is 2 unrepeated moves for each 4 million move in 69th move, that is 8 million total.

 

Now the number of the all moves is : 4 +12 + 36 + 108 + .... + 4 million + 8 million

It is possible to calculate all of the moves but it will take MUCH time.

 

            We should also ignore impossible moves. SPS has an ignoring impossible moves system too. After elimination of the moves, a simple maze that requires 1.39 x 10 42 moves, will only require a few thousand moves (that takes just 3 secs or so)

Since those ignoring operations have not simple algorithms, computer wastes much time to identify if a move is a bad move. Algorithms contain lots of big loops and arithmatic operations and take time due to number of blocks and wideness of movable area.

 

Impossible moves constitute Second Degree Rules. (Simply don't do impossible moves). If any of blocks or any group of blocks are in impossible (no solution) position then there's no need to calculate any combination unless they are all on targets.

 

 Impossible moves :

 

            Blocked moves : They are non-movable block moves. Some examples of blocked moves :

 

This is a famous blocked move. Two blocks, block each other and wall blocks from 1 side. Nothing to do.

The block is blocked from 2 sides by walls.

All of the objects block each other. If we could remove one of them, This wouldn't be a blocked move.

There is no blocking wall, but 4 blocks, block each other.

 

            Trapped Moves : They are movable block moves but it leads no solution anyway. For not to ignore a trapped move, Trapped block must have a target zone on its way. Some examples of trapped moves :

 

Here, the block beside the wall is trapped. Wherever it is pushed, It can't be pushed onto targets.

The bridge, beside blocks is fallen. Sokoban cannot get in bridge to push the block to targets. So blocks are in trap.

In this position, blocks cannot be pushed onto targets. They are in trap.

Block is in 'out of nowhere' position. It's in big trap.

 

 Some technical terms :

 

            LAB File : Labyrinth file, contains data of maze and blocks

            Evaluated Move : A move that may lead a solution.

            Scanned Move : A move that has been searched for new combinations or solution out of evaluated moves.

            Total Scanned Move : Number of all combinations including bad moves,repeated moves.

            Bad Move : A move that leads no solution.