Puzzle comparisons

19 posts / 0 new
Last post
WayneCa
Offline
Joined: 2014-07-13
Puzzle comparisons

I began my comparisons of the original puzzle collection with the boxxle 1 & 2, perfect and revenge puzzle collections using Sokoban YASC's duplicate finder. I have gotten SokoDup to run also, so I have included it in my comparisons also. Then I compared the results of both to each other. What follows is what was found, and what was not, by both programs. I have included the notes I placed at the beginning of the file I have attached to this post for your perusal. Because the output of SokoDup was easier to manipulate for this purpose, I chose to use it instead of the output from YASC duplicate finder. I will make that file available to anyone who requests it.

To make this all easier to understand, I have included a file that displays all of the duplicates found for each puzzle that has duplicates. It is loadable into the sokoban engine of your choice, as it is in standard sokoban level file text format. It uses the Sokoban YASC variant of this file format and originally had the .sok file name extension. I renamed it Duplicates.txt so I could upload it here. The puzzles it contains are not intended to be played. This merely makes it easier to grasp by displaying it the way puzzles are displayed in these game engines. It contains the 34 original puzzles that have duplicates.

I used the tribute file (Sokoban_Original_Puzzles_Tribute.txt) instead of the XSokoban file (Original.txt) because the tribute file contains all of the variants found in all 3 of the original games by Spectrum Holobyte and the original game by Spectral Associates, resulting in 64 puzzles instead of 50.

I shortened the name of the tribute file so I would not have to type such a long name into the command line. I moved the totals to the top so you wouldn't need to scroll to the bottom of the list to see them. Also included are corrected totals after accounting for all the duplicates missed by SokoDup.

Note that SokoDup and YASC Duplicate finder both missed the exact same duplicates.

I separated the unique entries found by SokoDup from the duplicate entries for easier study. Where a duplicate was identified as unique I put the original level number and title of that puzzle to the right of the entry. Where a duplicate was skipped in the duplicates section, I placed boundaries around the entry with notes to the right for easier study.

I had to wrap the lines to make this fit in the post. Using code tags to get a mono-space font caused the right side to go beyond the right margin of the post.

Examples: Unique entries that are not exactly unique: 7 *** 10 is unique Level 10 Color Computer 8 *** 11 is unique Level 10 MS-DOS, Apple II, Commodore 64, XSokoban Entry for duplicate not found: ---------------------------------------------- SokoDup did not find this 10 Level 10 Color Computer ~= 11 *** Level 10 MS-DOS, Apple II, Commodore 64, XSokoban ============================================== Entry for unusual entry where it seemed it was not necessary to insert two entries: ---------------------------------------------- don't know why SokoDup did this dup(4) 12 == 166 from Perfect.txt Level 11 Color Computer, MS-DOS, Apple II, Commodore 64 == 65 from Boxxle-01-(108).txt dup(5) 13 ~= 166 from Perfect.txt Level 11 XSokoban ~= 65 from Boxxle-01-(108).txt ~= 12 *** Level 11 Color Computer, MS-DOS, Apple II, Commodore 64 ============================================== Entry where SokoDup found some, but not all, duplicates: ---------------------------------------------- SokoDup found this dup(6) 14 == 171 from Perfect.txt Level 12 Color Computer, MS-DOS, Apple II, Commodore 64 == 71 from Boxxle-01-(108).txt ---------------------------------------------- but not this ~= 15 *** Level 12 XSokoban ==============================================

The notes may be easier to read and study in the file.

Enjoy.

ben
Offline
Joined: 2012-04-02

level 10 and 11 are clearly different, why do you expect them to be the same?

They are similar.

