computers can solve sokoban levels?

6 posts / 0 new
Last post
Roberto
Offline
Joined: 2004-03-22
computers can solve sokoban levels?

Hi everyone! I'm not a computer expert, so I wonder if the advanced computers of this days (like deep blue) can solve huge sokoban levels with lots of pieces (#boxes>10). If this machines can make milions of calculations in a second for solving tradicional board games like chess and checkers, can't they do the same for sokoban? Beside, can they find the best solutions (minimal number of moves, pushes, ans so on...)? I've tried to use some solvers avaiable on the internet into my computer, but for some kinds of levels (like that ones of Francois Marques) they dont't work. It's even more difficult if I choose the option 'with best moves' or 'best pushes'.

I ask that because I've just been at Francois Marques excelent page (http://sokoban.online.fr). There, I've seen the 'challenges of the month' section (http://sokoban.online.fr/concours_mois.html), in which some boards are like I've described above. For each sokoban challenge, there is a list of records. I wonder if the records listed there are really from human brains or from the computer chips.

Unfortunately, there are no more challenges at that page for the months after November/2003. And I hope someone here in this forum could tell me where I can find sites like Francois': with challenges, new challenges in the next month (or week) and a list of records. Thanks.

fst
Offline
Joined: 2004-09-02

Super computers or expert systems can solve huge sokoban puzzles with some complex algorithms and find a solution (not the best) for it. This level may be a very huge maze like size of 128x128, but used artificial search algorithms does not guarantee that it will find a solution for every level.

The algorithms used for finding the best solution is really slower and un-efficient so the result depends on movable area of the maze and number of boxes.

Sokoban game is really different from chess and chess-like games. In the chess game, you don't have to think the deepest move. In computers, Chess engines regulate their moves according to time to think. They think the moves deeper and deeper and some point they decide that the best move is found. So the computer does not have to think checkmate position from beginning, and after each move they generally think from that position as it is the beginning position (for ex. they forget the exact beginning position of the chess game because there is no need) but in Sokoban game, a computer must think from the beginning until the solution is found. Therefore, the computer needs less calculations for chess game Smile

If someone finds the real-sokoban algorithm someday, then sokoban game would be finished by computers but hey it is not still found for the chess game Smile

SpOiLeR
Offline
Joined: 2004-09-15

':D'

Although I know at least two great sokoban solving programs I don't really use them as long as author of level guaratees that level is solvable. Using solvers just spoils fun of trying to find perfect solution by myself. I'm kind of fanatic with that, because there are levels that I have found like 9 diferent solutions. Of course, there is always one best solution for moves and one for pushes, but just keeping tryng to find it by myself makes whole fun of sokoban. What do you people think about that? Are you satisfied with first solution found or you keep searching even when level is solved?

Ah, yes, the programs I was talking about...

First one is rbox (link to it is in download page of Sokoban)

Second one can be found at :

http://sps.gotdns.org/

I have tried both of them, and rbox ocasionally gives shorter solutions, but SPS looks better and it supports Sokoban+ levels (although I haven't tried that part of it)...
Blum 3Shok

Nebol
Offline
Joined: 2005-05-11

Of course it's possible to solve Sokoban levels.

Here's the webpage about my own solver-software:
http://www.nebol.se/truth/jesokoban

My software can currently find the optimal solution for the 3500 or so easiest levels within a reasonable amount of time... but then it goes downhill as the levels grow in complexity. But I have many ideas on how to improve on the time needed to find the solution.

Serg Belyaev
Offline
Joined: 2006-11-19

Here's my solver-software:
http://svb-sokoban.narod.ru

CellarDweller
Offline
Joined: 2004-12-22

It is now October 2019, and I'm looking for a solver. It seems they're all gone or don't work anymore for various reasons.

I used to use SPS from Codecola, but that's nowhere to be found.

Can anyone help?