Sokoban Wiki - User contributions [en]

User:Puzl bustr

2010-03-26T18:15:51Z

Puzl bustr: moved my Sokoban solving ideas to a main wiki divided into sections

I'm a Sokoban enthusiast - I like solving and creating puzzles. In the past I've helped program Sokoban games and a generator (backward solver), and maintained a website with my puzzles for download, but due to getting Repetitive Strain Injury (RSI) from typing am unable to do these things involving frequent typing. I've an adapted mouse and am able to write this with an onscreen keyboard. Am able to solve and recently started designing more puzzles.

I'm interested in computer Sokoban solving in terms of artificial intelligence. I believe that, using domain-specific knowledge and a combination of limited searches using heuristics (for example, identifying free space, empty squares which you could imagine adding a box to without creating an obvious deadlock or a new blocked-in area and variations to reach it via single-box push routes) and conventional tree search, it is possible to substantially improve on conventional computer solvers.

Since I cannot program my ideas, I'd like to make them available here for others to implement; I'd like to be credited with my name David Holland and for these ideas to be freely available (with any implementation open-source). I'll try to update these ideas as I can and include descriptions of algorithms (as I've already done for the main limited search identifying free space and computing single-box push routes and "shuffling") but as I have to rest my hands frequently would prefer "able-handed" programmers to do the coding. Several of the algorithms can also be used in conventional Sokoban solvers.

[[David Holland's computer Sokoban solving ideas]]
Section 3 contains the algorithms and the most precise descriptions.

David Holland's computer Sokoban solving ideas

2010-03-26T18:00:47Z

Puzl bustr: summary page of contents for my computer Sokoban solving ideas created

<div class="box margin-3">
<div class="title" align="center">Contents</div>

:* [[DHolland S1 | Section 1. Ideas]]
:* [[DHolland S2 | Section 2. Heuristics]]
:* [[DHolland S3 | Section 3 Algorithms]]
</div>

User talk:Puzl bustr

2010-03-18T10:01:40Z

Puzl bustr:

Hello.

Thanks a lot for your detailed ideas!!!
I will try to implement them in the next solver for my program 'JSoko'.

Matthias Meger

* Great! I just noticed my description of the goal trap algorithm is incomplete. Goal traps would be a good addition to the deadlock section of the wiki. I should exclude PRZs of push-squares which aren't "reversible": the extra condition that you can push from the goal to the push-square. In example goal trap on wall, only the PRZs along the wall constitute the goal trap, not the PRZ of the push-square off the wall. And there needs to be a condition where the goal itself belongs to the trap (as in the example goal trap on wall). A corner goal would have an empty goal trap but not belong to it - needs to be excluded as not a deadlock if corner has no box on it, provided some box can push to corner. The reversible region digraph generalization, with the example goal trap on wall as a sink and the off-the wall squares as a source, makes this clearer.

I'm relieved someone "able-handed" is working on this! I'm hoping you'll discuss it with other programmers and between you figure out what is easily implementable - some of my ideas are pretty ambitious and might take months or years to implement properly, if at all.

David Holland