From bf44088d4373a9520e860152c56a958332819c4b Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 1 May 2023 16:33:51 +0200 Subject: Split nissy in other repos, see README.md --- README.md | 130 ++++++++++++++++++-------------------------------------------- 1 file changed, 38 insertions(+), 92 deletions(-) (limited to 'README.md') diff --git a/README.md b/README.md index 8aa6a2d..7b0beda 100644 --- a/README.md +++ b/README.md @@ -1,104 +1,50 @@ -# WARNING +# Where is nissy? -I am currently rewriting some important parts of the code -and the git version is not working. -You can download the last stable version from the -[download page](https://nissy.tronto.net/download). +In April 2023 I have decided to split nissy in 2 separate projects: an +optimal solver and an FMC assistant. These two projects are not usable +yet, so in the meantime I will keep a third branch where I update the +classic version of nissy with bugfixes and minor improvements. -# Nissy +You can find these three branches at the following pages (also +on github, links below are to my personal git instance): -A Rubik's cube solver and FMC assistant. -For optimal HTM solving Nissy uses techniques from Herbert Kociemba's -[Cube Explorer](http://kociemba.org/cube.htm) and Tomas Rokicki's -[nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md). -With 4 cores at 2.5GHz and using about 3Gb of RAM, Nissy can find an -optimal solution in about a minute on average. +* [nissy-classic](https://git.tronto.net/nissy-classic): The stable + branch, will receive bugfixes and minor improvements but no big + change. Will eventually be replaced by the other two versions. +* [nissy-fmc](https://git.tronto.net/nissy-fmc): This will focus on + features useful for practicing FMC, for example finding EOs and + DRs (if you do not know what this means, there is a good chance + you don't care). I plan to make a graphical interface for it and + make it more usable. It will not be able to find an optimal + solution. *Not working at the moment.* +* [nissy-nx](https://git.tronto.net/nissy-nx): An optimal solver. + For now this is just my playground for implementing complex + optimizations, following the ideas of Tomas's Rokicki's + [nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md). + Eventually it will become faster than nissy-classic at optimal + solving, but without all other features. *Not working at the moment.* -Nissy can also solve many different substeps of Thistlethwaite's algorithm -(DR/HTR), and can use NISS (Normal-Inverse Scramble Switch). -It can be useful to analyze your DR solves (and more, once I implement more features). +# I am a user of nissy, what should I do? -You can get Nissy from [nissy.tronto.net](https://nissy.tronto.net). -The download links and installation instructions can be found on the -[download page](https://nissy.tronto.net/download). +If you are happy with using nissy as it is, you can keep using it. -## Structure of the code +When nissy-fmc and nissy-classic are ready, you can chek them out too. -You can find all the source code in the `src` folder. -I strived to keep it legible but I did not write many comments (barely any at all). -I'll try to explain here the main parts of the program. +# But I liked that nissy can do both optimal solving! Why did you split it? -### Cube, moves and transformations +Then I encourage you to keep using nissy-classic :-) -There are many ways to represent a cube. In Nissy I use two: +See +[my blog post](https://sebastiano.tronto.net/blog/2023-04-10-the-big-rewrite/) +for some reasons behind this change. -* An array representation `CubeArray`: 3 arrays representing the permutation -of corners, edges and centers and 2 arrays for the orientation of corners and edges. -* An 11-integers representation `Cube`: 3 integers for edge orientation (with respect -to the three axes), 3 for corner orientation, and so on. Edge permutation is a bit -complicated because encoding 12 factorial as a single number is too large for some -practical reasons, so I use 3 integers for that. +# I just want to look at the code, where should I go? -Moves are easy to apply on the array form, but they are slow. So `moves.c` -contains the instructions to create all the transition tables necessary -to get the next position for the cube with just 11 lookup operations -(one for each of the 11 integers in the second representation). -These transition tables are saved in the `mtables` file in the -`tables` folder in binary format. - -The 11 integers are obviously redundant, but keeping all of them makes it easy -to apply transformations. A transformation is a rotation of the whole cube, possibly -combined with a mirror operation. Applying a transformation to a cube (say obtained -by applying a scramble to the solved cube) means applying the transformation to a -solved cube, then the scramble and then the inverse of the transformation -(i.e. conjugating by it). - -### Coordinates and pruning tables - -A *coordinate* consists of a function that takes a cube (in the 11-integer -representation) and return an (unsigned, 64-bit) integer. They are used -to "linearize" a cube and build pruning tables, which speed up significantly the -solving process. To be able to access the pruning table quickly, the function -needs to be very fast (e.g. it should not convert between the two representations -of the cube if not necessary). - -Some coordinates make use of symmetries to reduce the size of the resulting -pruning table. Unfortunately this complicates the code a lot, but it is a huge -advantage: it reduces by a factor of about 16 the pruning table size. - -Pruning tables are related to a specific step, a moveset and a coordinate. They -contain one value from 0 to 15 (4 bits) for each possible value for the coordinate, -which is less or equal than the minimum number of moves required to solve the -given step with the given moveset for a cube which has the given coordinate. For example, -say the coordinate `neo` gives the number of non-oriented edges (say with respect to -F/B). Then the possible values for the coordinate are 0,2,4,...,12. An associated -pruning table to solving EO with HTM moveset and this coordinate would have values 0 -(for `neo=0`), 3 (for `neo=2`), 1 (for `neo=4`)... - -The values for most pruning tables are memorized modulo 16, so they only occupy -4 bits per entry, and values larger than 15 are saved as 15. This is good enough -for most applications. -Some large tables are memorized in compact form using only 2 bits, similarly -to what [nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md) does: -a base value `b` is picked and a value of `n` is saved as `MIN(3,MAX(0,n-b))`. -When a value of `v=1,2,3` is read it is simply returned as `v+b`, while if -`0` is a successive lookup to a fallback table is performed. The base value `b` -is picked to maximize the sum frequency of the values `1,2,3`. - -In order to generate the pruning tables, it is necessary to be able to move -a transform a coordinate; it is possible to do so without passing through a -complete cube representations, in a way similar to what Cube Explorer does. -This used to be different before version 2.1 (June 2022). - -More documentation on this and on the different types of coordinates (base -vs composed) is work in progress. - -### Solving - -Solving is implemented as a generic function that takes both a step and -a (scrambled) cube as input, as well as some extra parameters that say e.g. -how many solution one wants. A step consists, among other things, of -an estimator function that, given a cube, gives a lower bound for the number -of moves needed to complete the step. Many of these estimators simply -look up the corresponding values in the appropriate pruning table. +If you want to check out the git repository of the version you are +running, you probably want nissy-classic. The newer nissy-fmc will +eventually be nicer and easier to read, containing more or less +the same functionality (except for optimal solving). +If you want to follow my progress on an advanced optimal Rubik's +cube solver, you can check out nissy-nx - just remember that it +does not work yet! -- cgit v1.3