Sokoban Levels Design Contest - Description

The formal definitions

Given a Sokoban level, define three parameters of that level: B, L, Score as follows:

Additionally we define a Cyclic Sokoban level as a Sokoban level, where all the boxes in the starting position are placed already on a target goal position, so there is nothing to be done. However in this case an additional constraint is added, that there must be a first initial Pushing move from the starting position. After that push the smallest number of moves required for restoring all boxes back to the original configuration is the Score (the number of moves also includes the original push). Notice this means that in the The standard Sokoban level format, this level will be an All-Star, i.e. it will have only '*' characters for the boxes.

Some examples

The following examples are given in the The standard Sokoban level format, this is also the format for level submissions to this contest.

Here is an example, of a published level, titled Cosmonotes 15 from Author Aymeric du Peloux. The parameters for this level are: B=3, L=20, and Score=88.

     #@. #
    #  *  ##
    #  .$  #
    ####   #

Here is an example of a Cyclic level with parameters:B=1, L=8, and Score=8.
      #   ###
      #   *@#

The competition problem classes

In this competition, you will need to submit Sokoban levels designed by you or your programs. The levels submitted will be classified to one of 50 problem classes defined below, or deemed illegal for this contest. For each of those problem classes you get a score, called raw score which is the highest Score of a level you submitted in that class.

A problem class is defined by the parameter B (the number of boxes), and a range on the board size L, as defined by the table below. In addition whether the level is cyclic or not is also part of the class' definition.

When a level is submitted to the site, its parameters are checked and then it is automatically associated with the corresponding problem class. The competition's scorer determines its Score defined above, i.e. the length of the shortest solution to the level, and the raw score you get for that problem class is updated if it is an improvement upon an earlier submission for that class. Notice the table below has only 25 entries, because you need to submit both a cyclic level, and a non cyclic level with parameters defined by the table, hence there are actually 50 problem classes.

Here is the table defining the competition's problem classes:

Num B Min L Max L
1 1 3 128
2 1 129 256
3 1 257 512
4 1 513 1024
5 2 4 100
6 2 101 200
7 2 201 400
8 2 401 800
9 3 5 80
10 3 81 160
11 3 161 240
12 4 6 40
13 4 41 80
14 4 81 120
15 5 7 30
16 5 31 60
17 5 61 90
18 6 8 35
19 6 36 70
20 7 9 30
21 7 31 56
22 8 10 26
23 8 27 48
24 9 11 44
25 10 12 40

Scoring normalization and Rankings

Each of the 50 raw scores is converted to a normalized score between 0 to 1, as described below, and the final score for each contestant is the sum of all normalized scores, which is a number between 0 and 50. This score is visible to the rest of the world, and determines the competitors rankings. To win this contest all you have to do, is get the highest final score at the end of the contest!

The normalization of raw scores is very simple, but is time dependent. For each problem class, denote by Smax the maximal raw score submitted by some contestant for that class. If your raw score is S then the normalized score is S/Smax. That means if you submitted the best (highest) raw score for the problem class you will get 1.0, and otherwise you get a score that is less than 1, such as 0.85 for example. Notice that it means your final score will change also without you submitting anything, as it will become lower when Smax of some problem class is improved by another contestant. To make things more challenging, you can only see your final normalized score, and your raw scores, so figuring out what is the current Smax for any class is not that easy (though its possible to get a good estimate).

Additionally, If you have one of the three best raw scores for a problem class, you get on the podium for that problem class. So there are totally 50 podiums, with 150 different virtual medals. Even if you have no chance of winning the global contest, you might get a chance at one of the podium places...
On the podiums there certainly might be a tie of the raw scores, and in that case the one who submitted the earliest is the winner of course.

Submission process and etiquette

As mentioned above you need to generate your levels in the standard Sokoban level format. Run length encoding with up to two digits (maximum run is 99), is also supported. Hyphens and underscores are accepted as well as spaces to represent an empty square. Just copy and paste your level in the submit page text box. The total number of characters thus pasted, must not be more than 16000. If run length encoding is used for compression, the number of characters in the expanded level must not be more than 32768.

