Multi Period Photon Searcher

[mystical]

Multi-period photon searcher is a search program which can be used to find photons with large (or small, but its less suited for them) periods. It can be set up to search for a specific period or it can be set up to search all periods less than a maximum period. Interestingly, the time taken to search should only be linear in max period!

Edit by Sokwe: The latest version of MPPS is available here.

The main idea used here is similar to that of photonsrc (viewtopic.php?f=9&t=4649), but I came up with most of the ideas used in this program independently.

The program is not very user friendly for now, and you'll have to set some variables like max period & width in the source code itself. Some parameters like forbidden periods and the rulespace can be specified as command line arguments.

You can compile this program on linux using the command

Code: Select all

 g++ multi_period_photon_searcherv0.1.cpp -O3 -march=native -Wall -Wextra -o mpps 

and run it using (example search in B27(8)/S24(8) with forbidden periods 4 and 6)

Code: Select all

 ./mpps B27/S24 B278/S248 f 4 6 

Certain parameters need to be set directly in the part of the code where it says 'SET PARAMETERS HERE'.

The program can also search entire rulespaces rule by rule, which can be specified by setting the minrule and maxrule appropriately.
You can also set forbidden periods, which are extremely useful for certain searches. In many rules, like seeds, the program tends to get overwhelmed by p4 and p8 partials. To avoid this, you can add 4 to the list of forbidden partials given in the command and this will it skip all period 4,8,12,16,.. partials. This makes many searches much faster and helps find more interesting results.

You can also use this feature to search for ship with a specific period. For example, to perform a p14 search, you can use 'f 3 4 5 11 13' as the list of forbidden periods and set max_period to 14.

This program is still pretty unpolished and there are quite a few changes i'd like to make, including making it much more convenient to use. If any of you have any queries or suggestions on the program or if there are any bugs, I will be responding to messages here or on discord.

[Sokwe]

Very cool! By the way, I tried compiling with g++, but got the error

Code: Select all

ulti_period_photon_searcherv0.1.cpp:235:32: error: call to non-‘constexpr’ function...

This seems to be caused by using the non-constant variable birth_survival in a constexpr function. It compiled after I removed "constexpr" from lines 61 and 233.

It's a small program, but I don't have the time to code-dive right now, so I'm going to fire off some quick questions. Don't worry about answering them immediately.

Interestingly, the time taken to search should only be linear in max period!

Wow! Can you give some insight into this?

it can be set up to search all periods less than a maximum period.

Does it search periods separately, or are the different-period searches combined is some clever way? At what point does it stop searching a rule? In the example search, it produces several partials after finding ships, but it doesn't find a large number of p2 ships like I would expect.

[mystical]

Very cool!

Thanks!

By the way, I tried compiling with g++, but got the error

Code: Select all

ulti_period_photon_searcherv0.1.cpp:235:32: error: call to non-‘constexpr’ function...

This seems to be caused by using the non-constant variable birth_survival in a constexpr function. It compiled after I removed "constexpr" from lines 61 and 233.

Ah, that's a stupid error from my side. Not sure why my compiler didn't complain about it at all...

Interestingly, the time taken to search should only be linear in max period!

Wow! Can you give some insight into this?

The program basically tries all 2^w possible next rows for each partial, and then runs them for max_period gens to see if it starts repeating. If it does repeat, it is added to the queue. So, the time taken in this step is proportional to max_period and exponential in width. This is a pretty brute-force algorithm and so its not really practical for higher widths.
Its pretty simple to adapt this technique to non-photon ships too, but then it won't be possible to search multiple periods at once and the maximum width you can search will have to be very small and there are other problems too so it won't have any advantage over existing algorithms.

Does it search periods separately, or are the different-period searches combined is some clever way?

The searches for all the periods are done at the same time. It basically builds a giant tree where all the partials are the nodes. Each node has every possible extension as its children, even if they are of a higher multiple of the period. This helps it save a lot of time in many searches, for example if there are a lot of p1 partials in the rule, it searches all of them only once rather that repeating it for each period

At what point does it stop searching a rule? In the example search, it produces several partials after finding ships, but it doesn't find a large number of p2 ships like I would expect.

It stops searching a rule once it runs out of partials to extend. The reason it only finds one ship for each period is that I deliberately set it up to do that. The program keeps track of every pair of rows it has already visited and ensures that it does not visit the same pair of rows twice. This means that as soon as the end of the next ship is reached, the program detects the backend as already visited, and skips it. That's why it won't be able to list out all the ships of a certain period. The reason p2 partials were still being produced is because It can't just discard all partials of a period once a ship is found, since they might eventually have higher period extensions.

