Project Showcase: Sokoban AI Solver

Developed by Menachem Kornreich, this project implements an automated solver for the classic 1980s puzzle game, Sokoban (which translates to "warehouse keeper"). The objective is straightforward: maneuver every box onto a designated goal square.

🕹️ Gameplay Mechanics

The game takes place on a grid-based warehouse. The rules are as follows:

• Movement: The keeper can move one square at a time (Up, Down, Left, or Right).
• Pushing: A box can be pushed if the space immediately behind it is either an empty floor or a goal.
• Constraints:
  • Only $\text{one}$ box can be moved per step.
  • Boxes can be pushed out of a goal to clear a path.
• The Goal Count: Every board contains exactly one more goal than there are boxes. This is because the keeper must occupy the final goal to complete the puzzle.

---

🤖 The AI Architecture

Solving Sokoban is essentially an $A^*$ search problem. However, a naive search that evaluates every single keeper step would lead to a combinatorial explosion on complex boards.

To solve this, the author ported a native C++ optimal solver into plain JavaScript. This solver doesn't just find any solution; it finds the provably fewest-moves solution using a technique called Move-optimal macro-push A*.

⚙️ Technical Optimizations

Instead of searching step-by-step, the AI treats each "edge" in the search graph as a complete box push. The cost of an edge is calculated as:

$\text{Total Cost} = (\text{Shortest path for keeper to reach the push spot}) + 1$

This allows the algorithm to skip over the mundane walking steps while still maintaining an accurate count of the total moves.

State Management

To keep the memory footprint low, the solver uses highly compressed state representations:

Search Infrastructure

• Frontier: Managed via a bucket queue organized by cost.
• Visited Set: Stored in a flat typed-array hash which also maintains parent links for path reconstruction.

// Conceptual state representation
const state = {
  boxes: 0b10110010101, // Bitmask of boxes on reachable cells
  keeper: 42,           // Index of keeper's current cell
};

🛡️ Pruning and Admissibility

To prevent the search from exploring impossible paths, the AI employs several checks:

• Static Dead-Square Table: Uses reverse-reachability from goals to identify "dead" zones.
• Freeze Check: Detects positions where boxes can no longer be moved.
• Wall-Aware Push-Distance: A lower-bound heuristic that ensures the $A^*$ search remains admissible (guaranteeing the optimal solution).

---

📊 Performance & Results

For the majority of the provided levels, the solver is incredibly efficient.

• Boards 1–14: These are solved in milliseconds directly within the browser, returning the proven optimal move count.
• Board 15: This board is a special case. An optimal search requires exploring $\approx 49\text{ million}$ states and consuming $1\text{ GB}$ of RAM.

Because running this in a browser tab would be prohibitively slow, the solution for Board 15 was computed offline using the native C++ version of the algorithm.

Board 15 Offline Stats:

• Hardware: 24 CPU cores.
• Execution Time: $\sim 5\text{ seconds}$ (Parallel $A^*$).
• Optimal Result: 184 moves.
• Implementation: The browser simply replays this precomputed solution.