{"id":76,"date":"2022-01-19T04:36:55","date_gmt":"2022-01-19T04:36:55","guid":{"rendered":"https:\/\/timallanwheeler.com\/blog\/?p=76"},"modified":"2022-07-22T02:48:30","modified_gmt":"2022-07-22T02:48:30","slug":"basic-search-algorithms-on-sokoban","status":"publish","type":"post","link":"https:\/\/timallanwheeler.com\/blog\/2022\/01\/19\/basic-search-algorithms-on-sokoban\/","title":{"rendered":"Basic Search Algorithms on Sokoban"},"content":{"rendered":"\n

Sokoban – the basic block-pushing puzzle – has been on my mind off and on for several years now. Readers of my old blog know that I was working on a block-pushing video game<\/a> for a short while back in 2012. John Blow, creator of The Witness, later announced that his next new game would draw a lot from Sokoban (In 2017? I don’t remember exactly). Back in 2018, when we were wrapping up Algorithms for Optimization<\/a> and I started thinking about Algorithms for Decision Making<\/a>, I had looked up some of the literature on Sokoban and learned about it more earnestly. <\/p>\n\n\n

\n
\"\"
Mystic Dave pushing a block<\/figcaption><\/figure>\n<\/div>\n\n\n

At that time I stumbled upon Solving Sokoban by Timo Virkkala<\/a>, a great Master’s Thesis that covers the basics of the game and the basics used by many solvers. The thesis serves as a great background for search in general, that is, whenever one wants to find the best sequence of deterministic transitions to some goal state. While search problems are not front and center in Algorithms for Decision Making, I did end up writing an appendix chapter on them<\/a>, and looking back on it see how well comparatively the thesis covers the space.<\/p>\n\n\n\n

I started work at Volley Automation<\/a> in January of 2021, a startup working on fully automated parking garages. I am responsible for the scheduler, which is the centralized planner that orchestrates all garage operations. While the solo pushing of blocks in Sokoban is not quite the same as simultaneously moving multiple robots under trays and having them lift them up, the problems are fairly related. This renewed my interest in Sokoban, and I spent a fair amount of free time looking into solvers.<\/p>\n\n\n\n

Early in my investigation, I downloaded an implementation of YASS (Yet Another Sokoban Solver)<\/a>, a 27538-line Pascal program principally written by Brian Damgaard, which I found via the Sokoban wiki<\/a>. I had heard that this solver could solve the “XSokoban #50” level in under a second, and had found the wiki overview and the code, so felt it was a good place to dive in. After trying to translate the Pascal code into Julia directly, I both determined that the languages are sufficiently different that this was not really possible (Pascal, for example, has a construct similar to a C union, which Julia does not have), and that it also ultimately wasn’t what I wanted to get out of the exercise. I did learn a lot about Pascal and about efficient Sokoban solving from the code base, and ended up translating the overall gist of many algorithms in order to learn how Goal room packing<\/a> works. <\/p>\n\n\n\n

Before I fleshed out YASS’s goal room packing algorithm, I needed a good baseline and a way to verify that my Sokoban game code was correct. As such, I naturally started by writing some of the very basic search algorithms from my search appendix chapter. This post will cover these search algorithms and concretely show how they progressively improve on each other Sokoban problems of increasing complexity. It was really stark to see how the additions in each new algorithm causes order-of-magnitude changes in solver capability. As always, code is here.<\/a><\/span><\/strong><\/p>\n\n\n\n

Sokoban Basics<\/h2>\n\n\n\n

Sokoban is a search problem where a player is on a grid and needs to push some number of boxes to an equal number of goal tiles. The player can move north, south, east, or west, provided that they do not run into a wall or box tile. A player may push a box by moving into its space, provided that the box can move into the next space over. A simple 2-box Sokoban game and solution are shown below:<\/p>\n\n\n

\n
\"\"
The red star indicates the player position, boxes are green when not on goals, and blue when on goals. The dark tiles are walls.<\/figcaption><\/figure>\n<\/div>\n\n\n

While the action space is technically the set of legal north\/south\/east\/west player moves, it is more efficient to reason about push moves instead. That is, search algorithms will consider the pushes available from the player’s current position. This simplification yields massive speedups without losing much in terms of practicality. If a push is chosen, we can back out the minimum number of player moves to achieve the push by simply using a shortest-path solver. <\/p>\n\n\n\n

\"\"
Player move vs. box push problem formulations. Reasoning with a coarser representation has big performance implications.<\/figcaption><\/figure>\n\n\n\n

A push-optimal solution may not be player move optimal – for example it may alternate between pushing two different boxes that the player has to traverse between – but it is nevertheless well worth reasoning about push moves. Here is the push-move solution for the same simple 2-box problem:<\/p>\n\n\n

\n
\"\"<\/figure>\n<\/div>\n\n\n

Sokoban is made tricky by the fact that there are deadlocks. We cannot push a box that ends up in a corner, for example. It is not always obvious when one has reached a state from which deadlock is inevitable. A big concern in most Sokoban solvers is figuring out how to efficiently disregard such parts of the search tree.<\/p>\n\n\n\n

Problem Representation<\/h2>\n\n\n\n

A search problem is defined by a state space, an action space, a transition function, and a reward function. Sokoban falls into the category of shortest path problems, which are search problems that simply penalize each step and yield zero reward once a destination state is reached. As such, we are searching for the smallest number of steps to reach a goal state.<\/p>\n\n\n\n

The board here has both static and dynamic elements. The presents of walls or goals, for example, does not change as the player moves. This unchanging information, including some precomputed values, are stored in a Game<\/code> struct:<\/p>\n\n\n\n

struct Game\n    board_height::Int32\n    board_width::Int32\n    board::Board # The original board used for solving, \n                 # (which has some precomputation \/ modification in the tile bit fields)\n                 # Is of length (Width+2)*(Height+2); the extra 2 is for a wall-filled border\n    start_player_tile::TileIndex\n    goals::Vector{TileIndex} # The goal tiles do not change\n    # \u25a1 + step_fore[dir] gives the tile one step in the given direction from \u25a1\n    step_fore::SVector{N_DIRS, TileIndex}\n    # \u25a1 + step_left[dir] is the same as \u25a1 + step_fore[rot_left(dir)]\n    step_left::SVector{N_DIRS, TileIndex} \n    # \u25a1 + step_right[dir] is the same as \u25a1 + step_fore[rot_right(dir)]\n    step_right::SVector{N_DIRS, TileIndex} \nend<\/pre>\n\n\n\n
where TileIndex<\/code> is just an Int32 index into a flat Board<\/code> array of tiles. That is,<\/p>\n\n\n\n
const TileIndex = Int32 # The index of a tile on the board - i.e. a position on the board\nconst TileValue = UInt32 # The contents of a board square\nconst Board = Vector{TileValue} # Of length (Width+2)*(Height+2)<\/pre>\n\n\n\n
The 2D board is thus represented as a 1D array of tiles. Each tile is a bit field whose flags can be set to indicate various properties. The basic ones, as you’d expect, are:<\/p>\n\n\n\n
const BOX                     = one(TileValue)<<0\nconst FLOOR                   = one(TileValue)<<1\nconst GOAL                    = one(TileValue)<<2\nconst PLAYER                  = one(TileValue)<<3\nconst WALL                    = one(TileValue)<<4<\/pre>\n\n\n\n
I represented the dynamic state, what we affect as we take our actions, as follows:<\/p>\n\n\n\n
mutable struct State\n    player::TileIndex\n    boxes::Vector{TileIndex}\n    board::Board\nend<\/pre>\n\n\n\n
You'll notice that our dynamic state thus contains all wall and goal locations. This might seem wasteful but ends up being quite useful. <\/p>\n\n\n\n
An action is a push:<\/p>\n\n\n\n
struct Push\n    box_number::BoxNumber\n    dir::Direction\nend<\/pre>\n\n\n\n
where BoxNumber<\/code> refers to a unique index for every box assigned at the start. We can use this index to access a specific box in a state's boxes<\/code> field.<\/p>\n\n\n\n
Taking an action is as simple as:<\/p>\n\n\n\n
function move!(s::State, game::Game, a::Push)\n    \u25a1 = s.boxes[a.box_number] # where box starts\n    \u25a9 = \u25a1 + game.step_fore[a.dir] # where box ends up\n    s.board[s.player] &= ~PLAYER # Clear the player\n    s.board[\u25a1] &= ~BOX # Clear the box\n    s.player = \u25a1 # Player ends up where the box is.\n    s.boxes[a.box_number] = \u25a9\n    s.board[s.player] |= PLAYER # Add the player\n    s.board[\u25a9] |= BOX # Add the box\n    return s\nend<\/pre>\n\n\n\n
Yeah, Julia supports unicode \ud83d\ude42<\/p>\n\n\n\n
Note that this method updates the state rather than producing a new state. It would certainly be possible to make it functional, but then we wouldn't want to carry around our full board representation. YASS didn't do this, and I didn't want to either. That being said, in order to remain efficient we need a way to undo an action. This will let us efficiently backtrack when navigating up and down a search tree.<\/p>\n\n\n\n
function unmove!(s::State, game::Game, a::Push)\n    \u25a1 = s.boxes[a.box_number] # where box starts\n    \u25a9 = \u25a1 - game.step_fore[a.dir] # where box ends up\n    s.board[s.player] &= ~PLAYER # Clear the player\n    s.board[\u25a1] &= ~BOX # Clear the box\n    s.player = \u25a9 - game.step_fore[a.dir] # Player ends up behind the box.\n    s.boxes[a.box_number] = \u25a9\n    s.board[s.player] |= PLAYER # Add the player\n    s.board[\u25a9] |= BOX # Add the box\n    return s\nend<\/pre>\n\n\n\n
Finally, we need a way to know when we have reached a goal state. This is when every box is on a goal:<\/p>\n\n\n\n
function is_solved(game::Game, s::State)\n    for \u25a1 in s.boxes\n        if (game.board[\u25a1] & GOAL) == 0\n            return false\n        end\n    end\n    return true\nend<\/pre>\n\n\n\n
The hardest part is computing the set of legal pushes. It isn't all that hard, but involves a search from the current player position, and I will leave that for a future blog post. Just note that I use a reach<\/code> struct for that, which will show up in subsequent code blocks.<\/p>\n\n\n\n
Depth First Search<\/h2>\n\n\n\n
I started with depth first search, which is a very basic search algorithm that simply tries all combinations of moves up to a certain depth:<\/p>\n\n\n
\n
\"\"
Depth-first traversal of the search tree. Note that we can visit the same state multiple times <\/figcaption><\/figure>\n<\/div>\n\n\n
In the book we call this algorithm forward search. The algorithm is fairly straightforward:<\/p>\n\n\n\n
struct DepthFirstSearch\n    d_max::Int\n    stack::Vector{TileIndex} # Memory used for reachability calcs\nend\nmutable struct DepthFirstSearchData\n    solved::Bool\n    pushes::Vector{Push} # of length d_max\n    sol_depth::Int # number of pushes in the solution\nend\nfunction solve_helper(\n    dfs::DepthFirstSearch, \n    data::DepthFirstSearchData,\n    game::Game,\n    s::State,\n    reach::ReachableTiles,\n    d::Int\n    )\n    if is_solved(game, s)\n        data.solved = true\n        data.sol_depth = d\n        return true\n    end\n    if d \u2265 dfs.d_max\n        # We exceeded our max depth\n        return false\n    end\n    calc_reachable_tiles!(reach, game, s.board, s.player, dfs.stack)\n    for push in get_pushes(game, s, reach)\n        move!(s, game, push)\n        if solve_helper(dfs, data, game, s, reach, d+1)\n            data.pushes[d+1] = push\n            return true\n        end\n        unmove!(s, game, push)\n    end\n    # Failed to find a solution\n    return false\nend\nfunction solve(dfs::DepthFirstSearch, game::Game, s::State, reach::ReachableTiles)\n    t_start = time()\n    data = DepthFirstSearchData(false, Array{Push}(undef, dfs.d_max), 0)\n    solve_helper(dfs, data, game, s, reach, 0)\n    return data\nend<\/pre>\n\n\n\n
You'll notice that I broke the implementation apart into a DepthFirstSearch<\/code> struct, which contains the solver parameters and memory used while solving, a DepthFirstSearchData<\/code> struct, which contains the data used while running the search and is returned with the solution, and a recursive solve_helper<\/code> method that conducts the search. I use this approach for all subsequent methods. (Note that I am simplifying the code a bit too - my original code tracks some additional statistics in DepthFirstSearchData<\/code>, such as the number of pushes evaluated.)<\/p>\n\n\n\n
Depth first search is able to solve the simple problem shown above, and does so fairly quickly:<\/p>\n\n\n\n
DFS:\n\tsolved: true\n\tmax_depth: 12\n\tn_pushes_evaled: 38\n\tsolve_time: 2.193450927734375e-5s\n\tsol_depth: 8<\/pre>\n\n\n\n
While this is good, the 2-box problem is well, rather easy. It struggles with a slightly harder problem:<\/p>\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n
Furthermore, depth first search does not necessarily return a solution with a minimum number of steps. It is perfectly happy to return as soon as a solution is found.<\/p>\n\n\n\n
\n\n\n\n
Notice that I do not cover breadth-first search. Unlike depth-first search, breadth-first search is guaranteed to find the shortest path. Why don't we use that? Doesn't breadth-first search have the same space complexity as depth-first search, since it is the same algorithm but with a queue instead of a stack?<\/p>\n\n\n\n
I am glad you asked. It turns out that DFS and BFS do indeed have the same complexity, assuming that we store the full state in both the stack and the queue.<\/em> You will notice that this implementation of DFS does not store the full state. Instead, we apply a small state delta (via move!) to advance our state, and then undo the move when we backtrack (via unmove!).  This approach is more efficient, especially if the deltas are small and the overall state is large.<\/p>\n\n\n\n
\n\n\n\n
Iterative Deepening Depth First Search<\/h2>\n\n\n\n
We can address the optimality issue by using iterative deepening. This is simply the act of running depth first search multiple times, each time increasing its maximum depth. We know that depth first search will find a solution if d_max<\/code> is sufficiently large, and so the first run that finds a solution is guaranteed to be a minimum-push solution. <\/p>\n\n\n
\n
\"\"
Depth-first search will return the first solution it finds. Here we show a solution (violet) at a deeper depth, when a shorter solution may still exist in an unexplored branch.<\/figcaption><\/figure>\n<\/div>\n\n\n
We can re-use depth first search:<\/p>\n\n\n\n
struct IterativeDeependingDFS\n    d_max_limit::Int\n    stack::Vector{TileIndex}\nend\nfunction solve(iddfs::IterativeDeependingDFS, game::Game, s::State, reach::ReachableTiles)\n    t_start = time()\n    d_max = 0\n    solved = false\n    pushes = Array{Push}(undef, iddfs.d_max_limit)\n    data = DepthFirstSearchData(false, 0, 0, 0.0, pushes, 0)\n    clear!(reach, game.board)\n    while !data.solved && d_max < iddfs.d_max_limit\n        d_max += 1\n        dfs = DepthFirstSearch(d_max, iddfs.stack)\n        solve_helper(dfs, data, game, s, reach, 0)\n    end\n    return data\nend<\/pre>\n\n\n\n
Now we can solve our 2-box problem in the optimal number of steps:<\/p>\n\n\n\n
IDDFS\n\tsolved: true\n\tmax_depth: 8\n\tn_pushes_evaled: 1389\n\tsolve_time: 0.00043582916259765625s\n\tsol_depth: 8<\/pre>\n\n\n\n
Notice that we evaluated more pushes by doing so, because we exhaustively search all 1-step search trees, all 2-step search trees, all 3-step search trees, ...., all 7-step search trees before starting the 8-step search that found a solution. Now, the size of the search tree grows exponentially in depth, so this isn't a huge cost hit, but nevertheless that explains the larger number for n_pushes_evaled<\/code>.<\/p>\n\n\n\n
Unfortunately, iterative deepening depth first search also chokes on the 3-box problem.<\/p>\n\n\n\n
Zobrist Depth First Search<\/h2>\n\n\n\n
In order to tackle the 3-box problem, we need to avoid exhaustive searches. That is, depth first search will happily push a box left and then re-visit the previous state by pushing the box right again. We can save a lot of effort by not revising board states during a search.<\/p>\n\n\n
\n
\"\"
We can save a lot of computational effort by not re-visiting states<\/figcaption><\/figure>\n<\/div>\n\n\n
The basic idea here is to use a transposition table<\/em> to remember which states we have visited. We could simply store every state in that table, and only consider new states in the search if they aren't already in our table.<\/p>\n\n\n\n
Now, recall that our State<\/code> struct is potentially rather large, and we are mutating it rather than producing a new one with every push. Storing all of those states in a table could quickly become prohibitively expensive. (Debatable, but this is certainly true for very large Sokoban problems).<\/p>\n\n\n\n
One alternative to storing the full state is to store a hash value instead. The hash value, commonly a UInt64, takes up far less space. If a candidate state's hash value is already in our transposition table, then we can be fairly confident that we have already visited it. (We cannot be perfectly confident, of course, because it is possible to get a hash collision, but we can be fairly confident nonetheless. If we're very worried, we can increase the size of our hash to 128 bits or something).<\/p>\n\n\n\n
So to implement depth first search with a transposition table, we need a hash function. I learned a neat method from the YASS entry on the Sokoban wiki<\/a> about how they do exactly this. First, we observe that the dynamic state that needs to be hashed is the player position and the box positions. Next, we observe that we don't really care about the player position per-se, but rather which reachable region of the board the player is in. Consider the following game:<\/p>\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n
The player's reachable space is:<\/p>\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n
As far as we are concerned, all of the highlighted tiles have the same legal pushes, so all states are equivalent when conducting a search.<\/p>\n\n\n\n
We have to compute the player-reachable tiles anyhow when determining which pushes are legal. As such, we can \"normalize\" the player position in any state by just using the reachable tile with minimum index in board<\/code>. If the box positions and this minimum player-reachable tile index match for two states, then we can consider them equivalent.<\/p>\n\n\n\n
Finally, we need a way to hash the box positions. This is where Zobrist hashing<\/a><\/em> comes in. This is a hashing technique that is commonly used in games like Sokoban and Chess because we can keep track of the hash by updating it with each move (and un-move), rather than having to recompute it every time from scratch. It works by associating a random unique UInt64 for every tile on the board, and we xor together all of the hash components that correspond to tiles with boxes on them:<\/p>\n\n\n\n
function calculate_zobrist_hash(boxes::Vector{TileIndex}, hash_components::Vector{UInt64})::UInt64\n    result = zero(UInt64)\n    for \u25a1 in boxes\n        result \u22bb= hash_components[\u25a1]\n    end\n    return result\nend<\/pre>\n\n\n\n
We can modify Game<\/code> to store our Zobrist hash components.<\/p>\n\n\n\n
The biggest win is that xor's inverse is another xor. As such, we can modify State<\/code> to include our current Zobrist hash, and we can modify move<\/code> and unmove<\/code> to simply apply and undo the xor:<\/p>\n\n\n\n
function move!(s::State, game::Game, a::Push)\n    \u25a1 = s.boxes[a.box_number]\n    \u25a9 = \u25a1 + game.step_fore[a.dir]\n    s.board[s.player] &= ~PLAYER\n    s.board[\u25a1] &= ~BOX\n    s.zhash \u22bb= game.hash_components[\u25a1] # Undo the box's hash component\n    s.player = \u25a1\n    s.boxes[a.box_number] = \u25a9\n    s.board[s.player] |= PLAYER\n    s.board[\u25a9] |= BOX\n    s.zhash \u22bb= game.hash_components[\u25a9] # Add the box's hash component\n    return s\nend<\/pre>\n\n\n\n
Easy! Our algorithm is thus:<\/p>\n\n\n\n
struct ZobristDFS\n    d_max::Int\n    stack::Vector{TileIndex}\n    # (player normalized pos, box zhash) \u2192 d_min\n    transposition_table::Dict{Tuple{TileIndex, UInt64},Int} \nend\nmutable struct ZobristDFSData\n    solved::Bool\n    pushes::Vector{Push} # of length d_max\n    sol_depth::Int # number of pushes in the solution\nend\nfunction solve_helper(\n    dfs::ZobristDFS,\n    data::ZobristDFSData,\n    game::Game,\n    s::State,\n    reach::ReachableTiles,\n    d::Int\n    )\n    if is_solved(game, s)\n        data.solved = true\n        data.sol_depth = d\n        return true\n    end\n    if d \u2265 dfs.d_max\n        # We exceeded our max depth\n        return false\n    end\n    calc_reachable_tiles!(reach, game, s.board, s.player, dfs.stack)\n    # Set the position to the normalized location\n    s.player = reach.min_reachable_tile\n    # Exit early if we have seen this state before at this shallow of a depth\n    ztup = (s.player, s.zhash)\n    d_seen = get(dfs.transposition_table, ztup, typemax(Int))\n    if d_seen \u2264 d\n        # Skip!\n        data.n_pushes_skipped += 1\n        return false\n    end\n    # Store this state hash in our transposition table\n    dfs.transposition_table[ztup] = d\n    for push in get_pushes(game, s, reach)\n        data.n_pushes_evaled += 1\n        move!(s, game, push)\n        if solve_helper(dfs, data, game, s, reach, d+1)\n            data.pushes[d+1] = push\n            return true\n        end\n        unmove!(s, game, push)\n    end\n    # Failed to find a solution\n    return false\nend\nfunction solve(dfs::ZobristDFS, game::Game, s::State, reach::ReachableTiles)\n    empty!(dfs.transposition_table) # Ensure we always start with an empty transposition table\n    data = ZobristDFSData(false, Array{Push}(undef, dfs.d_max), 0)\n    solve_helper(dfs, data, game, s, reach, 0)\n    return data\nend<\/pre>\n\n\n\n
This algorithm performs better on the 2-box problem:<\/p>\n\n\n\n
ZOBRIST_DFS\n\tsolved: true\n\tmax_depth: 8\n\tn_pushes_evaled: 25\n\tn_pushes_skipped: 4\n\tsolve_time: 2.1219253540039062e-5s\n\tsol_depth: 8<\/pre>\n\n\n\n
Note how it only evaluates 25 pushes compared to 1389.<\/p>\n\n\n\n
It can easily solve the 3-box problem:<\/p>\n\n\n\n
ZOBRIST_DFS\n\tsolved: true\n\tmax_depth: 38\n\tn_pushes_evaled: 235522\n\tn_pushes_skipped: 189036\n\tsolve_time: 0.0870659351348877s\n\tsol_depth: 37<\/pre>\n\n\n\n
Note how it evaluated 235522 pushes and did not find an optimal solution. We can combine the Zobrist hashing approach with iterative deepening to get an optimal solution:<\/p>\n\n\n\n
ITERATIVE_DEEPENING_ZOBRIST_DFS\n\tsolved: true\n\tmax_depth: 11\n\tn_pushes_evaled: 174333\n\tn_pushes_skipped: 96738\n\tsolve_time: 0.05325913429260254s\n\tsol_depth: 11<\/pre>\n\n\n
\n
\"\"
A push-optimal solution for the 3-box problem. Notice that this is not player-move optimal.<\/figcaption><\/figure>\n<\/div>\n\n\n
A* (Best First Search)<\/h2>\n\n\n\n
For our next improvement, we are going to try to guide our search in the right direction. The previous methods are happy to try all possible ways to push a box, without any intelligence having it tend to push boxes toward a goal, for instance. We can often save a lot of computation by trying things that naively get us closer to our goal.<\/p>\n\n\n\n
Where depth-first search expands our frontier in a depth-first order, A* (or best-first search), will expand our frontier in a best-first order. Doesn't that sound good?<\/p>\n\n\n
\n
\"\"
A* can expand any node in the frontier, and selects the node that it predicts has the best chance of efficiently reaching the goal<\/figcaption><\/figure>\n<\/div>\n\n\n
A*, pronounced \"A Star\", is a best first search algorithm. It orders its actions according to how good the pushes are, where \"goodness\" is evaluated by a heuristic function. We are trying to minimize the number of pushes, and as long as this heuristic function gives as a lower bound on the true minimum number of pushes, A* will eventually find an optimal solution.<\/p>\n\n\n
\n
\"\"
A* uses a heuristic function (plus the cost to reach a node) to evaluate each node in the frontier. It expands the node with the highest predicted reward (i.e., lowest cost).<\/figcaption><\/figure>\n<\/div>\n\n\n
As with Zobrist depth first search, A* also uses state hashes to know which states have been visited. Unlike Zobrist depth first search, A* maintains a priority queue over which state to try next. This presents a problem, because we don't store states, but rather apply pushes in order to get from one state to another. Once again, YASS provided a nifty way to do something, this time to efficiently switch from states in one part of the search tree to another.<\/p>\n\n\n\n
We will store a search tree for our visited states, but instead of each node storing the full state, we will instead store the push leading to the position. We can get from one state to another by traversing backwards to the states' common ancestor and then traversing forwards to the destination state. I find the setup to be rather clever:<\/p>\n\n\n\n
const PositionIndex = UInt32\nmutable struct Position\n    pred::PositionIndex # predecessor index in positions array\n    push::Push # the push leading to this position\n    push_depth::Int32 # search depth\n    lowerbound::Int32 # heuristic cost-to-go\n    on_path::Bool # whether this move is on the active search path\nend<\/pre>\n\n\n\n
function set_position!(\n    s::State,\n    game::Game,\n    positions::Vector{Position},\n    dest_pos_index::PositionIndex,\n    curr_pos_index::PositionIndex,\n    )\n    # Backtrack from the destination state until we find a common ancestor,\n    # as indicated by `on_path`. We reverse the `pred` pointers as we go\n    # so we can find our way back.\n    pos_index = dest_pos_index\n    next_pos_index = zero(PositionIndex)\n    while (pos_index != 0) && (!positions[pos_index].on_path)\n        temp = positions[pos_index].pred\n        positions[pos_index].pred = next_pos_index\n        next_pos_index = pos_index\n        pos_index = temp\n    end\n    # Backtrack from the source state until we reach the common ancestor.\n    while (curr_pos_index != pos_index) && (curr_pos_index != 0)\n        positions[curr_pos_index].on_path = false\n        unmove!(s, game, positions[curr_pos_index].push)\n        curr_pos_index = positions[curr_pos_index].pred\n    end\n    # Traverse up the tree to the destination state, reversing the pointers again.\n    while next_pos_index != 0\n        move!(s, game, positions[next_pos_index].push)\n        positions[next_pos_index].on_path = true\n        temp = positions[next_pos_index].pred\n        positions[next_pos_index].pred = curr_pos_index\n        curr_pos_index = next_pos_index\n        next_pos_index = temp\n    end\n    return s\nend<\/pre>\n\n\n\n
Our heuristic lower bound can take on many forms. One of the simplest is the sum of the distance of each box to the nearest goal, ignoring walls. This is definitely a lower bound, as we cannot possibly hope to require fewer pushes than that. Better lower bounds certainly exist - for example this lower bound does not take into account that each box must go to a different goal. <\/p>\n\n\n\n
The lower bound we use is only slightly more fancy - we precompute the minimum number of pushes for each tile to the nearest goal ignoring other boxes, but not ignoring the walls. This allows us to recognize basic deadlock states where a box cannot possibly be moved to a goal, and it gives us a better lower bound when walls separate us from our goals.<\/p>\n\n\n
\n
\"\"
Our cost lowerbound is the sum of the push distance of each box to the closest goal<\/figcaption><\/figure>\n<\/div>\n\n\n
The A* implementation is a little more involved than the previous algorithms, but its not too bad:<\/p>\n\n\n\n
struct AStar\n    d_max::Int\n    n_positions::Int\nend\nmutable struct AStarData\n    solved::Bool\n    max_depth::Int # max depth reached during search\n    pushes::Vector{Push} # of length d_max\n    sol_depth::Int # number of pushes in the solution\nend\nfunction solve(solver::AStar, game::Game, s::State)\n    d_max, n_positions = solver.d_max, solver.n_positions\n    # Allocate memory and recalculate some things\n    data = AStarData(false, Array{Push}(undef, d_max), 0)\n    reach = ReachableTiles(length(game.board))\n    clear!(reach, game.board)\n    stack = Array{TileIndex}(undef, length(game.board))\n    pushes = Array{Push}(undef, 4*length(s.boxes))\n    queue_big = Array{Tuple{TileIndex, TileIndex, Int32}}(undef, length(s.board) * N_DIRS)\n    distances_by_direction = Array{Int32}(undef, length(s.board), N_DIRS)\n    dist_to_nearest_goal = zeros(Int32, length(s.board))\n    calc_push_dist_to_nearest_goal_for_all_squares!(dist_to_nearest_goal, game, s, reach, stack, queue_big, distances_by_direction)\n    # Calculate reachability and set player min pos\n    calc_reachable_tiles!(reach, game, s.board, s.player, stack)\n    move_player!(s, reach.min_reachable_tile)\n    # Compute the lower bound\n    simple_lower_bound = calculate_simple_lower_bound(s, dist_to_nearest_goal)\n    # Allocate a bunch of positions\n    positions = Array{Position}(undef, n_positions)\n    for i in 1:length(positions)\n        positions[i] = Position(\n            zero(PositionIndex),\n            Push(0,0),\n            zero(Int32),\n            zero(Int32),\n            false\n        )\n    end\n    # Index of the first free position\n    # NOTE: For now we don't re-use positions\n    free_index = one(PositionIndex)\n    # A priority queue used to order the states that we want to process,\n    # in order by total cost (push_depth + lowerbound cost-to-go)\n    to_process = PriorityQueue{PositionIndex, Int32}()\n    # A dictionary that maps (player pos, zhash) to position index,\n    # representing the set of processed states\n    closed_set = Dict{Tuple{TileIndex, UInt64}, PositionIndex}()\n    # Store an infeasible state in the first index\n    # We point to this position any time we get an infeasible state\n    infeasible_state_index = free_index\n    positions[infeasible_state_index].lowerbound = typemax(Int32)\n    positions[infeasible_state_index].push_depth = zero(Int32)\n    free_index += one(PositionIndex)\n    # Enqueue the root state\n    current_pos_index = zero(PositionIndex)\n    enqueue!(to_process, current_pos_index, simple_lower_bound)\n    closed_set[(s.player, s.zhash)] = current_pos_index\n    done = false\n    while !done && !isempty(to_process)\n        pos_index = dequeue!(to_process)\n        set_position!(s, game, positions, pos_index, current_pos_index, data)\n        current_pos_index = pos_index\n        push_depth = pos_index > 0 ? positions[pos_index].push_depth : zero(Int32)\n        calc_reachable_tiles!(reach, game, s.board, s.player, stack)\n        # Iterate over pushes\n        n_pushes = get_pushes!(pushes, game, s, reach)\n        for push_index in 1:n_pushes\n            push = pushes[push_index]\n            move!(s, game, push)\n            calc_reachable_tiles!(reach, game, s.board, s.player, stack)\n            move_player!(s, reach.min_reachable_tile)\n            # If we have not seen this state before so early, and it isn't an infeasible state\n            new_pos_index = get(closed_set, (s.player, s.zhash), zero(PositionIndex))\n            if new_pos_index == 0 || push_depth+1 < positions[new_pos_index].push_depth\n                lowerbound = calculate_simple_lower_bound(s, dist_to_nearest_goal)\n                # Check to see if we are done\n                if lowerbound == 0\n                    # We are done!\n                    done = true\n                    # Back out the solution\n                    data.solved = true\n                    data.sol_depth = push_depth + 1\n                    data.pushes[data.sol_depth] = push\n                    pred = pos_index\n                    while pred > 0\n                        pos = positions[pred]\n                        data.pushes[pos.push_depth] = pos.push\n                        pred = pos.pred\n                    end\n                    break\n                end\n                # Enqueue and add to closed set if the lower bound indicates feasibility\n                if lowerbound != typemax(Int32)\n                    # Add the position\n                    pos\u2032 = positions[free_index]\n                    pos\u2032.pred = pos_index\n                    pos\u2032.push = push\n                    pos\u2032.push_depth = push_depth + 1\n                    pos\u2032.lowerbound = lowerbound\n                    to_process[free_index] = pos\u2032.push_depth + pos\u2032.lowerbound\n                    closed_set[(s.player, s.zhash)] = free_index\n                    free_index += one(PositionIndex)\n                else\n                    # Store infeasible state with a typemax index\n                    data.n_infeasible_states += 1\n                    closed_set[(s.player, s.zhash)] = infeasible_state_index\n                end\n            else\n                data.n_pushes_skipped += 1\n            end\n            unmove!(s, game, push)\n        end\n    end\n    return data\nend<\/pre>\n\n\n\n
Notice that unlike the other algorithms, this one allocates a large set of positions for its search tree. If we use more positions than we've allocated, the algorithm fails. This added memory complexity is typically worth it though, as we'll see.<\/p>\n\n\n\n
Here is A* on the 3-box problem:<\/p>\n\n\n\n
AStar\n\td_max 100\n\tn_positions 500\n\t\tsolved: true\n\t\ttotal time: 0.0008640289306640625s\n\t\tsetup_time: 2.4080276489257812e-5s (2.79%)\n\t\tsolving time: 0.0008399486541748047s\n\t\tmax_depth: 11\n\t\tsol_depth: 11\n\t\tn_pushes_evaled: 1660\n\t\tn_pushes_skipped: 959\n\t\tn_infeasible_states: 313\n\t\tn_positions_used: 388<\/pre>\n\n\n\n
It found an optimal solution by only evaluating 1,660 pushes, where iterative deepening Zobrist DFS evaluated 174,333. That is a massive win!<\/p>\n\n\n\n
A* is able to solve the following 4-box puzzle to depth 38 by only evaluating 5,218 pushes, where iterative deepening Zobrist DFS evaluates 1,324,615:<\/p>\n\n\n
\n
\"\"
A push-optimal solution for \"Chaos\", a level by YASGen and Brian Damgaard <\/figcaption><\/figure>\n<\/div>\n\n\n
It turns out that A* can handle a few trickier puzzles:<\/p>\n\n\n
\n
\"\"
Sasquatch 01<\/figcaption><\/figure>\n<\/div>\n\n
\n
\"\"
Sasquatch 02<\/figcaption><\/figure>\n<\/div>\n\n\n
However, it too fails as things get harder. <\/p>\n\n\n\n
Conclusion<\/h2>\n\n\n\n
There you have it - four basic algorithms that progressively expand our capabilities at automatically solving Sokoban problems. Depth first search conducts a very basic exhaustive search to a maximum depth, iterative deepening allows us to find optimal solutions by progressively increasing our maximum depth, Zobrist hashing allows for an efficient means of managing a transposition table for Sokoban games, and A* with search tree traversal lets us expand the most promising moves.<\/p>\n\n\n\n
The YASS codebase had plenty of more gems in it. For example, the author recognized that the lower bound + push depth we use in A* can only increase. As such, if we move a box toward a goal, our overall estimated cost stays the same. But, every state we move from is by definition a minimum-cost state, so the new state is also then minimum cost as well. We can thus save some computation by just continuing to expand from that new state. See, for example, the discussion in \"Combining depth-first search with the open-list in A*<\/a>\".<\/p>\n\n\n\n
I'd like to cover the reachability calculation code in a future blog post. I thought it was a really good example of simple and efficient code design, and how the data structures we use influence how other code around it ends up being architected. <\/p>\n\n\n\n
Thanks for reading!<\/p>\n\n\n\n
\n\n\n\n
Special thanks to Oscar Lindberg for corrective feedback on this post.<\/p>\n","protected":false},"excerpt":{"rendered":"
Sokoban – the basic block-pushing puzzle – has been on my mind off and on for several years now. Readers of my old blog know that I was working on a block-pushing video game for a short while back in 2012. John Blow, creator of The Witness, later announced that his next new game would […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[3],"class_list":["post-76","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-sokoban"],"_links":{"self":[{"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/posts\/76","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/comments?post=76"}],"version-history":[{"count":30,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/posts\/76\/revisions"}],"predecessor-version":[{"id":422,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/posts\/76\/revisions\/422"}],"wp:attachment":[{"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/media?parent=76"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/categories?post=76"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/tags?post=76"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}