If you do want to use the program to find multiple ships, you have disable the caching feature entirely ( by setting CACHE_TILL_PERIOD to 0 ) and comment out line 412

Code: Select all

if (curr!=0 && tree[curr].is_terminated())
        {
            // don't want to show ships from periods shown already
           // if (seen_periods.insert(tree[curr].period()).e1) 
            {
		                if (minprintperiod<=tree[curr].period()) 

[mystical]

Here is version 0.2 of the program. There have been a lot of improvements over the previous version. The biggest ones are:

• You can enable parallel evolution by using the optimal5 library and genrulecode.cpp to generate code. This greatly improves speed, but can't be used in bulk searches. You will need to download optimal5 from here: https://gitlab.com/apgoucher/optimal5
• Now the program tries to find all the cells in the next row which are forced to be in some state. It uses this to greatly reduce the number of partials to check, since knowing the state of even one cell in the next row can cut the amount of partials to search into half.
• Running out of memory is now a much smaller problem, as there is an option to try and reduce memory usage when the tree gets too big.
• You can easily do bulk searches using the MULTI_RULE option.

The program can be complied similarly to v0.1, except now it need c++20. The command line arguments format is pretty much the same except you can specify a single rule more easily.

Compilation command for the main program:

Code: Select all

g++ mpps.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o mpps

Compilation command for the code generation program (Once you have set the path to optimal5 in the 2 places in the file):

Code: Select all

g++ genrulecode.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o genrc

[LaundryPizza03]

I can't seem to find information online that can resolve the following error:

Code: Select all

% g++ mpps.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o mpps
In file included from mpps.cpp:5:
In file included from ./processrule.h:1:
./common.h:53:10: fatal error: 'bits/stdc++.h' file not found
#include <bits/stdc++.h>
         ^~~~~~~~~~~~~~~
1 error generated.

I am using macOS 12.7.6 and have the latest version of gcc installed through Homebrew.

[Sokwe]

I can't seem to find information online that can resolve the following error:

Code: Select all

% g++ mpps.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o mpps
In file included from mpps.cpp:5:
In file included from ./processrule.h:1:
./common.h:53:10: fatal error: 'bits/stdc++.h' file not found
#include <bits/stdc++.h>
         ^~~~~~~~~~~~~~~
1 error generated.

I am using macOS 12.7.6 and have the latest version of gcc installed through Homebrew.

Replace the line that reads "#include <bits/stdc++.h>" in common.h (line 53) with the following:

Code: Select all

#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <chrono>
#include <deque>
#include <iostream>
#include <regex>
#include <set>
#include <span>
#include <sstream>
#include <vector>

@mystical, you should really do this as well to make the code more portable.

Edit: added "#include <regex>" so that genrulecode.cpp can also be compiled.
Edit: added "#include <algorithm>", just in case.

Edit 2:

You can enable parallel evolution by using the optimal5 library and genrulecode.cpp to generate code. This greatly improves speed, but can't be used in bulk searches. You will need to download optimal5 from here: https://gitlab.com/apgoucher/optimal5
...
Compilation command for the code generation program (Once you have set the path to optimal5 in the 2 places in the file):

Code: Select all

g++ genrulecode.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o genrc

To clarify, you will need to change line 1 ("#include "optimal5.h"") and line 40 ("opt5::Optimiser opt("knuthies.dat");") in genrulecode.cpp. My suggestion is to place the optimal5 project into a folder called "optimal5" within the same folder as genrulecode.cpp. Then you can change line 1 to "#include "optimal5/optimal5.h" and line 40 to "opt5::Optimiser opt("optimal5/knuthies.dat");".

[Sokwe]

You can enable parallel evolution by using the optimal5 library and genrulecode.cpp to generate code. This greatly improves speed, but can't be used in bulk searches. You will need to download optimal5 from here: https://gitlab.com/apgoucher/optimal5
...
Compilation command for the code generation program (Once you have set the path to optimal5 in the 2 places in the file):

Code: Select all

g++ genrulecode.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o genrc

It's somewhat annoying to have to compile a separate program, run it with the desired rule, copy the output to a non-obvious place, comment or uncomment a line in a header file, and then compile the main program. I suggest using a shell script like ikpx2's recompile.sh. For example, you could cut out lines 84-101 from processrule.h ("\\replace this with...") and paste them into a new file called pevo.h. Then add ' #include "pevo.h" ' at line 2 of processrule.h (just below ' #include "common.h" '). With this done, you could use the following script to recompile the program for a given rule:

Code: Select all

#!/bin/bash

# Usage: ./recompile.sh [--rule RULESTRING]
# If no rule is provided, mpps will be compiled without parallel evolution.

compiler="g++"

rulearg=`echo "$@" | grep -o "\\-\\-rule [^ ]*" | sed "s/\\-\\-rule\\ //"`

set -e

if ((${#rulearg} == 0)); then
echo "Rule unspecified; compiling mpps without parallel evolution..."
$compiler mpps.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o mpps

echo ""
echo "**** build process completed successfully ****"
exit 0
fi

if [ ! -f "genrc.a" ]; then
echo "Compiling genrulecode..."
$compiler genrulecode.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o genrc.a
fi

# Run genrc.a to make sure it doesn't crash due to bad input
./genrc.a $rulearg >/dev/null

echo "Generating code..."
./genrc.a $rulearg > pevo.h

echo "Compiling mpps for rule $rulearg..."
$compiler mpps.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o mpps -D PARALLEL_EVOLVE

echo ""
echo "**** build process completed successfully ****"

If the script is saved as "recompile.sh", then, for example, you can run

Code: Select all

./recompile.sh --rule B2/S0

to compile with parallel evolution for B2/S0. If you want to compile without parallel evolution, just run "./recompile.sh" without any arguments. Other parameters are still set by editing common.h.

Is there a particular reason why various parameters can't be set at run time, like width, symmetry, or max period? Would it cause the search to run slower, or is it simply a matter of not having written an option parser? If it's the former, these options could also be incorporated into recompile.sh. If it's the latter, then it might be best to write a runtime option parser.

Edit:

To clarify, you will need to change line 1 ("#include "optimal5.h"") and line 40 ("opt5::Optimiser opt("knuthies.dat");") in genrulecode.cpp. My suggestion is to place the optimal5 project into a folder called "optimal5" within the same folder as genrulecode.cpp. Then you can change line 1 to "#include "optimal5/optimal5.h" and line 40 to "opt5::Optimiser opt("optimal5/knuthies.dat");".

When you create a git repository for this project, perhaps you should include optimal5 as a submodule. Then the paths can be properly hard-coded as "optimal5/optimal5.h" and "optimal5/knuthies.dat", and "git submodule update --init --recursive" can be added to recompile.sh.

[LaundryPizza03]

I can't seem to find information online that can resolve the following error:

Code: Select all

% g++ mpps.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o mpps
In file included from mpps.cpp:5:
In file included from ./processrule.h:1:
./common.h:53:10: fatal error: 'bits/stdc++.h' file not found
#include <bits/stdc++.h>
         ^~~~~~~~~~~~~~~
1 error generated.

I am using macOS 12.7.6 and have the latest version of gcc installed through Homebrew.

Replace the line that reads "#include <bits/stdc++.h>" in common.h (line 53) with the following:

Code: Select all

#include <array>
#include <bit>
#include <cassert>
#include <chrono>
#include <deque>
#include <iostream>
#include <regex>
#include <set>
#include <span>
#include <sstream>
#include <vector>

@mystical, you should really do this as well to make the code more portable.

Edit: added "#include <regex>" so that genrulecode.cpp can also be compiled.

Word. A new compilation error involving " lexicographical_compare_three_way" in mpps.cpp:

Code: Select all

% g++ mpps.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o mpps
In file included from mpps.cpp:6:
./ds.h:32:16: error: use of undeclared identifier 'lexicographical_compare_three_way'; did you mean 'lexicographical_compare'?
        return lexicographical_compare_three_way(
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
               lexicographical_compare
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/lexicographical_compare.h:56:1: note: 'lexicographical_compare' declared here
lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
^
In file included from mpps.cpp:6:
./ds.h:32:16: error: no viable conversion from returned value of type 'bool' to function return type 'std::strong_ordering'
        return lexicographical_compare_three_way(
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:319:7: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'bool' to 'const std::strong_ordering &' for 1st argument
class strong_ordering {
      ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:319:7: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'bool' to 'std::strong_ordering &&' for 1st argument
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:323:22: note: explicit constructor is not a candidate
  explicit constexpr strong_ordering(_EqResult __v) noexcept : __value_(_ValueT(__v)) {}
                     ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:325:22: note: explicit constructor is not a candidate
  explicit constexpr strong_ordering(_OrdResult __v) noexcept : __value_(_ValueT(__v)) {}
                     ^
2 errors generated.

[Sokwe]

A new compilation error involving " lexicographical_compare_three_way" in mpps.cpp:

Code: Select all

% g++ mpps.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o mpps
In file included from mpps.cpp:6:
./ds.h:32:16: error: use of undeclared identifier 'lexicographical_compare_three_way'; did you mean 'lexicographical_compare'?
        return lexicographical_compare_three_way(
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
               lexicographical_compare
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/lexicographical_compare.h:56:1: note: 'lexicographical_compare' declared here
lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
^
In file included from mpps.cpp:6:
./ds.h:32:16: error: no viable conversion from returned value of type 'bool' to function return type 'std::strong_ordering'
        return lexicographical_compare_three_way(
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:319:7: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'bool' to 'const std::strong_ordering &' for 1st argument
class strong_ordering {
      ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:319:7: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'bool' to 'std::strong_ordering &&' for 1st argument
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:323:22: note: explicit constructor is not a candidate
  explicit constexpr strong_ordering(_EqResult __v) noexcept : __value_(_ValueT(__v)) {}
                     ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:325:22: note: explicit constructor is not a candidate
  explicit constexpr strong_ordering(_OrdResult __v) noexcept : __value_(_ValueT(__v)) {}
                     ^
2 errors generated.

Try adding a line with "#include <algorithm>". I find it interesting that the compiler seems to recognize lexicographical_compare (from c++17) but not lexicographical_compare_three_way (from c++20).

If that doesn't work, can you post what you get when you run "g++ -v"?

Please post here if you get it working or if you still get errors.

[mystical]

I have finally put up the latest version on github here: MPPS
There are quite a lot of changes in how you have to use it, hopefully making it much more convenient. More details should be in the readme file

It's somewhat annoying to have to compile a separate program, run it with the desired rule, copy the output to a non-obvious place, comment or uncomment a line in a header file, and then compile the main program. I suggest using a shell script like ikpx2's recompile.sh. For example, you could cut out lines 84-101 from processrule.h ("\\replace this with...") and paste them into a new file called pevo.h. Then add ' #include "pevo.h" ' at line 2 of processrule.h (just below ' #include "common.h" '). With this done, you could use the following script to recompile the program for a given rule:
...
If the script is saved as "recompile.sh", then, for example, you can run

Code: Select all

./recompile.sh --rule B2/S0

to compile with parallel evolution for B2/S0. If you want to compile without parallel evolution, just run "./recompile.sh" without any arguments. Other parameters are still set by editing common.h.

Thank you for the suggestions and the code! I have modified your version of recompile.sh and added it to the repo. I also got rid of bits/stdc++.h as you suggested.

Is there a particular reason why various parameters can't be set at run time, like width, symmetry, or max period? Would it cause the search to run slower, or is it simply a matter of not having written an option parser? If it's the former, these options could also be incorporated into recompile.sh. If it's the latter, then it might be best to write a runtime option parser.

Making all of known only at runtime might affect performance since the code would have to choose between the different logics at runtime and I would have to make many of the arrays dynamically sized, and it might also make it harder for the compiler to optimize. To be honest, I haven't tried setting each of them at runtime and profiling the speed, so all of this is just speculation.
I haven't written a proper option parser yet, so for now, I've just made it so you can set many of the options as arguments to recompile.sh, which is hopefully better than before.

Word. A new compilation error involving " lexicographical_compare_three_way" in mpps.cpp:

Code: Select all

% g++ mpps.cpp -O3 -march=native -Wall -Wextra -std=c++20 -o mpps
In file included from mpps.cpp:6:
./ds.h:32:16: error: use of undeclared identifier 'lexicographical_compare_three_way'; did you mean 'lexicographical_compare'?
        return lexicographical_compare_three_way(
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
               lexicographical_compare
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/lexicographical_compare.h:56:1: note: 'lexicographical_compare' declared here
lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
^
In file included from mpps.cpp:6:
./ds.h:32:16: error: no viable conversion from returned value of type 'bool' to function return type 'std::strong_ordering'
        return lexicographical_compare_three_way(
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:319:7: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'bool' to 'const std::strong_ordering &' for 1st argument
class strong_ordering {
      ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:319:7: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'bool' to 'std::strong_ordering &&' for 1st argument
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:323:22: note: explicit constructor is not a candidate
  explicit constexpr strong_ordering(_EqResult __v) noexcept : __value_(_ValueT(__v)) {}
                     ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/compare:325:22: note: explicit constructor is not a candidate
  explicit constexpr strong_ordering(_OrdResult __v) noexcept : __value_(_ValueT(__v)) {}
                     ^
2 errors generated.

Try out the new version I have put up on github. I have made the changes that should fix this. If it doesn't work, could you paste the error message here and try 'g++ -v' as Sokwe said