commit 2b30bffc6cfef47c785c9bd3d5aa365750c0d533
parent af6193e3fca6e5ec5e9442af601a026ea328b19b
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 4 Dec 2023 16:16:01 +0100
Added coordinate writeup
Diffstat:
1 file changed, 280 insertions(+), 0 deletions(-)
diff --git a/src/speedcubing/coordinates/coordinates.md b/src/speedcubing/coordinates/coordinates.md
@@ -0,0 +1,280 @@
+# Cube coordinates
+
+In this page I describe the way I implemented *coordinates*, in the
+sense of [Cube Explorer](http://kociemba.org/cube.htm), in one of the
+versions of [Nissy](https://nissy.tronto.net).
+
+Unfortunately, this implementation got lost between rewrites and is
+currently not included in any working version of Nissy or other projects,
+so it this page is of theoretical interest only. Some code is available
+in the [nissy-nx repository](https://git.tronto.net/nissy-nx), but it
+is currently broken (what is described in this page works, though).
+
+## What are cube coordinates?
+
+A *cube coordinate* is a way of associating to any legal position
+of the Rubik's cube an integer in a certain range [0..n-1]. For
+example, any way of encoding the permutation of the corners as a
+number from 0 to 8!-1 is a valid coordinate; another example is
+an encoding of the orientation of the edges with respect to a given
+axis as a number in [0..2^11].
+
+In other words, a coordinate is a function from the set of legal
+configurations to [0..n-1]. Coordinates need not be surjective,
+though it is more convenient if they are, and in my examples they
+will be.
+
+To work with cube coordinates, we need to implement the following:
+
+* An integer `n`, the maximum value of a coordinate +1.
+* A function `index()` that takes a cube as input and returns an integer
+ in the range [0..n-1] as output.
+* A function `to_cube()` that takes an integer in [0..n-1] as input and
+ returns a cube `c` such that `index(to_cube(x)) == x` for every x in
+ [0..n-1]. In other words, `to_cube()` is a *section* of `index()`.
+ In practice, it is not necessary that the output of `to_cube()` is a
+ valid cube object.
+* A function `move()` that takes as input a coordinate, a move m and an
+ integer x in [0..n-1] and returns an integer y in [0..n-1] such
+ that `y == index(m(to_cube(x)))` (here m(c) is the cube c moved by m).
+* If applicable, a `transform()` function that applies a transformation
+ in a similar way as `move()` applies a move. For coordinates this is
+ not possible, because they do not capture enough of the cube state.
+ For some coordinates, only some transformations are possible. For
+ example, for the edge orientation coordinate only the transformations
+ that fix the axis with respect to which the edge orientation is defined
+ can be applied.
+
+For the implementation, see
+[coord.c](https://git.tronto.net/nissy-nx/file/src/coord.c.html)
+and
+[coord.h](https://git.tronto.net/nissy-nx/file/src/coord.h.html),
+as well as the definition of
+[coordinate](https://git.tronto.net/nissy-nx/file/src/cubetypes.h.html#l181)
+in cubetypes.h.
+
+## Coordinate types
+
+In my work I have defined four types of coordinates (but I actually use
+only three of them).
+
+### Basic coordinates
+
+Basic coordinates are the simplest kind, and they are completely defined
+by the integer `n` and the functions `index()` and `to_cube()` defined
+above. This is the type of coordinate that "does not exist" in the code,
+because they are just a special case of *composite coordinates*.
+
+### Composite coordinates (COMP_COORD)
+
+Composite coordinates are, like the name says, a composition of many basic
+coordinates. They are given by a list of basic coordinates (n_1, index_1(),
+to_cube_1()), ..., (n_k, index_k(), to_cube_k()). The value of such a
+composite coordinate on cube c is computed as
+index_1(c) + n_1 * (index_2(c) + n_2 * (...)).
+
+### Symmetric coordinates (SYM_COORD)
+
+A symmetric coordinate consists of a basic coordinate reduced by symmetry.
+Symmetric coordinates must be initialized from a given set of *cube
+transformations* before they can be used. The initialization step produces
+the following data:
+
+* A table that associates every possible value of the basic coordinate
+ with its class in the symmetric coordinate. Computing the value of the
+ symmetric coordinate will then amount to computing the basic coordinate
+ via `index()` and looking up the value in this table.
+* A table that associates every possible value of the basic coordinate
+ with a fixed representative for its class.
+* A table that associates every possible value of the basic coordinate
+ the cube transformation that brings it to its representative.
+* A table that associates every possible value of the basic coordinate
+ with the list of cube transformations that do not affect it, that is
+ a list of *self-symmetries*. This will be useful when computing the
+ pruning table associated to this coordinate.
+
+### Symmetric-composite coordinates (SYMCOMP_COORD)
+
+A symmetric-composite coordinate is based on two other coordinates, a
+symmetric coordinate and a composite coordinate. To compute the value
+of a symmetric-composite coordinate one must compute the symmetric
+coordinate value first, then transform the cube using the transformation
+that brings the basic coordinate associated to the symmetric coordinate
+to its representative in order to compute the correct value for the
+composite coordinate, and finally combine the two.
+
+More precisely and with less tong-twisting, for a given cube c one must
+take the following steps:
+
+* Compute the value x_s of the symmetric coordinate at c, the value
+ x_b of the *basic* coordinate associated with the symmetric coordinate
+ and the value x_c of the composite coordinate.
+* Read from the table the transformation t that brings x_b to its
+ representative.
+* Apply t to the composite coordinate value x_c to obtain x_t.
+* Compute the value x_s * n_c + x_t, where n_c is the maximum value +1
+ of the composite coordinate.
+
+## Moving coordinates
+
+A move is applied to a coordinate by lookup into a transition table,
+pretty much as explained in Jaap's
+[computer puzzling page](https://www.jaapsch.net/puzzles/compcube.htm#trans).
+These transition tables are initialized once and for all at the beginning,
+and in my implementation I actually saved them to a file to speed up
+subsequent runs.
+
+Some extra care has to be taken in dealing with symmetries.
+
+### Basic and composite coordinates
+
+This case is quite simple: the transition table with something along these
+lines:
+
+```
+for i in [0..n-1]
+ for m in Moves
+ move_table[m][i] = index(m(to_cube(i)))
+```
+
+### Symmetric coordinates
+
+As mentioned above, this case and the next are tricky, because we need
+to keep track of which transformation has to be applied to get from the
+representative of the symmetry class to our actual cube.
+
+You can imagine a move applied to symmetric coordinate as if we just
+move between different representatives. The actual cube can be recovered
+from this by keeping track of an *offset transformation*, and updating
+it after every move.
+
+The necessary tables can be generated with something like this:
+
+```
+for i in [0..n-1]
+ for m in Moves
+ j = m(rep of i) /* Apply as basic coordinate */
+ move_table[m][i] = class of j
+ offset_table[m][i] = transformation bringing j to its rep
+```
+
+### Symmetric-composite coordinates
+
+A symmetric-composite coordinate requires some extra work, but the hard
+part is already handled by its base symmetric coordinate.
+
+To move a symmetric-composite coordinate, first we recover the value s
+of its symmetric coordinate's and the value c of its composite coordinate
+by taking the quotient and the remainder of division by the maximum value
+of the composite coordinate.
+
+Then we apply the move to the values s and c using their respective
+transition tables. The offset transformation is taken from the symmetric
+coordinate, and apply it to the result of the move on the composite coordinate.
+
+This may be summarized with the following pseudo-code:
+
+```
+s = ind / M /* M is the maximum value +1 of the composite coordinate */
+c = ind % M
+new_s = move_table_s[m][s] /* Using the table for the symmetric coordinate */
+new_c = move_table_c[m][c] /* Using the table for the composite coordinate */
+offset = offset_table[m][s]
+new_c = offset(new_c) /* See next section for transformations */
+
+return (new_s * M + new_c, offset)
+```
+
+## Transforming coordinates
+
+When we talk about *cube transformations*, we are talking about
+conjugating a cube by a rotation, possibly combined with a mirroring
+along a fixed axis. More precisely, transforming a cube c is done with
+the following steps:
+
+* Start from a solved cube
+* (optional) Mirror it left-right
+* Apply the required rotation
+* Apply c (as a permutation / move sequence) to the rotated solved cube
+* Apply the inverse of the rotation
+* (optional) Mirror it left-right
+
+When working with coordinates, transformations are applied pretty much
+in the same way as moves, using a transition table. This time, though,
+symmetric coordinates are much less of a problem: any transformation
+on a symmetric coordinate is, by definition, trivial! Of course, this
+is only true if we limit ourselves to applying transformations that are
+part of the set used to "reduce" the symmetric coordinate; but we always
+do this anyway.
+
+## Pruning tables
+
+I'd like to mention pruning tables here, because their computation is
+quite straightforward when using coordinates.
+
+Say you want to compute a table that associates every possible value i in
+[0..n-1] of a coordinate with the minimum amount of moves required to
+solve any cube c such that `index(c) == i`. For the purpose of this page
+we assume one can afford to allocate enough bits so that the actual value
+can be stored.
+
+With coordinates, one can do the following, without ever going back to
+the full cube representation:
+
+```
+set all values of the pruning table to infinity
+set the value associated with the solved cube to 0
+for d in [1..20]
+ for i in [0..n-1]
+ if pruning_table[i] == d-1
+ for m in Moves
+ old = pruning_table[m(i)]
+ pruning_table[m(i)] = min(d, old)
+```
+
+This is conceptually very simple, but unfortunately it is not enough.
+Because of self-symmetries, not every position will be reached in this
+way for a symmetric-composite coordinate: there may be more ways to
+bring the base of the symmetric coordinate to its representative, each
+having a different effect on the composite coordinate, but we only pick
+one of them when building the move tables.
+
+Luckily, this can be solved because we have memorized for every position a
+list of all the transformations that keep it invariant (see above). Then
+it is enough to add the following loop at the end of every iteration of
+the outermost loop above:
+
+```
+ for i in [0..n-1]
+ for t in the set of self-symmetries of i/M
+ old = pruning_table[t(i)]
+ pruning_table[t(i)] = min(d, old)
+```
+
+The code for this can be found in
+[pruning.c](https://git.tronto.net/nissy-nx/file/src/pruning.c.html).
+The use of pthread made it more complicated, so it can be hard to follow
+without reading this page first.
+
+## Why using coordinates?
+
+Coordinates are necessary to compute pruning tables, which are fundamental
+when solving a cube using the methods described in Jaap's
+[computer puzzling page](https://www.jaapsch.net/puzzles/compcube.htm).
+
+However, using transition tables for moves and transformations is
+not necessary. It used to be an efficient way to perform moves on a
+cube, but with newer hardware the trade-offs between memory access and
+instruction execution are changing.
+
+One thing that is made particularly cumbersome by using coordinates
+instead of a full representation of the cube is computing the
+inverse. While it is possible to compute the inverse somewhat efficiently
+from a representation of the cube made of a smart selection of coordinate
+values, it is not necessarily efficient.
+See [fst.c](https://git.tronto.net/nissy-nx/file/src/fst.c.html#l113)
+for an implementation.
+
+For these reasons, I am not using the coordinate approach described here
+for my new work-in-progress solver (temporarily named
+[h48](https://git.tronto.net/h48)).
