Tutorials/ikpx2
Welcome to the tutorial where you can learn to find spaceships using ikpx2!
Things to do first
If you haven't, go to the Compiling C Code tutorial first.
Dependencies
ikpx2 requires the following in order to work:
- A bash command line (see the above tutorial to install one on Windows).
- An x86-64 CPU (required for lifelib to work).
- The packages
g++,python3,git, andmake. - A C compiler (
gccorclang).
Installing ikpx2
Now that you have your dependencies, it is time to install ikpx2. But first, you will need to clone ikpx2. To do so, use this command:
git clone https://gitlab.com/apgoucher/ikpx2 cd ikpx2
Compiling
ikpx2 requires that you recompile the program each time you want to change the rule. The syntax looks like this:
./recompile.sh --rule RULE
We are going to compile ikpx2 for Conway's Game of Life in this tutorial, so use
./recompile.sh --rule b3s23
The first time ikpx2 compiles, it needs to build the SAT solvers it uses, which could take some time. Subsequent builds are faster because it does not need to rebuild the SAT solvers.
Searching for spaceships
Now that we have ikpx2 compiled, we can start searching for spaceships. Let's try running a spaceship search for a glider, which travels at c/4d:
./ikpx2 -v 'c/4d'
This will give us the glider, along with lots of other 'spaceships', most of which are gliders following close together. To stop ikpx2 from running, press Ctrl+C.
Parallelization
Let's try a harder problem. Let's search for a c/3 spaceship:
./ikpx2 -v 'c/3'
Depending on your system, this might take a few seconds, but the first spaceship you will find is the turtle. If we want to speed this up, we will need to use parallelization. By default, ikpx2 uses up to 8 threads, but some systems support more. For example, if your system has 16 threads, you can use the following to increase the search speed:
./ikpx2 -v 'c/3' -p 16
There are several other parameters to specify/optimize your search. To see them all, type ./ikpx2 --help
Partials
You may have noticed that most of the output is not spaceships, but are partial spaceships. Here are some of the first partials printed by the c/3 search:
| c/3 partial results from the ikpx2 search (click above to open LifeViewer) |
The difference in how ikpx2 prints the partial results is that ikpx2 prints spaceships with a blue label, while partials do not use that label.
ikpx2 only prints partials if they are the longest partial seen in the search so far. This is done to avoid flooding the output with partials.
It is possible to start a spaceship search back up with an initial partial. To do this, you can navigate to your ikpx2 folder and create a text file with the RLE of the desired partial. Then simply add the file name to the end of the command. Here's an idea of what that looks like:
./ikpx2 -v 'c/8' Partial.txt
When ikpx2 is not printing partials, you will periodically see output like this:
# 256 iterations (121 problems, 330 subproblems, 135 solutions) completed: queuesize = 33; heapsize = 0; treesize = 155
The iteration count gives a sense of how long the search is running for.
Adaptive widening
When ikpx2 exhausts all possibilities of the width it is currently searching, it will widen by 1 unit. This is done in such a way as to preserve the search tree, which allows subsequent widths to be searched faster.
Long searches
Now that we know how to do an ikpx2 search, let's try doing a higher period search:
./ikpx2 -v 'c/5d'
As a general rule, searches with higher period take longer. If you let your search run for a few days or weeks, it might be able to find the spaceship we are looking for.
Contributing to ikpx2_stdin
If you haven't already, see Contributing_to_Catagolue on how to generate a Payosha256 key.
ikpx2 has a built-in apgsearch that is able to search the spaceship partials ikpx2 processes. This is useful for finding patterns such as puffers, wickstretchers, and period-multiplied spaceships. When censusing spaceship partials, apgsearch uploads to ikpx2_stdin. For example, the following command censuses all the c/4 partials that ikpx2 generates:
./ikpx2 -v 'c/4' -n NUMBER_OF_SOUPS -k PAYOSHA256_KEY
where NUMBER_OF_SOUPS is the number of soups per haul, and PAYOSHA256_KEY is the payosha256 key you use (if you contribute anonymously, use #anon).
Discovering new spaceships
Now, let's look at how you can discover new spaceships in the Game of Life and other cellular automata.
Unknown speeds
If you want to make a notable discovery using ikpx2, you will likely want to search for an unknown speed. Examples of unknown speeds include (2,1)c/7, c/8, 3c/8, and c/9d. Because ikpx2 is a depth first search program, if you let a search continue to run after finding a spaceship, it tends to find long spaceships, and after it finishes exploring the long spaceships, it finds another short spaceship. For this reason, ikpx2 is not very useful for [ reducing a spaceship that was previously discovered using ikpx2.
Another place where ikpx2 can be useful is other cellular automata. To explore another cellular automata, simply recompile ikpx2 with the rule you want to use. For example:
./recompile.sh --rule b36s23
will compile ikpx2 for OCA:HighLife. Most of the time, a rule will have a spaceship stamp collection with a spaceship that others have discovered. Look for an unknown speed in that stamp collection, and set ikpx2 to search for that speed. Otherwise, assume no one has searched in that rule before.
Posting your spaceships
If it is in Conway's Life, post it in the Spaceship Discussion thread. If it is in another cellular automata, post it in the thread where you found that cellular automata.
| |||||||||||||||||