# 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:

- -1 *(ln (BF% / 2)) / 3

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—–