Message #1670

From: Brandon Enright <bmenrigh@ucsd.edu>
Subject: Re: [MC4D] Re: Goldilock’s function
Date: Mon, 09 May 2011 05:37:37 +0000

—–BEGIN PGP SIGNED MESSAGE—–
Hash: SHA1


On Sat, 07 May 2011 13:42:00 -0000 or thereabouts "Matthew"
<damienturtle@hotmail.co.uk> wrote:


> Hi David, good to see you back.
>
> It’s an interesting formula you have there, and I would also like a
> bit of background on how you derived it. However, I may have spotted
> a little problem with it, and hopefully the feedback will help
> improve the formula, or prove to not be an issue. It was discussed
> that deeper cut puzzles would require less moves to scramble them,
> since twists affect more pieces, and will thus move pieces around the
> puzzle faster. However, the formula doesn’t quite bear this out for
> the various types of face-turning dodecahedra. I hope I haven’t made
> a numerical error here, if I have I apologise.
>
> Megaminx: 105 twists
> Pyraminx crystal: 81 twists
>
> So far so good.
>
> Starminx: 381 twists
>
> This is far deeper cut than a megaminx, but apparently takes over 3
> times as many moves to scramble? That result doesn’t seem correct.
>
> Pentultimate: 130 twists
>
> I hope I haven’t made a mistake, and made false accusations against
> your work. Perhaps there is a way to introduce another parameter,
> either for the number of pieces moved during a twist, or perhaps the
> ratio of pieces which are moved, to those which aren’t? Regardless,
> good work here :).
>
> Matt



Hi David,


I have been very ill so I haven’t had the energy to think about this a
lot or compose a very thoughtful message.


I think one thing you analysis doesn’t capture is the % of pieces are
moved in a single twist. For a puzzle like the Pentultimate where 50%
of the pieces move in a twist it doesn’t take many moves to scramble
the puzzle beyond recognition.


I’ve seen this referred to as the "branching-factor" because if you
imagine a tree where the solved state is the root node and the
next-most solved states are its children then the more pieces you are
forced to move in a single twist the farther away from the root you
will branch. I don’t have the time to make this argument more rigerous
but obviously in terms of branching factors the order would be
Megaminx < Pyraminx Crystal < Starminx < Pentultimate
as this just follows the cut-depth.


Especially troubling is that you require more moves to scramble a
Starminx and a Pentultimate than humans can solve them. Human
solving strategies are very inefficient compared to "god’s number" for
these puzzles. Based on intuition and a lot of computer searching
estimate god’s number for the Pentultimate is probably between 40 and
70 moves.


The deeper-cut the puzzle is the bigger the boost you get from each
random twist that you do.


Perhaps you can incorporate some factor like:



Where BF% is the number of pieces in the puzzle that move in a single
twist. The Pentutimate would have a value of .5 there. You’ll want to
play with this and the constants to see if it produces results that
you like.


I think you should shoot for a Starminx scramble at 200-250 moves and a
Pentultimate scramble at 80-100 moves. Your Megaminx and Pyraminx
Crystal numbers look good to me.


Brandon




—–BEGIN PGP SIGNATURE—–
Version: GnuPG v2.0.17 (GNU/Linux)


iEYEARECAAYFAk3HfagACgkQqaGPzAsl94JwGwCgxiVZXK22W328rKE+cA0mwdGs
zwwAn0rOijIppDsWYeHgi9gpfJeYpcfk
=Hv9q
—–END PGP SIGNATURE—–