diff options
Diffstat (limited to 'README.md')
| -rw-r--r-- | README.md | 25 |
1 files changed, 20 insertions, 5 deletions
| @@ -21,6 +21,12 @@ solutions for EO/DR/HTR or similar substeps. | |||
| 21 | 21 | ||
| 22 | ## Requirements | 22 | ## Requirements |
| 23 | 23 | ||
| 24 | ** Warning: ** *This section is not up to date with the code. In nissy-2.0beta8 | ||
| 25 | or later the only way to get the table files is to generate them yourself. | ||
| 26 | All but the huge table just requires a few minutes; the huge table for | ||
| 27 | optimal solving can require a couple of hours. Use more than 1 thread | ||
| 28 | if you can.* | ||
| 29 | |||
| 24 | A full installation of Nissy requires a little more than 2Gb of space, | 30 | A full installation of Nissy requires a little more than 2Gb of space, |
| 25 | of which 1.6Gb are occupied by the huge pruning table for fast optimal solving, | 31 | of which 1.6Gb are occupied by the huge pruning table for fast optimal solving, |
| 26 | and running it requires the same amount of RAM. | 32 | and running it requires the same amount of RAM. |
| @@ -120,17 +126,26 @@ of the cube if not necessary). | |||
| 120 | 126 | ||
| 121 | Some coordinates make use of symmetries to reduce the size of the resulting | 127 | Some coordinates make use of symmetries to reduce the size of the resulting |
| 122 | pruning table. Unfortunately this complicates the code a lot, but it is a huge | 128 | pruning table. Unfortunately this complicates the code a lot, but it is a huge |
| 123 | advantage: it reduces by a factor of about 16 the huge pruning table, which | 129 | advantage: it reduces by a factor of about 16 the pruning table size. |
| 124 | results in around 1.6Gb instead of 24 or so. | ||
| 125 | 130 | ||
| 126 | Pruning tables are related to a specific step, a moveset and a coordinate. They | 131 | Pruning tables are related to a specific step, a moveset and a coordinate. They |
| 127 | contain one value from 0 to 15 (4 bits) for each possible value for the coordinate, | 132 | contain one value from 0 to 15 (4 bits) for each possible value for the coordinate, |
| 128 | which is less or equal than the minimum number of moves required to solve the | 133 | which is less or equal than the minimum number of moves required to solve the |
| 129 | given step with the given moveset for a cube which has the given coordinate. For example, | 134 | given step with the given moveset for a cube which has the given coordinate. For example, |
| 130 | say the coordinate `neo` gives the number of non-oriented edges (say with respect to | 135 | say the coordinate `neo` gives the number of non-oriented edges (say with respect to |
| 131 | F/B). Then the possible values for the coordinate are 0,2,4,...,12. An associate pruning | 136 | F/B). Then the possible values for the coordinate are 0,2,4,...,12. An associated |
| 132 | table to solving EO with HTM moveset and this coordinate would have values 0 (for | 137 | pruning table to solving EO with HTM moveset and this coordinate would have values 0 |
| 133 | `neo=0`), 3 (for `neo=2`), 1 (for `neo=4`)... | 138 | (for `neo=0`), 3 (for `neo=2`), 1 (for `neo=4`)... |
| 139 | |||
| 140 | The values for most pruning tables are memorized modulo 16, so they only occupy | ||
| 141 | 4 bits per entry, and values larger than 15 are saved as 15. This is good enough | ||
| 142 | for most applications. | ||
| 143 | Some large tables are memorized in compact form using only 4 bits, similarly | ||
| 144 | to what [nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md) does: | ||
| 145 | a base value `b` is picked and a value of `n` is saved as `MIN(3,MAX(0,n-b))`. | ||
| 146 | When a value of `v=1,2,3` is read it is simply returned as `v+b`, while if | ||
| 147 | `0` is a successive lookup to a fallback table is performed. The base value `b` | ||
| 148 | is picked to maximize the sum frequency of the values `1,2,3`. | ||
| 134 | 149 | ||
| 135 | There is one caveat: each coordinates also needs an inverse function that takes a | 150 | There is one caveat: each coordinates also needs an inverse function that takes a |
| 136 | coordinate value and returns a cube which has that coordinate. This is in general | 151 | coordinate value and returns a cube which has that coordinate. This is in general |
