Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Fri Jul 25, 2014 8:04 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Puzzle Branching Factors (Mathy post)
PostPosted: Tue Oct 15, 2013 6:32 pm 
Offline

Joined: Sun Oct 28, 2007 5:23 pm
A nice way of bounding by below the longest solution on a puzzle is by a counting argument, for example on a cube there are 18 possible moves and so if there are p positions, then the length of the longest algorithm k must be such that the number of move sequences of length at most k must be at least p. The factor of 18 on a cube also is the branching factor on a naive brute force search to solve the cube. Both of these can be improved by noting that on a cube, preforming LR is the same as performing RL, so if you only allow one of these orders, the branching factor can be improved to under 14. This gives a larger lower bound on God's algorithm and speeds up the brute force search by a large factor (although other tricks are still needed to get a reasonable search).

I was curious as to how this would work for other puzzles, such as the Megaminx, where the commuting moves don't nicely pair up. I came up with a technique where you keep track of which moves have been used recently. For example, if you turn one face, there is no need to turn that face again until one of its adjacent faces. This means that if you have a graph with a vertex for each axis and pairs of vertices are connected if they don't commute, one has to keep track of an independent set of vertices and update the set when you make a new move, removing all of the adjacent points from the set and adding the new one. Furthermore, to take care of fixing the order between two commuting moves, give each axis a number and only allow a move if no commuting move with a lower number is currently in the set. This gives a system of recurrences (possibly many) that can give the total number of unique moves up to a given length. This means that there is a solution to the system of recurrences that is a sum of exponentials, so I wrote a program to calculate the largest of them (the largest eigenvalue of the related matrix).

In summary, the list below gives the branching factors of various puzzles, taking the fact that certain axes commute into account. The value for the listed polyhedron is assuming that the puzzle has an axis for each face and that axes commute if they don't share an edge; for example, the value for octahedron works for a dino cube, but not a face turning octahedron. It is assumed that if the polyhedron has n-fold symmetry around a face, then the face has n-1 possible moves. Note that this doesn't take jumbling or fudging into account, so a rhombic dodecahedron has only one move per face and the hexagons on the truncated octahedron have only two moves per face. The entries listed with values of big had too many independent sets for my program to calculate, but were included in the table for completions sake. As far as I know, only a few of these were previously known.


Tetrahedron: 6.0
Cube: 13.348469228349533
Octahedron: 8.418307885893643
Rhombic Dodecahedron: 5.645751311064589
Dodecahedron: 26.480303433871622
Icosahedron: 9.897936961398141
Rhombic Triacontahedron: 6.319918428462637

Truncated Tetrahedron: 11.132631540166239
Truncated Cube: 20.659251569084045
Truncated Octahedron: 16.57073441219379
Cuboctahedron: 13.13554100759743
Great Cuboctahedron: 20.338639289994845
Truncated Dodecahedron: 35.95476263148417
Truncated Icosahedron: 22.163447213360012
Icosidodecahedron: 13.13554100759743
Great Icosidodecahedron: big

Half truncated Cube: 7.664546987461376
4-truncated Rhombic Dodecahedron: 10.70522820695193
3-truncated Rhombic Dodecahedron: 8.948422488554135
5-truncated Rhombic Triacontahedron: 13.757663732948052
3-truncated Rhombic Triacontahedron: big
Hemi-Dodecahedron: 9.040294042680404
Hemi-Rhombic Dodecahedron: 4.449489742783179

I will be glad to clarify points in what is surely a pretty opaque post. There are some other thing that I hope to add soon, such as more exact lower bounds on God's algorithm for some of the puzzles like the nxnxn cubes.

_________________
as in clarinet


Top
 Profile  
 
 Post subject: Re: Puzzle Branching Factors (Mathy post)
PostPosted: Tue Oct 15, 2013 6:56 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
contrabass wrote:
[...]The value for the listed polyhedron is assuming that the puzzle has an axis for each face and that axes commute if they don't share an edge
[...]
Dodecahedron: 26.480303433871622


Your commuting faces metric forces the puzzle to be very shallow. It should work for a Megaminx but it won't work for a Pyraminx Crystal. Any chance you can recompute for a few different cut depths?

For the 26.480303433871622 value, I assume I can do something like:

? log(((20! / 2) * (30! / 2) * (3^20 / 3) * (2^30 / 2)) / 48) / log(26.480303433871622) + 1
% = 47.609450523099887034349233643719026861

