Talk:Links

2009-05-25T16:03:32Z

Sokobania: /* sokogen résumé */

== 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:<br>
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:<br>
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?

[[User:Sokobania|Sokobania]] 12:36, 29 April 2009 (CEST)

<div style="background-color:#F0FFF0;padding:5px;border:1px solid green;">
Hello Jacques!

Thanks a lot for your explanations!<br>
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 [http://sourceforge.net/projects/jsokoapplet/ 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.

<br> Matthias, 30.04.2009
</div>

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 - [[User:Sokobania|Sokobania]] 11:53, 22 May 2009 (CEST)

Brian:<br />
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( [[User:Sokobania|Sokobania]] 18:03, 25 May 2009 (CEST)

User:Sokobania

2009-04-29T09:17:51Z

Sokobania: /* a brief history of "sokogen" */

== The Sokoban Level Generator "Sokogen" ==

My name is Jacques Duthen (sokobania).

In 1996, as my son Dimitri was 6 years old, I wrote, for him (and, in anticipation, for his young brother), the collection with their name "Dimitri and Yorick".
I found it very painful to do this by hand (initially on the Trouville beach sand!). So, I wrote a program in my spare time to automatically generate sokoban levels. I called this program "Sokogen", which stands for "sokoban generator".<br>
Cf. also http://games.groups.yahoo.com/group/sokoban/message/939

This program was partially inspired from the Yoshio Muraso's paper.

The collections generated with "sokogen" are all called "sokogen-yymmdd", where "yymmdd" is the date when the collection is generated or finished.

I also wrote a program "pskm-print.el" (in emacs-lisp and postscript) to generate the postscript printable version of a collection of sokoban levels.

I've not modified my personal pages since many years, but, still, the page "interlude" refers to these program-generated levels:
http://duthen.club.fr/sokoban/interlude.html

For this interlude happening, I printed out (with pskm-print) different collections so that everybody can play (we had not enough computers).

Let me translate (the best I can!) this part of this page:

[TRANSLATION]

=== Play on paper ===
There will be several kilogrammes of sheets, with several copies of hundreds of small Sokoban levels (with an approximate size 7x7), i.e. enough material to keep us busy for some time.

To play on paper, please bring several coins of 10 centimes and one or two coins of ½ Franc (NDT: this was before the "euro" conversion) (or the other way around for the richer ones).

Available paper collections are:

* the 41 levels by Yoshio Murase (hand made)
* the 52 levels by Yoshio Murase (generated by computer)
* my 61 levels (hand made for beginners)
* my 78 levels Sokogen-990602 (generated by computer)

and, exclusively worlwide:

* my 153 levels Sokogen-990702
* my 160 levels Sokogen-990917
* my ??? levels Sokogen-9911??
[/TRANSLATION]

So, at this time (1999 november), I had 5 different collections.
The first two collection can be found with internet:
* "Dimitri and Yorick" (61 hand-made levels)
* "Sokogen-990602" (78 sokogen levels)
The three other ones have not been (yet) released, though, I think, I sent "Sokogen-990702" to some game designer to include it in a sokoban game.
In nov 1999, the last one was still in progress.

Presently (may 2009), I plan to rewrite the "sokogen" program from lisp to Objective-C or Java, but it would probably take some time...

)jack(

Sokoban Wiki - User contributions [en]

Talk:Links

User:Sokobania