This program searches random initial configurations in Conway's Game of Life and periodically uploads results to a remote server. You can read more information about the distributed search at the following URL:
An automatic live Twitter feed of new discoveries found by the search was established by Ivan Fomichev:
There is also an automatically-updated summary page, with animations of interesting objects and various charts:
The search was originally performed by people running instances of a Python script; this repository contains the source code for a C++ program which is 20 times faster. The prefix 'apg-' stands for Ash Pattern Generator and the suffix '-luxe' refers to the capabilities vis-a-vis previous versions (apgmera, apgnano, and apgsearch).
Note: apgluxe can only run on x86-64 machines. If you have an ancient computer, then the recommended alternative is the Python script.
This program is designed to be compiled using gcc or clang. If you
have one of these compilers installed, then building apgluxe is as
simple as running:
bash recompile.sh
in the repository directory. If compilation succeeded, the last two lines should resemble the following:
apgluxe v5.0-ll2.2.0: Rule b3s23 is correctly configured.
apgluxe v5.0-ll2.2.0: Symmetry C1 is correctly configured.
which means you are ready to run the program like so:
./apgluxe [OPTIONS]
The options may include, for example:
-k mypasswordUpload soups where 'mypassword' is your key-n 5000000Run 5000000 soups per upload-p 4Parallelise across 4 threads--rule b36s245Run the custom rule B36/S245--symmetry D2_+1Run soups with odd bilateral symmetry-L 1Save a local log of each haul-t 1Disable uploading to Catagolue-i 10Upload exactly 10 hauls before exiting-v 5Peer-verify 5 hauls for every haul uploaded--maxpop 10000Skip soups with a maximum population larger than 10000--maxgen 180000Skip soups that run for longer than 180000 generations
This invocation will upload results every 20 million soups:
./apgluxe -n 20000000
If you want to upload soups non-anonymously, use the -k flag and provide a valid payosha256 key. The correct syntax is as follows:
./apgluxe -n 20000000 -k mykey
where 'mykey' is replaced with your payosha256 key (available from https://catagolue.hatsya.com/payosha256 -- note the case-sensitivity). Omitting this parameter will cause soups to be uploaded anonymously.
If you have a quad-core computer and would prefer not to run four separate instances, then use the -p command to parallelise:
./apgluxe -n 20000000 -k mykey -p 4
This will use C++11 multithreading to parallelise across 4 threads, thus producing and uploading soups approximately four times more quickly. Note that this does not work on Cygwin.
Compiling and running apgluxe is easy, as explained above. To download the source code, use the following command:
git clone https://gitlab.com/apgoucher/apgmera.git
Then you can enter the directory and compile the search program using:
cd apgmera
./recompile.sh
If the online repository is updated at all, you can update your local copy in-place by running:
git pull
in the repository directory.
Apple M1 chips use a different instruction set, namely ARMv8, so
emulation is required to use apgsearch. In particular, you need to
ensure that Rosetta 2 is installed and use the arch command as
follows:
arch -x86_64 ./recompile.sh
Even though this uses emulation (traditionally slow), the Apple M1 chip is surprisingly fast at emulating an x86_64 processor and runs apgsearch at a comparable speed to a pre-Haswell processor.
Even though the Cygwin64 solution above will work perfectly on Windows 10, one user noted that it does not fully utilise the processor. Instead, you are encouraged to use WSL bash as described here.
It seems that the order of magnitude difference quoted above is on the extreme side; other users report a 20 percent difference between WSL, VirtualBox, and Cygwin64 (in descending order of speed).
Moreover, these comparisons were performed with the old threading model (OpenMP threads), whereas apgluxe has subsequently migrated to pure C++11 threads for increased cross-platform support.
There is a precompiled Windows binary, only for b3s23/C1, available from
here.
When executed, it will prompt you for the haul size, number of CPUs to use,
and your payosha256 key. For
finer control, it can be run from the Command Prompt with any combination
of the options mentioned in the Example Usage above.
Compiling from source has the advantage of allowing other rules and symmetries to be explored. Moreover, it allows certain optimisations to be applied to specifically target the machine you're using, conferring a marginal speed boost.
Install Cygwin64 (from https://cygwin.com), ensuring that the following are checked in the list of plugins to install:
- git
- make
- gcc-g++
- python (2 or 3)
Open a Cygwin terminal, which will behave identically to a Linux terminal but run inside Windows. This reduces your problem to the above case.
If you get the error stoll is not a member of std, then you are using an
old version of GCC. Run the Cygwin setup program to ensure that gcc-g++ is
updated.
Note that the -p option for parallelisation does not work in Cygwin.
There are several compilation flags that can be used for accelerated searching.
If you have an NVIDIA GPU with at least 1.5 GB of memory, then it can be used as a 'preprocessor' which discards uninteresting soups and delegates the interesting soups to the CPU search program. Compilation uses:
./recompile.sh --cuda
Note that the program will upload to a different census (b3s23/G1 instead of b3s23/C1) as the process of discarding uninteresting soups heavily distorts the census results. Work is in progress to allow the GPU to census soups itself, thereby allowing CUDA-accelerated searching of b3s23/C1.
It will default to using the whole GPU (device 0, unless you explicitly
change CUDA_VISIBLE_DEVICES as explained in the next section) as a soup
preprocessor and 8 CPU threads to census the interesting soups. If you
have a very powerful GPU and it is under-utilised, you may want to increase
the number of CPU threads using the -p flag:
./apgluxe -n 1000000000 -p 12 -k mykey
This is particularly pertinent for the NVIDIA Volta V100 and RTX 2080 Ti GPUs, which can each manage 1 080 000 soups per second if sufficiently many CPU threads are being used. The Ampere A100 should theoretically be able to manage considerably more than that, provided the number of threads is high enough.
You can see the CPU usage using htop and the GPU usage using:
watch -n 0.1 nvidia-smi
If the GPU utilisation is significantly below 100% for a significant amount of time, then increasing the number of threads is recommended.
Each process can only utilise a single GPU. The CUDA_VISIBLE_DEVICES
environment variable allows you to select the GPU to use (this is a standard
part of the CUDA runtime, and not a feature of apgsearch specifically). For
example, to run a process on GPU 3, use:
CUDA_VISIBLE_DEVICES=3 ./apgluxe [OPTIONS]
This requires you to have firstly compiled with ./recompile.sh --cuda as
described in the previous section.
To search on multiple GPUs, run one process on each GPU. You might want to create a Bash script resembling the following (with one line per device) so that you can conveniently run a process per GPU:
#!/bin/bash
KEY="insert_your_key_here"
CPU_THREADS=8
CUDA_VISIBLE_DEVICES=0 ./apgluxe -p "$CPU_THREADS" -n 1000000000 -k "$KEY" &
CUDA_VISIBLE_DEVICES=1 ./apgluxe -p "$CPU_THREADS" -n 1100000000 -k "$KEY" &
CUDA_VISIBLE_DEVICES=2 ./apgluxe -p "$CPU_THREADS" -n 1200000000 -k "$KEY" &
CUDA_VISIBLE_DEVICES=3 ./apgluxe -p "$CPU_THREADS" -n 1300000000 -k "$KEY" &
CUDA_VISIBLE_DEVICES=4 ./apgluxe -p "$CPU_THREADS" -n 1400000000 -k "$KEY" &
CUDA_VISIBLE_DEVICES=5 ./apgluxe -p "$CPU_THREADS" -n 1500000000 -k "$KEY" &
CUDA_VISIBLE_DEVICES=6 ./apgluxe -p "$CPU_THREADS" -n 1600000000 -k "$KEY" &
CUDA_VISIBLE_DEVICES=7 ./apgluxe -p "$CPU_THREADS" -n 1700000000 -k "$KEY" &
wait
Warning: The output to the terminal may look confusing and bizarre because it contains the interleaved output from all of these processes. This is to be expected and is no cause for concern.
Profile-guided optimisation can be enabled with:
./recompile.sh --profile
This is only supported for the compilers GCC and Clang, rather than nvcc, so is specific to CPU searching. The benefits are relatively mild.
These can be enabled by using the --maxpop and/or the --maxgen arguments as such
./recompile.sh --maxpop 10000 --maxgen 180000
This is useful for searching rules that may explode on some soups. The hauls will be uploaded to separate symmetries such as C1_spaceinvaders to avoid mixing hauls with regular symmetries.
The software apgluxe and lifelib are both written by Adam P. Goucher and
available under an MIT licence. Thanks go to Dave Greene, Tom Rokicki, 'Apple
Bottom', Darren Li, Arthur O'Dwyer, and Tod Hagan for contributions,
suggestions, testing, and feedback.
All third-party components are similarly free and open-source:
- 'CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme' is Licensed under Creative Commons License CC-BY 4.0;
- The SHA3 (Keccak) hash function implementation, by Dr. Markku-Juhani O. Saarinen, is available under an MIT licence;
- The SHA-256 hash function implementation, by Olivier Gay, is available under a BSD 3-clause licence;
- The 'RSA Data Security, Inc. MD5 Message-Digest Algorithm' reference implementation can be copied, modified and used under the condition that the copyright notice is included;
- The 'HappyHTTP' library, by Ben Campbell, can be copied, modified and used under the condition that the copyright notice is included.