ConwayLife.com

This is a topic for discussion of Tim Coe's spaceship search program, "knight2".

Knight2 is available as a c source file in this post.

I have a question to start things off. The following search seems to terminate prematurely: Here is the output: @Tim Coe
Do you know why the search is ending?

I wonder if it might be a memory problem due to having set the -d parameter too low. I tried the same search as above but with -d 1 and -w 8, and it also terminated early. I've started a new search with -d 5 that's still running.

I haven't yet tried using the -t or -i commands when the search fails.

I notice that the output numbers in this failed search are higher than the numbers in my properly completed searches, but I'm not yet sure what that means.

Edit: The -d 5 search also failed. Trying again with -d 6 and -t

Sokwe,

Thanks for trying out knight2. This is going to be a learning experience for me in that I often leave out key information.

When the "-v" option is used the internal period is 2 higher than the command line period for algorithmic reasons. So "-p 8 -v" is operating at an internal period of 10 and an internal period of 10 does not work correctly. I will work out the details of correct operation for an internal period of 10 over the next few days and post an updated version of the source code. This will actual cover several different speeds, (4,x)/10, (3,x)/9, and (2,x)/8. I am sorry for wasting your time on the (2,x)/8 cases.

Two lines of statistics are printed out after the completion of each row (actual phase tracked). The first line is a printout of the width of the active search tree for all the previous rows. The second line contains several counts of different types of computations performed. The last number in this line of statistics is the width of the current row and the next to last number is the total memory used for search tree storage. The memory allocated for search tree storage is ROADSTORE and is currently set to 50000000. When the memory used reaches the ROADSTORE the program exits immediately.

I would recommend using "-m 3" as a command line option, as that frees a lot of memory for tree storage. I usually run with "-d 6", as for most searches that results in good performance along with no memory overflows. As the row width is increased the tree widths grow exponentially. I started my (2,1)/6 and (1,1)/5 searches before I implemented the tree compaction algorithm, and I had to run them at "-d 12" and "-d 14" in order to safely avoid overflowing memory.

I almost never run with the "-t" option and to date have only run the knightship search with it set.

I will post an example of using the "-i" option over the next few days.

I welcome your continued comments about your experiences with knight2.

Have a happy day,

-Tim Coe

I tried in order to search for 2c/6 spaceships, but what I get is which is a c/3 spaceship.

When changing -w 10 into -w 6, the output seems quite normal: Is there anything wrong with the -h command?

EDIT: Changing the -h parameter into 5 works.

moebius wrote:So "-p 8 -v" is operating at an internal period of 10 and an internal period of 10 does not work correctly.

Is this a problem specific to period-10, or does it affect all -v searches? For example, would this affect a (1,0)c/6 or (1,1)c/6 search?

@Bullet51,
The code does a check for HYPEROW >= 2 (line 1743), that I suspect has something to do with it. Setting -h 2 seems to prevent the p3 ship from being output.

Sokwe,

When knight2 is instructed to search (1,0)/6 or (1,1)/6 is will indeed be operating at period 8 internally. Knight2 functions fine at this setting.

-Tim Coe

Chopping a job up in knight2 and distributing it across several scalar CPUs

Over the years I have primarily used UNIX head, tail, and cat to chop jobs up. This was highly manual but workable. Under DOS this is way too much of a pain. So last weekend I modified a few lines of code in knight2.c to make a somewhat easier to distribute the chopped up jobs. I haven't actually made the modifications on the code on this machine, so I am going to make them right now and describe what I am doing. I don't want to just post the whole source code because I have also made a variety of other modifications, none of which I have documented.

Near the top of the code add a couple of variables:
At roughly line 203 in the processing of command line inputs change
to
At about line 500 change
to
What this is doing is skipping over the first "BASEIN" entries of the read in search tree prior before starting the first phase of searching. Later we will turn off INTREE.

At about line 2065 change
to
This is checking to see if at least "CHOPIN" entries have been processed on this first processed phase, and if so skip over the rest of the entries and set the termination condition for the phase processing.

At about line 2068 change
to
After the first phase processed is finished, turn off INTREE.

To use this suppose you run
After about 15 phase you think it is going to slow and want to parallelize it. First kill your original job. Then look at the last #D line which might look like this
The "40100" is the number of entries in the last recorded phase. What I do is open a bunch of command prompt windows in DOS and in each window I submit a cut up job as follows:
.
.
. There are probably better ways to work DOS, but I don't know them.

In UNIX I just put an "&" after each command and run them in the background.

You do not want to have more jobs running than you have logical processors on your machine. In fact you generally want to leave at least one logical processor free, because "knight2" sticks to processors much better than the many other processes (in particular internet browsing).

It does work to take advantage of hyperthreading. On a CORE I7 I run 7 jobs simultaneously and things seem to be working well.

Have a happy day,

-Tim Coe

I am including the source code for my latest search program "knightt".

I wrote this program to investigate the complete spaceship trees for spaceships of a given speed, period, and symmetry. As part of the run the smallest ship containing each unique (2*PERIOD + 1) phases of a row that is in any ship of the given type is printed out. Effectively this set of printed ships gives a recipe for constructing all ships of the given type.

This printout can be a vast armada of ships. I enjoy just watching the armada scroll by, and sometimes perturbing it and watching it blow up. I am posting "knightt" mainly so that others who want to experiment with vast armadas of ships may do so.

Knightt can be compiled from the command line as follows in unix and dos:

gcc -O3 knightt.c -o knightt

cl /O2 knightt.c

The help screen is out of date and not to be relied upon.

Run knightt using the following options:

-p <PERIOD> Must be greater than or equal to 3
-x <XMOVE> The only speeds currently supported are 1/N and N/(2*N + 1), default XMOVE is 1

-d <DEPTH> I usually set this to 8 times the PERIOD. For period 4 this means 32

-o
-e These are the symmetry modes. If none are asserted gutter is assumed.
-n

-u <UNIQUE> By setting a positive value on this the required uniqueness for printing ships is increased

No other options are guaranteed to work.

When operating knightt I recommend that you first run some very quick runs from the command line and watch what gets printed out. Then increase the width by one and try again. For example:

knightt -p 3 -d 24 -e -w 6
knightt -p 3 -d 24 -e -w 7
knightt -p 3 -d 24 -e -w 8
knightt -p 3 -d 24 -e -w 9

Then you can pipe the output to a file and then filter the file and view it in Golly:

knightt -p 3 -d 24 -e -w 7 > knt_1o3e_7
findstr /v "D" > knt_1o3e_7.lif

Alternatively you could run the filter straight away and view it in Golly immediately:

knightt -p 3 -e -w 8 | findstr /v "D" > knt_1o3e_8.lif

I will be happy to answer any questions.

Have a happy day,

-Tim Coe