Ancient Web: Alberta's Sokoban Page Treated Box-Pushing Like AI Research

Part of the Ancient Web Collection.

Sokoban looks like a puzzle about pushing crates into corners. At the University of Alberta, it became a laboratory for figuring out how computers think their way into corners.

Visit the original Sokoban research homepage.

The homepage preserves the layout of an academic games site with a visitor-count label dating to October 20, 1998. Its links lead to research papers, examples, solved mazes, and a program called Rolling Stone. These are not modern interactive demos packaged as a product; much of the work lives in plain HTML tables and old PostScript documents.

The researchers' explanation of their choice is illuminating. Sokoban has simple rules, a supply of increasingly difficult test cases, and configurations that become unsolvable after an ill-chosen push. These qualities made it an ideal playground for search algorithms trying to detect deadlocks and break complicated problems into manageable parts.

Rolling Stone learns not to waste moves

The program page describes Rolling Stone's use of iterative-deepening A-star search, then itemizes enhancements with a count of puzzles solved after each addition. Hash tables help avoid repeated positions; deadlock tables recognize hopeless arrangements; tunnel and goal macros reduce unnecessary search; pattern searches and relevance cuts make the work more selective.

The numerical progression is unusually revealing. According to the page's experimental table, early configurations solved none of the standard ninety problems; after successive additions the count climbed to fifty-seven. The page offers a source-code link, but that does not establish whether every historical download remains available.

The publication list anchors the experiment in dated research. It includes work by Andreas Junghanns and Jonathan Schaeffer from the late 1990s, Junghanns's 1999 dissertation, and journal articles from 2001. Some papers are marked unavailable; others link to PostScript files.

There is also a striking cultural tangent. In the history section, Andreas criticizes the copying of carefully authored Sokoban levels without permission or attribution. He argues that their elegant design deserves respect, comparing it to other creative work. The people making clever puzzles were not merely feeding anonymous test data to researchers.

That tension makes the site unusually human. It preserves the technical problem, the solver's progress, and the researchers' growing appreciation for the people who invented the challenges.

Examine Rolling Stone's algorithm table.

Part of the Ancient Web Collection.