# Message #1674

From: David Smith <djs314djs314@yahoo.com>

Subject: Re: [MC4D] Re: Goldilock’s function

Date: Mon, 09 May 2011 03:36:37 -0700

Hi Brandon,

Thanks for writing, and I hope you are starting to feel better! No worries for

taking your time, and I hope you are well soon.

To clarify, my formula does account for the percentage of pieces moved in a twist.

Otherwise it would not work at all! :) I approximate this number as best as I can,

and for some puzzles it is more accurate than others. Please remember that making

my formula work for all puzzles is not a priority right now; I am dedicated to making

it as accurate as possible for all of our higher-dimensional puzzles in the programs

Melinda, Don, Roice, Andrey, and others have made for us (but only Melinda

specifically requested this).

The problem with making my formula work for all puzzles is that for many puzzles

there is no single value for the number of pieces in the puzzle that move in a single

twist. Many puzzles have differently shaped faces, for example the duoprisms.

But the real issue lies in slice moves. Slice moves affect far fewer pieces on many

large puzzles, such as the n-cube. And the n-cube is one of the most important

puzzles to implement as accurately as possible.

This would be the ideal formula for AveNumTwists:

AveNumTwists = (nPieces/(number of pieces moved in an average twist))*

(0.577 + ln(nPieces)

But the number of pieces moved in an average twist is very hard to calculate for

all different puzzles via a single formula. Some puzzles will have many slice moves,

such as the larger cubes, others will have none, such as the Pentultimate and the

Starminx, some will have few slice moves, such as the dodecahedral prism, some

will have many, etc.

My current formula works by treating the puzzle as if it has slice moves and

calculating the number of pieces moved in a such a move. It does this via the number

of 1-colored pieces. This approximation works very well, as for larger cubes if we

used a face move, the count would be far too low. For MC4D puzzles with no or few

slice moves, such as the 120-cell, it is not too far off because such puzzles usually

have few 1-colored pieces per face, and many other types of pieces, and are of

small order. The 120-cell has 2740 pieces, and only 120 of them are 1-colored,

making the slice move count negligible. And there are no 120-cells of order

larger than 3, and there really can’t be, just as for all puzzles with no slice moves,

for if there were, slice moves would be required to move the inner 1-colored pieces.

Note that both the Starminx and Pentultimate are special cases - they each do

not have any slice moves, while at the same time having a large ratio of 1-colored

pieces to total number of pieces, due to their small order and unique design.

However, it is now clear how we can fix the formula for those two puzzles! Since

there are no slice moves, we simply remove the ‘minus n1CStickers’ in the formula!

We get a new formula for AveNumTwists:

AveNumTwists = (nPieces*nFaces/nStickers)*(0.577+ln(nPieces))

Now, let us see how our modified formula works for the Starminx and the

Pentultimate:

Starminx: 131 moves

Pentultimate: 54 moves

These numbers should be much more accurate. I actually felt that your

estimates for the Starminx and Pentultimate were too high prior to these

calculations (especially considering that the Pentultimate only has 32 pieces;

I think 80-100 moves would be too many). Normally that would just be my

opinion, but in this instance the mathematics seems to back it up. No

offense intended!! You were probably just making a rough estimate, and

perhaps you will agree that my formula now gives very accurate results for

these two puzzles.

Thanks again for writing! When Melinda deems it appropriate, I will be happy

to provide further explanation of my formula.

All the best,

David

— On Mon, 5/9/11, Brandon Enright <bmenrigh@ucsd.edu> wrote:

From: Brandon Enright <bmenrigh@ucsd.edu>

Subject: Re: [MC4D] Re: Goldilock’s function

To: 4D_Cubing@yahoogroups.com

Cc: damienturtle@hotmail.co.uk, bmenrigh@ucsd.edu

Date: Monday, May 9, 2011, 1:37 AM

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