diff options
| -rw-r--r-- | README.md | 10 | ||||
| -rw-r--r-- | TODO.md | 191 | ||||
| -rw-r--r-- | doc/solvers.md | 8 |
3 files changed, 200 insertions, 9 deletions
| @@ -1,4 +1,4 @@ | |||
| 1 | # The engine of Nissy, including the H48 optimal solver | 1 | # The future engine of Nissy, including the H48 optimal solver |
| 2 | 2 | ||
| 3 | **Warning**: this library is work in progress, breaking changes can | 3 | **Warning**: this library is work in progress, breaking changes can |
| 4 | happen without notice. | 4 | happen without notice. |
| @@ -11,6 +11,14 @@ H48 is an experimental Rubik's cube solver. It is heavily inspired by | |||
| 11 | [vcube](https://github.com/Voltara/vcube), but it uses a different set | 11 | [vcube](https://github.com/Voltara/vcube), but it uses a different set |
| 12 | of pruning tables that were developed independently. | 12 | of pruning tables that were developed independently. |
| 13 | 13 | ||
| 14 | ## Contributing | ||
| 15 | |||
| 16 | If you want to contribute to this project, see [TODO.md](./TODO.md) for | ||
| 17 | some ideas. | ||
| 18 | |||
| 19 | In case you want to develop your own tool based on nissy-core, do get | ||
| 20 | in touch with me and I'll be happy to help you out! | ||
| 21 | |||
| 14 | ## Building | 22 | ## Building |
| 15 | 23 | ||
| 16 | This project is mainly developed on UNIX systems (Linux, MacOS, BSD...), | 24 | This project is mainly developed on UNIX systems (Linux, MacOS, BSD...), |
| @@ -0,0 +1,191 @@ | |||
| 1 | # Ideas, improvements, things that I may never do... | ||
| 2 | |||
| 3 | This document contains a list of ideas for possible new features or | ||
| 4 | improvements to nissy-core. This file used to be private, but it makes | ||
| 5 | more sense to have it public, in case someone else wants to contribute. | ||
| 6 | |||
| 7 | ## Priorities | ||
| 8 | |||
| 9 | Items in this section are what I consider top priorities. They enable or | ||
| 10 | simplify using nissy-core as a library inside other projects. | ||
| 11 | |||
| 12 | ### Python packaging and distribution | ||
| 13 | |||
| 14 | Make a [PyPI](https://pypi.org/) package for nissy-core. There is already | ||
| 15 | a Python module in the `python/` folder, and it builds both on UNIX and on | ||
| 16 | Windows, so this should not require too much work. It is also possible to | ||
| 17 | make this process automatic using GitHub actions or something similar. | ||
| 18 | |||
| 19 | The documentation of the Python module should also be improved. | ||
| 20 | |||
| 21 | ### WASM interface improvements | ||
| 22 | |||
| 23 | Currently there is a proof-of-concept web version for the H48 optimal | ||
| 24 | solver (see [h48.tronto.net](https://h48.tronto.net) - it is based on | ||
| 25 | a very old version of the solver). This needs some polishing, namely: | ||
| 26 | |||
| 27 | * The main thing we want to do is enabling downloading the pruning tables | ||
| 28 | in small pieces and show a progress bar of some sort. The best way to do | ||
| 29 | this would probably be handling all the data storage logic in JavaScript | ||
| 30 | code (`http/worker.mjs`) rather than in C++ (`storage.cpp`). With this, | ||
| 31 | we should also be able to remove the `-sASYNCIFY` and `-sFETCH` options | ||
| 32 | from the Emscripten build command. | ||
| 33 | * Table generation can be removed from the web version. | ||
| 34 | * Logging can also be simplified by just using `console.log`. We will then | ||
| 35 | loose the ability to show the log pane in the HTML page, but this is not | ||
| 36 | very interesting to the user. If future applications based on nissy-core | ||
| 37 | want to notify the user of the status of the solver, we can handle this | ||
| 38 | later with callback parameters to the solve function. | ||
| 39 | * For now it is fine to stick to 32-bit WASM and limit ourselves to 1.8GB | ||
| 40 | tables at most. | ||
| 41 | |||
| 42 | If possible, it would be nice to publish a nissy-core package on | ||
| 43 | [NPM](https://www.npmjs.com/). | ||
| 44 | |||
| 45 | ### Improved documentation | ||
| 46 | |||
| 47 | Currently, there is documentation in multiple places, like the `doc/` | ||
| 48 | folder and the `nissy.h` header. This documentation should be expanded | ||
| 49 | into a sort of "developer guide" for contributing to the project. | ||
| 50 | Some critical parts of the code base could also be better commented. | ||
| 51 | |||
| 52 | For example, a list of instructions for implementing a new solver can | ||
| 53 | be useful. | ||
| 54 | |||
| 55 | ## Turning this into a usable application | ||
| 56 | |||
| 57 | There are at least three ways to turn this into a useful tool for FMC | ||
| 58 | training. I don't know if I want to work on any of these in the near | ||
| 59 | future - they are all up for grabs! | ||
| 60 | |||
| 61 | ### CLI application | ||
| 62 | |||
| 63 | The easiest interface to make for nissy-core is a command line | ||
| 64 | one. This can be done be either improving on the shell in this | ||
| 65 | repository (see `shell/`), or by plugging this library into the old | ||
| 66 | [nissy](https://nissy.tronto.net). In either case, the result would not | ||
| 67 | be much different from the latest version of nissy-classic: there would | ||
| 68 | be a faster optimal solver, but some other features may be missing. | ||
| 69 | |||
| 70 | ### Desktop application | ||
| 71 | |||
| 72 | It is easy to use nissy-core as a library in a C or C++ based | ||
| 73 | application. I have some examples using the QT framework in | ||
| 74 | [qt-experiments](https://github.com/sebastianotronto/qt-experiments) | ||
| 75 | (note: the examples there are based on a very old version of nissy-core). | ||
| 76 | |||
| 77 | Distribution could be a bit of a pain, especially for Linux. That's why | ||
| 78 | I would personally prefer making a TUI-based application. For example, | ||
| 79 | [termbox2](https://github.com/termbox/termbox2) could be a good library | ||
| 80 | for this, if they implement Windows support. | ||
| 81 | |||
| 82 | Yet another option is using Python (for example with QT, via | ||
| 83 | [PySide6](https://doc.qt.io/qtforpython-6/)). | ||
| 84 | |||
| 85 | ### Web application | ||
| 86 | |||
| 87 | Since nissy-core builds to WebAssembly, it is possible to use it as a | ||
| 88 | library for a WebApp. This would run entirely in the user's browser, | ||
| 89 | like [h48.tronto.net](https://h4.tronto.net). | ||
| 90 | |||
| 91 | It would also be nice to turn it into an installable PWA, see [this | ||
| 92 | repository](https://github.com/chr15m/minimal-pwa) for a minimal example. | ||
| 93 | |||
| 94 | ## Additional features | ||
| 95 | |||
| 96 | Possible new features for nissy. | ||
| 97 | |||
| 98 | ### Additional solvers | ||
| 99 | |||
| 100 | More solvers, or options for current solvers, can be added: | ||
| 101 | |||
| 102 | * Finish from HTR. This is available in nissy-classic and it is not hard | ||
| 103 | to implement. | ||
| 104 | * Direct HTR, without having DR or EO. This can be useful for finding HTR | ||
| 105 | trigger that break DR. The pruning table for this one is too big, but | ||
| 106 | we can take advantage of the H48 tables. | ||
| 107 | * Floppy reduction. | ||
| 108 | * JZP / Axial reduction, from EO or direct. | ||
| 109 | * Slice solver, using | ||
| 110 | [VR](https://www.youtube.com/watch?v=8SHjQtvuz5Q&list=PL0DmWpJUeHN-o0OKYhDe7w8O6GahIvOtx&index=2). | ||
| 111 | * Finish / leave double slice from JZP. This is a different type of solver, | ||
| 112 | because we want to look from both sides for increasingly long solutions | ||
| 113 | and meet in the middle. Similarly, we may also want to implement a | ||
| 114 | "leave double slice" and a "solve double slice" steps. | ||
| 115 | * Finish / HTR / JZP finish / leave slice etc... with minimal number of | ||
| 116 | quarter turns. | ||
| 117 | |||
| 118 | ### Coordinate solvers improvements | ||
| 119 | |||
| 120 | The coordinate solvers do not support pause / resume / stop via callback | ||
| 121 | function. This is not too hard to add (just copy what the H48 solver is doing), | ||
| 122 | but also not too useful, as coordinate solvers are generally very fast. | ||
| 123 | |||
| 124 | ## Performance improvements | ||
| 125 | |||
| 126 | I have worked a lot on performance, but some things can still be improved. | ||
| 127 | |||
| 128 | ### H48 performance improvements | ||
| 129 | |||
| 130 | The only idea I have left for improving the performance of the H48 optimal | ||
| 131 | solver is implementing *microthreading*. This means making the main | ||
| 132 | solve DFS iterative, and working on multiple DFS branches at the same | ||
| 133 | time on the same physical thread. The end goal is taking advantage of | ||
| 134 | [prefetching](https://sebastiano.tronto.net/blog/2026-01-28-prefetch/) | ||
| 135 | even further. | ||
| 136 | |||
| 137 | ### Coordinate solvers | ||
| 138 | |||
| 139 | Neither the solve algorithm nor the pruning table generation for | ||
| 140 | coordinate solver is parallelized. It should not be hard to do (just | ||
| 141 | copy what is done for the H48 optimal solver), but coordinate solvers | ||
| 142 | are generally small and fast. Parallelized pruning table generation | ||
| 143 | could save some time though. | ||
| 144 | |||
| 145 | ### Cube analysis | ||
| 146 | |||
| 147 | A new API function can be added to analyze a given cube position. | ||
| 148 | Example of analysis are: | ||
| 149 | |||
| 150 | * HTR state. Should return a short name for the HTR case. | ||
| 151 | * EO state (no NISS). First a nomenclature for EO cases should be defined. | ||
| 152 | * ARM subsets. | ||
| 153 | * VR case. | ||
| 154 | |||
| 155 | ## Technical improvements | ||
| 156 | |||
| 157 | I lumped together here a bunch of possible improvements that would not | ||
| 158 | affect the use of the library much, but can still be useful or interesting | ||
| 159 | for developers. | ||
| 160 | |||
| 161 | ### On-line (internal) documentation | ||
| 162 | |||
| 163 | Currently the only way to know which solvers are available is reading the | ||
| 164 | `doc/solver.md` page. There should be an API function to list available | ||
| 165 | solvers. Same thing for variations. | ||
| 166 | |||
| 167 | In general, there should be more documentation available from within | ||
| 168 | the library itself. | ||
| 169 | |||
| 170 | ### Python pause / stop / resume | ||
| 171 | |||
| 172 | The pause / stop / resume via callback functionality for the H48 optimal | ||
| 173 | solver is not supported in the Python module. I tried to make it to work, | ||
| 174 | but I had some issues which I suspect were related to the GIL and the | ||
| 175 | fact the the solver is multi-threaded. However, I get the exact same | ||
| 176 | issues with no-GIL versions of Python. | ||
| 177 | |||
| 178 | I have tried calling the callback function from within an `ALLOW_THREADS` | ||
| 179 | block, but I get a segfault. If I remove the `ALLOW_THREADS` blocks, | ||
| 180 | the program hangs indefinitely. | ||
| 181 | |||
| 182 | Good luck debugging this. | ||
| 183 | |||
| 184 | ### Better Windows development support | ||
| 185 | |||
| 186 | The build script for Windows has fewer options than the UNIX one. For | ||
| 187 | example, to configure the maximum number of threads a developer would | ||
| 188 | have to manually edit the build script. | ||
| 189 | |||
| 190 | I'll leave this one to anyone who actually wants to work on nissy-core | ||
| 191 | from Windows. | ||
diff --git a/doc/solvers.md b/doc/solvers.md index b7fe613..c2a6791 100644 --- a/doc/solvers.md +++ b/doc/solvers.md | |||
| @@ -169,11 +169,3 @@ These solvers include: | |||
| 169 | to use `coord_DRSLICE_xx` as described above as it may produce shorter | 169 | to use `coord_DRSLICE_xx` as described above as it may produce shorter |
| 170 | solutions, and it is easier to filter out duplicates (solutions that | 170 | solutions, and it is easier to filter out duplicates (solutions that |
| 171 | differ only by how they affect the E-layer). | 171 | differ only by how they affect the E-layer). |
| 172 | |||
| 173 | ## Planned future solvers | ||
| 174 | |||
| 175 | The following solvers are planned to be introduced in the future: | ||
| 176 | |||
| 177 | * Finish from HTR | ||
| 178 | * JZP / Axial reduction, from EO or direct | ||
| 179 | * Finish / leave double slice from JZP | ||
