Most Efficient Way to Digitally Store CubeStates?

Discussion in 'Puzzle Theory' started by Chree, Feb 10, 2016.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. Sort of a side note; if you wanted to store the entire 43 quintillion cube states, you could further reduce that using all the rotations (both sorts) reflections and inverses to reduce by a factor of 2^3*2*24*6~2300 unless I for my calculations wrong somewhere if you add a certain tag at the front to show rotation/reflection which would be 10 bits long I think tough it may be possible to reduce that further.
     
  2. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    Since the position of the last two edges is forced you can use a EP* from 0 to 12!/2 -1 by combining the index of the combination of 10 edges (Binomial(12,10) possibilities) with the 10! possible permutations of these 10 edges (Binomial(12,10)*10! = 12!/2). I used this kind of coordinate several times in my programs. This saves 1 bit.
    Of course you can now build the total Index for example with

    3^7(8!(2^11 EP*+EO)+CP)+CO

    and you get an unique index from 0...43252003274489856000-1 for each cube, which needs 66 Bits.
     
  3. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    This will not help. Your tag bits will eat up your savings by the reduction. It is impossible to get below Log[2,43 quintillion] bits.
    Btw. the reduction factor by symmetries and inversion is only 96, not 2300.
     
    Last edited: Feb 12, 2016
  4. hamfaceman

    hamfaceman Member

    219
    39
    Aug 9, 2015
    Melbourne, Australia
    WCA:
    2015MONC01
    I think you guys may be overthinking this. How about a scramble sequence?
     
  5. That has come up. It's less efficient than some of he other methods and would also mean you need to gen all of the algs foe all of the cases and store them in binary.
     
  6. EMI

    EMI Member

    844
    23
    Apr 23, 2011
    Germany
    WCA:
    2011RHEI01
    YouTube:
    EMI94100
    The efficiency of your representation depends on what you want to do with it. The length of the shortest possible (binary) representation is obvious. (Btw, too bad that it is 66 (65?) bits, not 64...)
    But to make calculations fast, you want to store a state as some bit string(s) in such a way, that simple bit operations made up from AND, OR, XOR etc. and some constants can represent single moves, as well as the "concatenation" of two different states maybe.
    I have wondered before how those fast solving programs (Cube Explorer, ...) implement it, but I was too lazy to find out. ^^
     
  7. RicardoRix

    RicardoRix Member

    127
    2
    Jul 29, 2013
    WCA:
    2013LEIS01
    That's not true. Whatever is deemed 'human readable' has not be defined, but if you encode a scramble then the 'decoder' method (and everything suggested so far would need some kind of decoder) would just give you a scramble, no need for any kind of 43q lookup.

    hamfaceman maybe talking about storing the scramble sequence without any compression at all, and so then would not need any kind of decoder to be human readable, would need a few more bytes though, but even so would be an efficient solution for this scenario.
    Also a coded scramble (19 different types of move (5 bits), 20 moves = 100 bits = 13 bytes) and very easily decoded, no lookup, the same is true for your BLD method, and also makes it more efficient than the 14 bytes you quoted earlier.
     
  8. SenorJuan

    SenorJuan Member

    361
    169
    Sep 26, 2014
    U.K
    If you're describing a scramble sequence, then after the first turn (18 possibilities = 5 bits) you have less options for the subsequent move: just 5 faces & 3 rotation choices = a 4-bit number. Then a 20-turn sequence would be 5 + 19 x 4 = 81 bits long.
     
  9. RicardoRix

    RicardoRix Member

    127
    2
    Jul 29, 2013
    WCA:
    2013LEIS01
    Fair enough, very clever. I was considering a 'no-move' for the 19th different type of move, but if you go to that extent I suppose the length of the data could deal with no-moves.
     
  10. SenorJuan

    SenorJuan Member

    361
    169
    Sep 26, 2014
    U.K
    I guess you would choose the 'unused' 16th value to define a no-move, and hence end-of-scramble. And ditto, one of the many spare states for the first move could be used to represent no-move, ie. the cube is solved, without needing any turns.
     
  11. rokicki

    rokicki Member

    254
    3
    Oct 31, 2008
    I have to ask, why do we need a particularly concise representation? If you're not storing many positions, the
    difference between a cubie representation (20 bytes, one per cubie, each holding a value of 0..23) and a 66-bit
    index (which generally really takes 128 bits or 16 bytes due to alignment) is not a big deal.

    Directly indexing positions has a certain elegance, but it's not too far from just lexicographically ordering a
    working cubie representation.

    The cubie representation permits operations such as moves, inversions, reorientations, and direct position
    multiplication (pretty much the standard group operations). And it's pretty quick to turn into an index, or to
    derive from an index.

    So if the reason you want such a concise representation is to store many many positions, then you get into
    ideas of how to efficiently store a finite subset of a large finite set, or conversely, how many distinct
    elements you can store in a given amount of memory. While you can't do a whole lot better than 66 bits
    per, you can do somewhat better, depending on the operations you need to perform and their required
    relative speed.

    For instance, to store 200M positions (say, known distance-20 positions) concisely, you
    might just index them, sort the indices, and then break them out into about 5000 separate lists by the
    leading 13 bits, reducing the bit count of each entry to about 53 bits (and paying a small amount of
    overhead for the required datastructures to keep track of this information). If access speed is not important,
    you can just encode the delta between adjacent entries in a big sorted list; this would probably be about 40
    bits per position (using Huffman or arithmetic coding to encode the bit length of each entry).

    But you have to ask yourself if saving 26 bits out of 66 or about 40% is worth all these heroics.
     
  12. Bruce MacKenzie

    Bruce MacKenzie Member

    9
    1
    Sep 3, 2017
    There are 4.33 x 10^19 3x3x3 cube positions. One may map each cube position onto the integers and uniquely represent a cube state in I think 65 bits. This is commonly done to index pruning tables based on cube subgroups using some kind of radix compression scheme. For example the configuration of the corner cubies may be represented by the number:

    ... 15 * (18 * (21 * {0 to 23} + {0 to 20}) + {0 to 17} ) + {0 to 14} ) ...

    The first corner may in any of 24 states numbered 0 to 23, leaving the second corner any of 21 states, ect.
     
    Last edited: Sep 4, 2017
  13. This was discussed earlier in the thread but was ruled out as an answer to the problem as envisioned by the op pretty early on.
     
  14. Bruce MacKenzie

    Bruce MacKenzie Member

    9
    1
    Sep 3, 2017
    The point being made is that a representation of a cube position requires a minimum of 65 bits. Any scheme requiring more than that is not as efficient in terms of space. Any scheme using less than that will not be able to represent all possible states.

    Woops, I went to the calculator and found that it requires 66 bits, not 65.
     
    Last edited: Sep 4, 2017
  15. I agree that it is not as efficient in terms of space though the op stated he wanted a somewhat "human-readable" way of storing the infomation rather than just assigning each state a number (though again that is the most efficient way to store cubestates).

    A way of getting the mapping on the cubestates is by using the devil's algorithm and assigning each state a certain distance along the cycles.
     
    Last edited: Sep 4, 2017
    Bruce MacKenzie likes this.
  16. Bruce MacKenzie

    Bruce MacKenzie Member

    9
    1
    Sep 3, 2017
    A cube simulation will have a "usable" representation of the cube. Commonly, the simulation will have a representation which specifies the position and orientation of the eight corner cubies and the twelve edge cubies. The simulation has routines for graphically rendering the representation to the display. It can apply face turns to the representation, multiply two representations, etc.

    Anyway, if it becomes necessary to store cube positions in a minimum of space the algorithms for mapping such a representation onto the integers 0 to 43,252,003,274,489,855,999 are straightforward.
     
  17. Bruce MacKenzie

    Bruce MacKenzie Member

    9
    1
    Sep 3, 2017
    You're correct that if the configuration is saved in a structure such as below the structure uses 16 bytes.

    struct configuration{ uint8 rump; uint64 radix; };

    However, the data may be stored in 9 bytes if a 9 element array of uint8 is used instead. i.e

    struct configuration{ uint8 bytes[9]; } foo ;

    uint64 *radix;

    radix = (uint64 *)foo.bytes;

    permutationIndex = *radix;

    orientationIndex = permutationIndex % MAX_ORIENTATION_INDEX;

    permutationIndex = 4 * (permutationIndex / MAX_ORIENTATION_INDEX) + foo.bytes[8];
     
  18. Bruce MacKenzie

    Bruce MacKenzie Member

    9
    1
    Sep 3, 2017
    The best human readable representation I've run across is that of Michael Reid who wrote one of the first optimal solvers 15 or 20 years ago. His represented the cube as a facelet permutation. The representation for a solved cube is:

    UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

    and an example of a scrambled cube would be:

    DR FL FD UB DL LB UL BD BR RF UR UF LFU BDL RFD URB LDF DBR LUB FRU

    This specifies that the down_right cubie is in the up_front slot with the down facelet in the up position. The front_left cubie is in the up_right slot with the front facelet in the up position, and so forth. Stripped of spaces this rep uses 48 bytes.
     
  19. CuberFles

    CuberFles Member

    3
    0
    Sunday
    But 48 bytes is like 384 bits, not at all efficient :?
     
  20. Bruce MacKenzie

    Bruce MacKenzie Member

    9
    1
    Sep 3, 2017
    Not efficient but it is human readable. Also, it may be directly used to represent the cube as a facelet permutation. One may then use permutation multiplication to model cube manipulations.

    ...........................1..............2.............3.............4
    Index.........12 34 56 78 90 12 34 56 78 90 12 34 567 890 123 456 789 012 345 678
    Slot..........UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
    Configuration.DR FL FD UB DL LB UL BD BR RF UR UF LFU BDL RFD URB LDF DBR LUB FRU

    Facelet Permutation (GAP Canonical Cycle Notation):
    (1,11,24,2,12,23)(3,19,18,22,4,20,17,21)(5,10,16,13,7)(6,9,15,14,8)(25,35,29,43,33,37,42,48)(26,36,30,44,31,38,40,46)(27,34,28,45,32,39,41,47)
     

Share This Page