JavaScript Sokoban AI Solver Demonstrates Optimal Solutions for Puzzle Game

Sokoban AI Solver Introduction

A new AI solver for the classic 1980s puzzle game Sokoban has been developed and released. The solver, implemented in plain JavaScript, is a port of a C++ optimal solver and is designed to find the provably fewest-moves solution for Sokoban boards. The game requires a player to push every box onto a goal, with the keeper also needing to finish on a goal.

Technical Implementation Details

The AI solver operates using an A* search algorithm, optimized to handle the complexity of Sokoban. Key optimizations include a move-optimal macro-push A* where each search edge represents a complete box push, calculated by the keeper's shortest walk to the push spot plus one. This approach allows the search to skip individual walking steps, focusing on significant moves.

Efficiency and State Management

To manage memory and improve performance, the solver uses compact bitmask states. Boxes are packed into a 32-bit integer, and the keeper's position into another number, resulting in a state key of approximately 8 bytes. This compact representation allows millions of states to fit within tens of megabytes of memory. The A* frontier is managed with a dial bucket queue, and visited states are stored in an allocation-free, cache-friendly typed-array hash.

Deadlock Pruning and Admissibility

The solver incorporates deadlock pruning to discard unsolvable positions early. This is achieved through a static dead-square table, which uses reverse-reachability from goals, and a freeze check. A wall-aware push-distance lower bound ensures that the A* algorithm remains admissible, guaranteeing optimal solutions.

Performance and Solved Boards

The solver demonstrates its efficiency by solving boards 1 through 14 to their proven optimum in milliseconds. The optimal move counts displayed for these boards are precisely what the solver returns. Board 15, an 8-box maze, is noted as an exception, requiring the exploration of approximately 49 million states for an optimal search.