This calculation assumes 48 choices for the first turn and 26.480303433871622 choices for the remaining moves giving a lower bound of 49 moves. Does this sound right?

Edit: fixed the math a bit.

Edit 2:

If I'm doing this right, the Rubik's cube would be:

? log((((8! * 12!) / 2) * (2^12 / 2) * (3^8 / 3)) / 18) / log(13.348469228349533) + 1
% = 17.332166195062793503264859496466053047

Or a lower bound of 18.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Puzzle Branching Factors (Mathy post)
PostPosted: Tue Oct 15, 2013 7:08 pm 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
Great post and math. When I was working on my megaminx solver I used the exact same method to prevent redundant moves. I was only trying to test my turn rates so I didn't directly try to calculate the branch rate, but I can see how you did now. I only managed to guess ~26.50 after a depth 8 search.

Could you do the cube one again for higher order cubes like 4x4, 5x5, etc. ?

*slow poster so Brandon beat me*
bmenrigh wrote:
Your commuting faces metric forces the puzzle to be very shallow. It should work for a Megaminx but it won't work for a Pyraminx Crystal. Any chance you can recompute for a few different cut depths?
Yeah, deeper depth cuts for the dodecahedron would be interesting too.

bmenrigh wrote:
This calculation assumes 48 choices for the first turn and 26.480303433871622 choices for the remaining moves giving a lower bound of 49 moves. Does this sound right?
I could be wrong, but I think the 26.48 is the only number you should be using (don't ever use 48). It already takes everything into account. You don't really have 48 choices for the first move because if you want to do the move "CA" and the two faces aren't adjacent, you should be doing "AC" instead.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: Puzzle Branching Factors (Mathy post)
PostPosted: Tue Oct 15, 2013 7:14 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
There was a related discussion in this topic but I welcome the new discussion since there is probably a lot left to say in this area and I find the topic quite interesting :D .

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Puzzle Branching Factors (Mathy post)
PostPosted: Wed Oct 16, 2013 7:53 am 
Offline

Joined: Sun Oct 28, 2007 5:23 pm
Here are some more requested branching factors:
Deeper cut dodecahedron: 41.90890230020664
4x4x4: 20.730509637946682
5x5x5: 28.120978779040065
6x6x6: 35.51482296942452
7x7x7: 42.910355416554786
17x17x17: 116.88890151869273
Gigaminx: 54.890296106968144
Teraminx: 83.31590766854173
Petaminx: 111.74542596469087
Examinx: 140.17650715312683

As for the exact counting methods, the values given are such that the largest term of the expression for the total number of moves of length k is c*b^k, where b is the branching factor and c is some constant. Taking the sum from j=0 to k of c*b^j gives about bc/(b-1) b^k. For all of the puzzles given, that factor bc/(b-1) is between 1 and 3.3, and for the megaminx, the factor is 1.4426236265623917.
Solving for k to get the number of positions for the megaminx give k=47.67914174495091, giving the bound of 48. In essence, this extra factor changes the value by a small amount, so just taking the logarithm of the number of positions and dividing by the logarithm of the branching factor will probably be within 0.5 of the correct answer and so will be within 1 of the correct bound. For the cube, the additional factor is 1.6282550728636884, giving k=17.259410632386267, so 18 is still the bound.

_________________
as in clarinet


Top
 Profile  
 
 Post subject: Re: Puzzle Branching Factors (Mathy post)
PostPosted: Sat Oct 19, 2013 10:41 pm 
Offline

Joined: Sat Mar 22, 2003 9:11 am
Location: Marin, CA
I don't follow why there are non-integral branching factors. It seems like the branching factor should be the number of possible moves minus one. Some interesting branching factors if you go by that definition are that the Alternating Cube and Spider Gear have a branching factor of 2, and the Bramboules has a branching factor of 15.


Top
 Profile  
 
 Post subject: Re: Puzzle Branching Factors (Mathy post)
PostPosted: Sun Oct 20, 2013 9:34 am 
Offline

Joined: Sun Oct 28, 2007 5:23 pm
The branching factors are non-integral because they are a weighted average of branching factors taking into account some moves that have already been accounted for. In the cube example, guaranteeing that there is no RL move (only LR moves) means that at the start there are 18 moves, if you have just performed an L move, there are 15 possible moves, and if you have performed an R move, there are 12 possible moves. Those states each have a certain likelihood to occur in a random scramble, and taking those into account gives an average branching factor of about 13.35.

_________________
as in clarinet


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Anthony and 8 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group