Sokodup is designed to find SAME levels, not similar level.
(the only similar level that does it when levels are the same except for the player's position)

Also, it would be nice if you also upload the SokOriPuzTrib.txt file to make reading the output better.

The Duplicates.txt file is very hard to read.
Yes, you may find it easy to read them side by side in TEXT.
But I find it very difficult to see.
Levels are best viewed graphically and compared graphically.
It's better to list the levels one after another, that way it's much easier to compare them graphically using programs, not looking at the ASCII TEXT.

WayneCa
Offline
Joined: 2014-07-13

Actually, sokodup and YASC duplicate finder do find similar puzzles. In sokodup they are shown with ~=. I know the documentation says it only detects different player position as similar, but that is not the only similarity two puzzles can have.

The Duplicates.txt file is meant to be viewed from in your preferred sokoban engine. Load it the same way you would load a collection you intend to play.

The levels skipped should be seen as similar. If sokodup only sees difference in player position then it is not seeing all possible similar puzzles. You will see what I mean when you view the duplicates.txt levels within your sokoban engine.

The puzzles in Duplicates.txt are 45 cells wide by 45 cells tall, and should be view-able in any sokoban engine that displays 50x50 puzzles (except for the puzzle 42 comparison, which requires a wider display due to having 6 levels compared in 2 rows of 3). As an example, here is the level 10 comparison from Duplicates.txt:


  

Again, these puzzles are not intended to be played, only viewed so you can see the similarities. I have attached the sokoban tribute file for you.

As to sameness, using level 10 as an example, while the solution to the left puzzle may not be valid for the right puzzle, the solution to the right puzzle is valid for the left puzzle. In my opinion, if a solution is transferable even in one direction, the puzzles are the same. Likewise, if the only difference is the placement, addition or removal of one or two boxes/goals or wall blocks, the puzzles are similar, if not the same.

attachment: 
ben
Offline
Joined: 2012-04-02

Well, the problem is, when you view the level like this in a quad setup, you cannot really compare the levels -- not to mention that you also removed the player from each of the levels, making it impossible to know where the player was in the original level.

The best way to compare any two levels graphically is to load the level and then toggle back and forth between the levels.
This way, it's very easy to see what exactly is changed.

Sokodup is designed to find SAME levels.
For similar levels, the best tool is SokoFind.
But Sokofind is not designed to compare level sets.
It is only designed to find similar levels in your entire collection, and it only works for one level. It is not designed to batch process an entire collection.

ben
Offline
Joined: 2012-04-02

>>> if a solution is transferable even in one direction, the puzzles are the same

NO, a solution that works for both levels doesn't necessary say both levels are the same.

Even if a solution from level A works for Level B, and a solution from Level B works for Level A, it doesn't make them the same.
It only says that one solution solves both levels.

Solutions work very differently than "Math Set".
(i.e. if A is a subset of B and B is a subset of A, then A=B.)
So, forcing this idea that one solution works for another and make them the same (Or even similar) is totally incorrect.

You can easily design levels that looks very very different where the solutions are the same.
Imagine this, you level A, with 100 boxes, where you just make one push (say right) to finish the level.
Then you have this so-called classic "first" level:

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

where you also make one push and it solves the level.
Are they the same?
Are they similar?

I would think not.
Level A can also have a solution that's 20 moves to solve, or millions to solve. Having same solutions doesn't make them the same level.

ben
Offline
Joined: 2012-04-02

Just went thru the comparisons using Sokodup, I don't see anything wrong.
The unique levels are unique.
The levels that are the same are the same.
What you considered as similar is not what SokoDup considered as Similar level.

Also, you wrote:

Entry for unusual entry where it seemed it was not necessary to insert two entries:
---------------------------------------------- don't know why SokoDup did this
dup(4) 12 == 166 from Perfect.txt Level 11 Color Computer, MS-DOS, Apple II, Commodore 64 == 65 from Boxxle-01-(108).txt
dup(5) 13 ~= 166 from Perfect.txt Level 11 XSokoban ~= 65 from Boxxle-01-(108).txt ~= 12 *** Level 11 Color Computer, MS-DOS, Apple II, Commodore 64
==============================================

To me, it's very clear.
It's saying that level 12 from SokOriPuzTrib.txt, is exactly the same level as level 166 from Perfect.txt, it is also the same as level 65 from Boxxle-01-(108).txt.

Further, it's saying that level 13 from SokOriPuzTrib.txt, is the SAMEX level as level 166 from Perfect.txt, it is also the SAMEX as level 65 from Boxxle-01-(108).txt and it's also the SAMEX level 12 from SokOriPuzTrib.txt.

SAMEX (using the symbol ~=) -- I just use this as place holder to mean same level except player's position was different but has a clear path between.
(basically means level is the same, just the beginning moves are different to make the first push)

All of these are very clear.

Remember that Sokodup is comparing the level with every level in the collection and every level it has read in the current file.

ben
Offline
Joined: 2012-04-02

I want to stress again, SOKODUP find same levels and levels with player moved.

There are options to compare without internal walls etc, but those should not be used to compare whether levels are the same or similar. Those options are for special use purposes and not for finding same or similar levels.

Usually, when people say similar levels, they are referring to levels that look almost the same, but not. With walls, boxes, or rooms added, level were changed to be bigger or smaller. In short, level was changed in some way but still recognizable.

Sokodup does not find similar levels, period.

Similar levels should never be treated as SAME -- even if they are 99.99% the same.

WayneCa
Offline
Joined: 2014-07-13

Well, the problem is, when you view the level like this in a quad setup, you cannot really compare the levels -- not to mention that you also removed the player from each of the levels, making it impossible to know where the player was in the original level.

The best way to compare any two levels graphically is to load the level and then toggle back and forth between the levels.
This way, it's very easy to see what exactly is changed.

I think I failed to add that in order to make the puzzle loadable without a player start point disappearing I replaced all player start positions with boxes on goals and placed the player at the center of the grid. If you are familiar with the puzzles then you will know where the start positions are and you can tell by looking if one of the puzzles shows a different start point. While one of the puzzles (maybe 2) have boxes on goals at the start, the start positions for these puzzles is not in the goal area and should be easy to identify.

I made these this way for visual comparison. You can easily tell where the differences are, and much more quickly, seeing them together than when having to go back and forth between puzzles to examine them. If the puzzles seem small, expand the window to maximized, or full screen if it is available and maximized does not scale the puzzle up. I am using Sokoban YASC on a laptop with a resolution of 1280x800 and I can tell the differences with the window at it's normal size (although i did enlarge the window some so it already scaled them up abit).

I have viewed them in YSokoban, and I can tell the differences at the default window size. If you are not familiar with the puzzles, or just have an issue with seeing, just maximize the window and the puzzle will be scaled up, making it much easier to see the detail. I. myself, have issues with seeing. I am extremely nearsighted, but not so much that I cannot see the puzzles. I do have issues with reading and text size, however, which is why I prefer the graphical approach over comparing text.

Sokodup is designed to find SAME levels.
For similar levels, the best tool is SokoFind.
But Sokofind is not designed to compare level sets.
It is only designed to find similar levels in your entire collection, and it only works for one level. It is not designed to batch process an entire collection.

I compared Original to Boxxle 1 & 2, Perfect and Revenge. SokoDup handled this very well. To say that it does not (or is not intended) to find similar levels is not correct, as the ~= (roughly equal or similar) equality token does exist within it.

YASC has, as part of its duplicate finder function, a sub-function for finding similar puzzles that differ in other ways besides start position change. (I believe that some of the options for SokoDup are intended for the same purpose.) These work on an individual puzzle and not a collection as a whole, but it can be used with the different puzzles you want to check for similar puzzles with. It sounds as though SokoFind does the same thing as the YASC duplicate finder similar puzzle sub-function. It is precisely because it only processes a single puzzle and does not allow for processing an entire collection set that I have not used it more.

WayneCa
Offline
Joined: 2014-07-13

>>> if a solution is transferable even in one direction, the puzzles are the same

NO, a solution that works for both levels doesn't necessary say both levels are the same.

...

It is easy to make that comparison as a one move/push solution is the easiest there is to duplicate with an extremely different puzzle. However, the more complex the solution the less likely it is that another more different puzzle will duplicate that solution. There is a chance that it may, in some part, duplicate the solution, but not as the entire solution. However, we are not talking about those kinds of puzzles.

We are talking about puzzles that are known to have a more unique type of solution, and one for which duplicating it in an altogether different puzzle would be more work than anyone would want to put into to designing such a puzzle. In addition, we are talking about puzzles where the similar puzzle is so close to being the same puzzle in look that someone who is not familiar with it would think it was the same puzzle when they saw it.

WayneCa
Offline
Joined: 2014-07-13

Just went thru the comparisons using Sokodup, I don't see anything wrong.
The unique levels are unique.
The levels that are the same are the same.
What you considered as similar is not what SokoDup considered as Similar level.

That I see some puzzles as similar that SokoDup does not was never disputed.

Also, you wrote:

...

I understand now. I had thought that, since SokoDup could parse through the file, that it would parse ahead in its comparisons before going through the other files being compared to. I see now that it is more backward looking in respect to the same file being read.

I had been thinking that something like this was possible:

dup(4) 12 == 166 from Perfect.txt == 65 from Boxxle-01-(108).txt ~= 13 ***

It would have saved an entry and still given the same data.

WayneCa
Offline
Joined: 2014-07-13

I want to stress again, SOKODUP find same levels and levels with player moved.

There are options to compare without internal walls etc, but those should not be used to compare whether levels are the same or similar. Those options are for special use purposes and not for finding same or similar levels.

Usually, when people say similar levels, they are referring to levels that look almost the same, but not. With walls, boxes, or rooms added, level were changed to be bigger or smaller. In short, level was changed in some way but still recognizable.

Sokodup does not find similar levels, period.

Similar levels should never be treated as SAME -- even if they are 99.99% the same.

I understand what you are saying. I'm not trying to put something into it that is not there. I merely have a different idea of what sameness and similarity are. For example, the puzzle we were recently discussing, Boxxle 1 hidden.

The only difference between that puzzle and Perfect 303 is one corner wall block was removed in 303, and one corner floor space was changed to a wall block in 303. To me, those puzzles looked identical, and it took me awhile to find the difference. The solution to Perfect 303 will solve Boxxle 1 hidden, but the solution to Boxxle 1 hidden will not solve Perfect 303.

The fact that the hidden solution will not solve 303 makes them similar, but not the same. However, because the solution to 303 will solve hidden, that makes them the same. Because they look so similar as to cause confusion until the difference has been spotted makes them almost identical.

While a program such as SokoDup may not be geared for such determinations, we humans (being visually oriented) are geared that way. At some point, we must make room for the human determinations, even if the machine determinations disagree.

Pages