Talk:Links
From Sokoban Wiki
Current revision as of 16:03, 25 May 2009
Level Generators
Sokogen
Hello Matthias !
I really appreciate this "sokoban wiki" !
I wanted to send you a mail via sokoban-wiki, but it seems that you have not allowed it in your personal preferences. So, I will use this discussion page (which is a good place to do that, imho!).
You wrote in the comment part of your last undo:
Level Generators - @Sokobania: is this just a level set or a real program? I haven't found the program at http://duthen.club.fr/SOKOBAN-HTML/sokoban-jd.html
I wrote a few lines on my local home page:
http://sokobano.de/wiki/index.php?title=User:Sokobania
Thus the answer to your question is: "yes, it's a real program", though it has not been released yet.
Would you agree to redo my change?
Sokobania 12:36, 29 April 2009 (CEST)
Hello Jacques!
Thanks a lot for your explanations!
I have removed your changes because I hadn't found your program and the Wiki shouldn't contain information about "secret" personal programs nobody else knows or can download. However, together with your extra information it's an interesting information how the level sets had been generated and what program had been used to do it. Therefore I of course have redone your change (well, nevertheless I hope that you may release the program at any time to the public).
If you plan to rewrite the program from lisp to Java I will be very interested to see it and - if you allow - to help you doing it. I am the author of the program JSoko. It's a Java program (open source). I'm in contact with Brian Damgaard who is the author of YASGen. My program is missing a generator for levels. Maybe we can exchange information on how to code such a generator so you can rewrite your program and I can implement a simple generator for my program.
Matthias, 30.04.2009
Hello Matthias,
Thank you for redoing the changes about Sokogen.
I'm currently writing an article about its algorithm, but I'm not sure (yet) if I want to "give/share" it... I need more time still...
Anyway, do you know whether SokEvo (http://fruise.googlepages.com/sokevo.html by Lee Haywood) is a sokoban level generator by itself or if it just uses the YASGen program ?
Jacques - Sokobania 11:53, 22 May 2009 (CEST)
Brian:
Lee's SokEvo is a level generator in its own right, but it uses my YASGen code as backend, i.e., as "calculator". It's easiest to explain the relationship by saying that the level generator consists of two parts:
- a level-producer: the evolver, or GA (genetic algorithm) machine, producing candidate templates.
- a level-searcher: a backwards search, starting with boxes at the goal squares and then pulling the boxes around on the board as far as possible. The position with the highest number of pulls is the best candidate which can created from this template. The level-searcher uses a conventional breadth-first search strategy, and is in a sense the opposite of a Sokoban solver.
Lee's SokEvo program has its own producer with a different GA machine than the YASGen program. My contribution was to convert the YASGen backend from Pascal to the C language, so it was easy for Lee to incorporate the backend in SokEvo.
For the learning experience, Lee years later gave the code a light massage to match his personal taste, but a comparison of his final backend and my "YASGen.c" C-language source-code (which can be found in the YASS package) reveals that it's still the same code.
Hello Brian!
Thank you very much! That sounds pretty clear for me!
And sokogen seems quite close to YASGen and SokEvo!
In a sense, this is not totally surprising since sokoban is never much more than pushing and/or pulling boxes!
When I wrote it, I did not want to write or use a solver (like Yoshio Murase did). So sokogen has no solver and it does not need any one since it deals only with valid sokoban puzzles.
Sokogen has different entry points: it can use an empty sokoban level (with no boxes and no pusher) or create a new one using templates as described in Yoshio's paper.
Then sokogen uses a breadth-first back and forth search strategy, using a subtle evaluation function to measure the "difficulty" of the levels which have been generated.
Et voilà!
)jack( Sokobania 18:03, 25 May 2009 (CEST)
