View unanswered posts  View active topics

Page 1 of 1

[ 7 posts ] 

Author 
Message 
contrabass

Post subject: Puzzle Branching Factors (Mathy post) Posted: Tue Oct 15, 2013 6:32 pm 

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 nfold symmetry around a face, then the face has n1 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 4truncated Rhombic Dodecahedron: 10.70522820695193 3truncated Rhombic Dodecahedron: 8.948422488554135 5truncated Rhombic Triacontahedron: 13.757663732948052 3truncated Rhombic Triacontahedron: big HemiDodecahedron: 9.040294042680404 HemiRhombic 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 


Brandon Enright

Post subject: Re: Puzzle Branching Factors (Mathy post) Posted: Tue Oct 15, 2013 6:56 pm 

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 


GuiltyBystander

Post subject: Re: Puzzle Branching Factors (Mathy post) Posted: Tue Oct 15, 2013 7:08 pm 

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 


Brandon Enright

Post subject: Re: Puzzle Branching Factors (Mathy post) Posted: Tue Oct 15, 2013 7:14 pm 

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 .
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


contrabass

Post subject: Re: Puzzle Branching Factors (Mathy post) Posted: Wed Oct 16, 2013 7:53 am 

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/(b1) b^k. For all of the puzzles given, that factor bc/(b1) 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 


Bram

Post subject: Re: Puzzle Branching Factors (Mathy post) Posted: Sat Oct 19, 2013 10:41 pm 

Joined: Sat Mar 22, 2003 9:11 am Location: Marin, CA

I don't follow why there are nonintegral 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 


contrabass

Post subject: Re: Puzzle Branching Factors (Mathy post) Posted: Sun Oct 20, 2013 9:34 am 

Joined: Sun Oct 28, 2007 5:23 pm

The branching factors are nonintegral 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 



Page 1 of 1

[ 7 posts ] 

Who is online 
Users browsing this forum: No registered users and 13 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


