Message #422

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] a few thoughts on "post processing" solutions to make them shorter
Date: Sat, 08 Sep 2007 18:30:14 -0700

Roice,

Yes, Don and I have thought a good deal about this subject. He even
wrote a history compression method that is currently being used to
optimize both his generated true solutions and the "cheat" solutions
prior to playback. I toyed with the idea of performing an automatic
compression prior to saving to log files but felt that might confuse and
frustrate some solvers who might not recognize the modified version of
their work when they return to working on a solution. I suppose that it
could be added as a run-time option, command line option, or stand-alone
file compressor program. It does attempt to combine all twists on a
given slice of a given face and to transform them into a single twist.
It also attempts to "compile out" all rotations and to remove several
types of redundancies. I think it still has a couple of problems but Don
would need to talk to that.

We’d also talked about implementing a state hashing algorithm like you
describe which would definitely be the ultimate in removing loops. If
you do decide to implement something like this I think you may want to
search not just for the earliest identical puzzle states but also for
ones that are symmetric (isomorphic?) to the current state.

I wonder whether this sort of approach might also point the way towards
a possibly very efficient computer solution to puzzles of this type.
Imagine a solution as a series of beads along a string from a scrambled
state to the pristine state. Since the diameter of the complete graph of
all connected states is probably much shorter than any typical
algorithmic solution, you can imagine solution strings are twisted
rather badly and contain lots of "slack" compared with the equivalent
god’s algorithm which probably produces rather straight strings through
this space. Compressing same-face twists and trimming out loops are
operations that result in shorter strings. Perhaps there are other
similar operations that locate kinks in the strings which don’t quite
form complete loops but that can be bridged with much shorter splices of
string. Maybe you can’t find a practical implementation of god’s
algorithm this way but I can definitely imagine an iterative method that
might be able to slowly "tighten up" these strings into lengths that are
not too far from it.

-Melinda

Roice Nelson wrote:
>
> I haven’t yet looked at the moves in my last logfile for extraneous
> twists as Remi had done. Seems there could be a couple of "post
> processing" optimizations one could do.
>
> One check would be to look for multiple sequential moves on a single
> face that could be combined into one. This may be what Remi was
> looking for as he went through twist by twist?
>
> Another check would be to catch preliminary moves that effectively
> countered preliminary moves from previous sequences, resulting in
> duplicate puzzle states. This would be hard for a human to spot using
> the log files, but… this is something a computer would be very good
> at. It could check the state after each move and store it and the
> associated move number in a container ( e.g. a list or hashtable). As
> it ran through the moves, if it ever found a puzzle state that already
> existed in the list, it could remove all the unnecessary twists which
> had only served to bring the puzzle back to a place it already had
> been. I may take a gander at writing such a function sometime.
> Though I don’t think it would make any significant difference in the
> length of my latest solution, it would help ensure all "the fat had
> been trimmed."
>
> I did notice the new MC4D does a little optimizing along these
> lines for you, in that a move which is the reverse of the previous
> move doesn’t append the log, and instead removes the previous move. I
> liked this. I also noticed the move must by physically the opposite,
> not logically the opposite (you need to do a reverse click on the
> exact same sticker). A state check function would catch logical cases
> as well, and be able to catch arbitrarily long sequences that returned
> someone to a previous state.
>
> Hope this finds everyone well,
>
> Roice