coordinates.md (11762B)

1 # Cube coordinates 2 3 In this page I describe the way I implemented *coordinates*, in the 4 sense of [Cube Explorer](http://kociemba.org/cube.htm), in one of the 5 versions of [Nissy](https://nissy.tronto.net). 6 7 Unfortunately, this implementation got lost between rewrites and is 8 currently not included in any working version of Nissy or other projects, 9 so it this page is of theoretical interest only. Some code is available 10 in the [nissy-nx repository](https://git.tronto.net/nissy-nx), but it 11 is currently broken (what is described in this page works, though). 12 13 ## What are cube coordinates? 14 15 A *cube coordinate* is a way of associating to any legal position 16 of the Rubik's cube an integer in a certain range [0..n-1]. For 17 example, any way of encoding the permutation of the corners as a 18 number from 0 to 8!-1 is a valid coordinate; another example is 19 an encoding of the orientation of the edges with respect to a given 20 axis as a number in [0..2^11]. 21 22 In other words, a coordinate is a function from the set of legal 23 configurations to [0..n-1]. Coordinates need not be surjective, 24 though it is more convenient if they are, and in my examples they 25 will be. 26 27 To work with cube coordinates, we need to implement the following: 28 29 * An integer `n`, the maximum value of a coordinate +1. 30 * A function `index()` that takes a cube as input and returns an integer 31 in the range [0..n-1] as output. 32 * A function `to_cube()` that takes an integer in [0..n-1] as input and 33 returns a cube `c` such that `index(to_cube(x)) == x` for every x in 34 [0..n-1]. In other words, `to_cube()` is a *section* of `index()`. 35 In practice, it is not necessary that the output of `to_cube()` is a 36 valid cube object. 37 * A function `move()` that takes as input a coordinate, a move m and an 38 integer x in [0..n-1] and returns an integer y in [0..n-1] such 39 that `y == index(m(to_cube(x)))` (here `m(c)` is the cube c moved by m). 40 * If applicable, a `transform()` function that applies a transformation 41 in a similar way as `move()` applies a move. For coordinates this is 42 not possible, because they do not capture enough of the cube state. 43 For some coordinates, only some transformations are possible. For 44 example, for the edge orientation coordinate only the transformations 45 that fix the axis with respect to which the edge orientation is defined 46 can be applied. 47 48 For the implementation, see 49 [coord.c](https://git.tronto.net/nissy-nx/file/src/coord.c.html) 50 and 51 [coord.h](https://git.tronto.net/nissy-nx/file/src/coord.h.html), 52 as well as the definition of 53 [coordinate](https://git.tronto.net/nissy-nx/file/src/cubetypes.h.html#l181) 54 in cubetypes.h. 55 56 ## Coordinate types 57 58 In my work I have defined four types of coordinates (but I actually use 59 only three of them). 60 61 ### Basic coordinates 62 63 Basic coordinates are the simplest kind, and they are completely defined 64 by the integer `n` and the functions `index()` and `to_cube()` defined 65 above. This is the type of coordinate that "does not exist" in the code, 66 because they are just a special case of *composite coordinates*. 67 68 ### Composite coordinates (COMP\_COORD) 69 70 Composite coordinates are, like the name says, a composition of many basic 71 coordinates. They are given by a list of basic coordinates (n\_1, index\_1(), 72 to\_cube\_1()), ..., (n\_k, index\_k(), to\_cube\_k()). The value of such a 73 composite coordinate on cube c is computed as 74 `index_1(c) + n_1 * (index_2(c) + n_2 * (...))`. 75 76 ### Symmetric coordinates (SYM\_COORD) 77 78 A symmetric coordinate consists of a basic coordinate reduced by symmetry. 79 Symmetric coordinates must be initialized from a given set of *cube 80 transformations* before they can be used. The initialization step produces 81 the following data: 82 83 * A table that associates every possible value of the basic coordinate 84 with its class in the symmetric coordinate. Computing the value of the 85 symmetric coordinate will then amount to computing the basic coordinate 86 via `index()` and looking up the value in this table. 87 * A table that associates every possible value of the basic coordinate 88 with a fixed representative for its class. 89 * A table that associates every possible value of the basic coordinate 90 the cube transformation that brings it to its representative. 91 * A table that associates every possible value of the basic coordinate 92 with the list of cube transformations that do not affect it, that is 93 a list of *self-symmetries*. This will be useful when computing the 94 pruning table associated to this coordinate. 95 96 ### Symmetric-composite coordinates (SYMCOMP\_COORD) 97 98 A symmetric-composite coordinate is based on two other coordinates, a 99 symmetric coordinate and a composite coordinate. To compute the value 100 of a symmetric-composite coordinate one must compute the symmetric 101 coordinate value first, then transform the cube using the transformation 102 that brings the basic coordinate associated to the symmetric coordinate 103 to its representative in order to compute the correct value for the 104 composite coordinate, and finally combine the two. 105 106 More precisely and with less tong-twisting, for a given cube c one must 107 take the following steps: 108 109 * Compute the value x\_s of the symmetric coordinate at c, the value 110 x\_b of the *basic* coordinate associated with the symmetric coordinate 111 and the value x\_c of the composite coordinate. 112 * Read from the table the transformation t that brings x\_b to its 113 representative. 114 * Apply t to the composite coordinate value x\_c to obtain x\_t. 115 * Compute the value x\_s * n\_c + x\_t, where n\_c is the maximum value +1 116 of the composite coordinate. 117 118 ## Moving coordinates 119 120 A move is applied to a coordinate by lookup into a transition table, 121 pretty much as explained in Jaap's 122 [computer puzzling page](https://www.jaapsch.net/puzzles/compcube.htm#trans). 123 These transition tables are initialized once and for all at the beginning, 124 and in my implementation I actually saved them to a file to speed up 125 subsequent runs. 126 127 Some extra care has to be taken in dealing with symmetries. 128 129 ### Basic and composite coordinates 130 131 This case is quite simple: the transition table with something along these 132 lines: 133 134 ``` 135 for i in [0..n-1] 136 for m in Moves 137 move_table[m][i] = index(m(to_cube(i))) 138 ``` 139 140 ### Symmetric coordinates 141 142 As mentioned above, this case and the next are tricky, because we need 143 to keep track of which transformation has to be applied to get from the 144 representative of the symmetry class to our actual cube. 145 146 You can imagine a move applied to symmetric coordinate as if we just 147 move between different representatives. The actual cube can be recovered 148 from this by keeping track of an *offset transformation*, and updating 149 it after every move. 150 151 The necessary tables can be generated with something like this: 152 153 ``` 154 for i in [0..n-1] 155 for m in Moves 156 j = m(rep of i) /* Apply as basic coordinate */ 157 move_table[m][i] = class of j 158 offset_table[m][i] = transformation bringing j to its rep 159 ``` 160 161 ### Symmetric-composite coordinates 162 163 A symmetric-composite coordinate requires some extra work, but the hard 164 part is already handled by its base symmetric coordinate. 165 166 To move a symmetric-composite coordinate, first we recover the value s 167 of its symmetric coordinate's and the value c of its composite coordinate 168 by taking the quotient and the remainder of division by the maximum value 169 of the composite coordinate. 170 171 Then we apply the move to the values s and c using their respective 172 transition tables. The offset transformation is taken from the symmetric 173 coordinate, and apply it to the result of the move on the composite coordinate. 174 175 This may be summarized with the following pseudo-code: 176 177 ``` 178 s = ind / M /* M is the maximum value +1 of the composite coordinate */ 179 c = ind % M 180 new_s = move_table_s[m][s] /* Using the table for the symmetric coordinate */ 181 new_c = move_table_c[m][c] /* Using the table for the composite coordinate */ 182 offset = offset_table[m][s] 183 new_c = offset(new_c) /* See next section for transformations */ 184 185 return (new_s * M + new_c, offset) 186 ``` 187 188 ## Transforming coordinates 189 190 When we talk about *cube transformations*, we are talking about 191 conjugating a cube by a rotation, possibly combined with a mirroring 192 along a fixed axis. More precisely, transforming a cube c is done with 193 the following steps: 194 195 * Start from a solved cube 196 * (optional) Mirror it left-right 197 * Apply the required rotation 198 * Apply c (as a permutation / move sequence) to the rotated solved cube 199 * Apply the inverse of the rotation 200 * (optional) Mirror it left-right 201 202 When working with coordinates, transformations are applied pretty much 203 in the same way as moves, using a transition table. This time, though, 204 symmetric coordinates are much less of a problem: any transformation 205 on a symmetric coordinate is, by definition, trivial! Of course, this 206 is only true if we limit ourselves to applying transformations that are 207 part of the set used to "reduce" the symmetric coordinate; but we always 208 do this anyway. 209 210 ## Pruning tables 211 212 I'd like to mention pruning tables here, because their computation is 213 quite straightforward when using coordinates. 214 215 Say you want to compute a table that associates every possible value i in 216 [0..n-1] of a coordinate with the minimum amount of moves required to 217 solve any cube c such that `index(c) == i`. For the purpose of this page 218 we assume one can afford to allocate enough bits so that the actual value 219 can be stored. 220 221 With coordinates, one can do the following, without ever going back to 222 the full cube representation: 223 224 ``` 225 set all values of the pruning table to infinity 226 set the value associated with the solved cube to 0 227 for d in [1..20] 228 for i in [0..n-1] 229 if pruning_table[i] == d-1 230 for m in Moves 231 old = pruning_table[m(i)] 232 pruning_table[m(i)] = min(d, old) 233 ``` 234 235 This is conceptually very simple, but unfortunately it is not enough. 236 Because of self-symmetries, not every position will be reached in this 237 way for a symmetric-composite coordinate: there may be more ways to 238 bring the base of the symmetric coordinate to its representative, each 239 having a different effect on the composite coordinate, but we only pick 240 one of them when building the move tables. 241 242 Luckily, this can be solved because we have memorized for every position a 243 list of all the transformations that keep it invariant (see above). Then 244 it is enough to add the following loop at the end of every iteration of 245 the outermost loop above: 246 247 ``` 248 for i in [0..n-1] 249 for t in the set of self-symmetries of i/M 250 old = pruning_table[t(i)] 251 pruning_table[t(i)] = min(d, old) 252 ``` 253 254 The code for this can be found in 255 [pruning.c](https://git.tronto.net/nissy-nx/file/src/pruning.c.html). 256 The use of pthread made it more complicated, so it can be hard to follow 257 without reading this page first. 258 259 ## Why using coordinates? 260 261 Coordinates are necessary to compute pruning tables, which are fundamental 262 when solving a cube using the methods described in Jaap's 263 [computer puzzling page](https://www.jaapsch.net/puzzles/compcube.htm). 264 265 However, using transition tables for moves and transformations is 266 not necessary. It used to be an efficient way to perform moves on a 267 cube, but with newer hardware the trade-offs between memory access and 268 instruction execution are changing. 269 270 One thing that is made particularly cumbersome by using coordinates 271 instead of a full representation of the cube is computing the 272 inverse. While it is possible to compute the inverse somewhat efficiently 273 from a representation of the cube made of a smart selection of coordinate 274 values, it is not necessarily efficient. 275 See [fst.c](https://git.tronto.net/nissy-nx/file/src/fst.c.html#l113) 276 for an implementation. 277 278 For these reasons, I am not using the coordinate approach described here 279 for my new work-in-progress solver (temporarily named 280 [h48](https://git.tronto.net/h48)).