Message #1675
From: David Smith <djs314djs314@yahoo.com>
Subject: Re: [MC4D] Re: Goldilock’s function
Date: Mon, 09 May 2011 05:24:56 -0700
Whoops! I made an obvious error when I said, "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."
I don’t know exactly why I said that. I just now realized that if we do *not* count
fixed centers in our counts of nStickers, nPieces, and n1CStickers, then the
formula will be more accurate. Melinda, I apologize for this oversight. But, if it
is easier to keep the formula the way it is, I’m fine with that, as the difference
between the current formula and this new improved one would be negligible,
and besides by keeping it the way it is, we are slightly overcounting, which is
safe. Also, your program no doubt has functions for the three functions involved
already, and they would have to be modified, making the formula more complex.
I’m fine with overcounting if you are, and it only affects pieces with fixed centers.
All the best,
David
— On Mon, 5/9/11, David Smith <djs314djs314@yahoo.com> wrote:
From: David Smith <djs314djs314@yahoo.com>
Subject: Re: [MC4D] Re: Goldilock’s function
To: 4D_Cubing@yahoogroups.com
Date: Monday, May 9, 2011, 6:36 AM
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
<br>
<br>
<br>
-----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—–