After a legal level is submitted, it will be classified automatically to its problem class and your raw score for that problem, and final score in the standings will be updated automatically. The competition parser does not require a level to be totally surrounded by walls, but if you forget a wall somewhere it means that the board size L, will be bigger than you intended.

Since many levels are published in the public domain, an effort was made to recognize all those published levels. If you submit a level that is known in the public domain, or a rotation/reflection of one, and that level is in the scorer database, your submission will be rejected automatically with an appropriate error message normally identifying the original Author. You may however submit a variation of a published level.

For each user, a copy of the level that achieved his best raw score would be kept in the site's database, however it would not be visible, even to the user. That is because in this site users will not have passwords, hence I don't want somebody that guessed your username to be able to view your levels! However when the contest is finished, I intend to publish the levels that achieved the podiums in each problem category with credits to their submitters as authors of course.

Status report

Since calculating the score may take more than 10 seconds for hard cases, and since server machine may be overloaded, a queuing mechanism is embedded in the server engine and getting your result may take some time, depending on the circumstances. In your status report, below the submit text box, you will see whether you have some submissions queued and whether you have one currently running. Below that, is a status report for your recent completed submissions. There is a built in delay of about 1.5 seconds in the reporting, so when server is idle and your problem is easy, you will see the status immediately after submitting. The report itself for a successful submission, will contain the parameters of the level, its raw score, and whether you improved upon earlier score. Otherwise, an error string is displayed. You can also view the original level related to that status.

The submitted level view

The level view popup window, lets you view your submitted level, and now also the solution sequence of moves found by the scorer for your successful submissions. You can only view your latest 3 submissions in the status report. To see the solution ASCII animation, just press the left and right arrow keys, to move through the solution sequence backwards and forwards. To reset the state to the original submission, just press the home key. The solution view will not work well for RLE compressed levels, and displayable solution length is limited to 4000, so for levels with higher score, there is no solution animation.

The scorer/solver program

Calculating the score of a Sokoban level is a non-trivial task of course, as by definition it means one must find a provably move optimal solution for that level. As you probably know Sokoban is quite a hard puzzle to solve for humans as well as computers. However when the board is not too big, and specially when the number of boxes is small the task becomes relatively easy for modern computers.

I have invested quite a bit in the solver program, that is the engine behind this site. It is probably the fastest and most efficient program for finding move optimal solution to arbitrary reasonably sized Sokoban levels, particularly because it was designed solely with this purpose in mind, compared to other excellent Sokoban solvers which are designed to solve much harder levels. It is not designed to find non-optimal solutions more quickly, and it can easily suffer from an exponential explosion of the search space when B is too large. It does not involve any clever/complicated heuristics since non optimal solutions are out of the question. I have also tuned it, and the competition parameters together, so that most submissions will be processed using relatively modest time and memory resources that are available to the site server. However, specially at the larger parameters, it would be possible to design levels that would take too much memory and processing time. Those levels actually are probably ones where the search tree is too fat, hence I do not expect them to have particularly good score. Anyway, in this contest, if the scorer program exhausts its fixed pre allocated memory area on your submitted level, this level would NOT be considered legal and an error would be produced. If you think that you have found an actual Bug in the program, please contact me, with your input level, and I will try to resolve the issue.

The source of the scorer program (minus the database check and other server related code) is included here, and it is highly recommended that you use it, as a starting point in your efforts. You can of course modify the code as you please. I included it, also as an incentive for contestants to build it and run it locally, which would be much faster than using the server, which is a virtual machine hence probably much slower than a 4 year old laptop. The source has the same memory limitations as the server scorer, so you can also check that your level is legal in that respect too before submitting it.

Except for the embedded comments in the source, no further help/support about the code, its design, and how to build and use it, will be provided from its author. It's supposed to be also a programming contest after all. Good luck!

The Discussion Group

If you want to enter the contest, it is recommended that you join the contest's discussion group. If you do not have a yahoo mail, you can join the mailing list interface by sending a blank e-mail here. The discussion group allows you to keep in touch with the other contestants, share ideas on attacking the problem, and hopefully will create a community, raising the level of everybody. It is also the preferred method of getting your questions answered (but look first at the FAQ below), and getting help about the site and the contest's rules.

Frequently Asked Questions