globins wrote: ↑
March 11th, 2020, 3:10 pm
Which search program is the best for completing (or finding) partial spaceship results in rules other than B3/S23? I noticed an interesting orthogonal partial in a random soup in B36/S1258, but I don't know which program to download to attempt to complete it. Also, would it be best to use a different program for diagonal ships than for orthogonal ones?
This is a complex question but I'll attempt to answer it and also answer your question from the zfind thread at the same time.
globins wrote: ↑
March 15th, 2020, 2:04 pm
You recommended using gfind for larger widths. What's the difference between that and qfind?
Here's a brief description of the different search programs, for more comprehensive (and accurate) descriptions you should read up on the references which you can find from the links I've provided. Sorry these aren't the most direct references, but information on many of these programs is a bit scattered.
is a hybrid BFS/DFS search program which supports searching for spaceships in outer-totalistic (OT) CA rules. It builds up partial spaceships row by row, but uses small look up tables to determine the CA evolution across the whole row. The breadth first search (BFS) phase of the search fills a search queue with all the partials found up to the current length (also called depth). The depth first search (DFS) phase of the search examines each partial and attempts to extend it to the current deepening level. Any partials which can't be extended are discarded. At the end of the DFS phase the deepening level is incremented and the search returns to the BFS phase. In this way the search can find (almost) all spaceships roughly ordered from shortest to longest.
is a purely DFS search. It's great advantage is that the lookup tables used return the evolution of the whole row in one lookup. This necessarily makes the tables much larger than for gfind which is why the maximum search width is restricted. Because the search is depth first the first spaceship found may be very long, or very short, and the search could spend a long time exploring unsuccessful partials before finding a ship or it could get lucky and find a ship very quickly.
A particularly useful discussion of some of the internals of zfind can be found here: https://conwaylife.com/forums/viewtopic ... 499#p41499
is a later version of zfind with two main improvements: It has better performance combined with reduced RAM requirements due to reductions in the LUT size (as well as on demand creation of the LUT) and it natively supports isotropic non-totalistic (INT) rules as well as OT rules.
is a hybrid between gfind and zfind. It is primarily based on gfind and uses the same hybrid BFS/DFS strategy, but it uses zfind's whole row LUT approach to determine the evolution of the rows. qfind also uses multi-threading to parallelise the DFS phase of the search.
The main alternative to these dedicated spaceship searching programs are JLS and WLS which are based on the Lifesrc algorithm. These programs search cell by cell and are generally slower, but much more flexible in setting up custom searches.
As far as extending partials goes: ntzfind and qfind make this fairly easy, but doing so with gfind is tricky. Extending partials with JLS and WLS is straightforward.
And for searching diagonal spaceships gfind or JLS/WLS are the best option. zfind and qfind can search for diagonal spaceships with speeds of 1c/P, but don't support diagonal symmetry.
A brief overview of other CA search software can be found here: https://conwaylife.com/wiki/Tutorials/Software