6 Sokoban

8.12

6 Sokoban🔗ℹ

Sokoban is a puzzle game in which the player must push crates around a warehouse, trying to put them in storage locations. It was created in 1981 and has since found a home in the AI research community as a useful problem domain for testing automated planners.

The Sokoban world is a rectangular grid containing walls, crates, a player, and storage locations. The goal is to push the crates to the storage locations. The player can move around the world and push crates up, down, left, and right, but only if the crate isn’t blocked by a wall or another crate.

Examples:

(define state
  (sokoban-level (space 1 1) player
                 (space 2 2) crate
                 (space 3 3) storage-location
                 #:width 5
                 #:height 5))
(define problem
  (hash-planning-problem
   #:state state
   #:actions (sokoban-possible-actions state)
   #:goal sokoban-goal))

> (hash-visualize-plan! problem #:draw-state-with sokoban-pict)

procedure
(space? v) → boolean?
v : any/c

A predicate for grid spaces in a Sokoban level. A space is a pair of an X coordinate and a Y coordinate.

procedure
(space x y) → space?
x : natural?
y : natural?

Constructs a grid space with x and y coordinates. The origin (space 0 0) represents the top left corner of a Sokoban level.

procedure
(space-x s) → natural?
s : space?
procedure
(space-y s) → natural?
s : space?

Returns the X and Y coordinates of s, respectively.

procedure
(sokoban-object? v) → boolean?
v : any/c

A predicate for objects in the Sokoban world.

value
wall : sokoban-object?
value
player : sokoban-object?
value
crate : sokoban-object?
value
storage-location : sokoban-object?
value
player-in-storage : sokoban-object?
value
crate-in-storage : sokoban-object?

The various objects that can exist in a Sokoban level. The player-in-storage and crate-in-storage objects are like the player and crate objects, except they represent cases where the player or crate is standing on top of a storage location space. Distinct objects for these cases are necessary because the Sokoban world uses the hash state representation, so a single space cannot contain multiple objects.

procedure
(sokoban-level s
object ...
...
#:width width
#:height height)
→ (hash/c space? sokoban-object?)
  s : space?
  object : sokoban-object?
  width : exact-positive-integer?
  height : exact-positive-integer?

Constructs a hash table representing a Sokoban level with dimensions of width and height. In addition to each of the space-object pairs specified by the s and object arguments, walls are placed on the edges of the level.

Example:

> (sokoban-pict
   (sokoban-level (space 1 1) player
                  (space 1 3) wall
                  (space 2 3) wall
                  (space 2 2) crate
                  (space 3 5) storage-location
                  (space 2 4) crate
                  (space 1 4) storage-location
                  #:width 5
                  #:height 7))

procedure
(sokoban-applicable-actions state) → (set/c hash-action?)
state : (hash/c space? sokoban-object?)

Constructs a set of all actions that are applicable in state.

Examples:

(define state
  (sokoban-level (space 1 1) player
                 (space 2 2) crate
                 (space 3 2) storage-location
                 #:width 5
                 #:height 4))

> (sokoban-pict state)
> (set-count (sokoban-applicable-actions state))
2

procedure
(sokoban-possible-actions initial-state) → (set/c hash-action?)
initial-state : (hash/c space? sokoban-object?)

Constructs a set of all possible actions that could be performed over the course of a Sokoban game starting from initial-state. This includes actions that are not mmediately applicable, but which can be applied if other actions are performed first.

The set of possible actions returned is an optimistic estimate. Every possible action is returned, but some impossible actions may also be returned. An estimate is returned because computing the exact set of possible actions can be complex and prohibitively expensive.

Examples:

(define state
  (sokoban-level (space 1 1) player
                 (space 2 2) crate
                 (space 3 2) storage-location
                 #:width 5
                 #:height 4))

> (sokoban-pict state)
> (set-count (sokoban-possible-actions state))
480

value
sokoban-goal : hash-goal?
= (hash-goal #:obstructing-values (set crate))

The goal of every Sokoban level is the same: push every crate into storage. Because pushing a crate into a storage location changes it into a crate-in-storage, this means that all that’s required to win is for the Sokoban level’s hash table to not contain any crate values.

procedure
(sokoban-pict state) → pict?
state : (hash/c space? sokoban-object?)

Draws a picture of state.

Example:

> (sokoban-pict
   (sokoban-level (space 1 1) player
                  (space 2 4) crate
                  (space 4 2) crate
                  (space 1 5) storage-location
                  (space 5 4) storage-location
                  #:width 7
                  #:height 7))

1	Overview
2	The Set State Representation
3	The Multiset State Representation
4	The Hash State Representation
5	Phase Transitions
6	Sokoban