Knight2

For scripts to aid with computation or simulation in cellular automata.
Post Reply
Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Knight2

Post by Sokwe » December 19th, 2015, 3:43 am

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.
-Matthias Merzenich

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Knight2

Post by Sokwe » December 19th, 2015, 4:30 am

I have a question to start things off. The following search seems to terminate prematurely:

Code: Select all

-p 8 -d 4 -v -n -w 9
Here is the output:

Code: Select all

#D 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
#D 1 0 2180 0 2161 0 1895 0 4394 0 198 15 14
#D
#D 2 0 21021 0 20578 0 18258 0 46557 0 958 178 163
#D 14
#D 3 0 246091 0 117728 0 54000 0 559229 0 82062 20218 20040
#D 14 163
#D 4 0 25170424 0 19470266 0 11362637 0 53624972 0 5137570 961548 941330
#D 14 163 19448
#D 5 0 253634677 0 236548252 0 173305701 0 601181214 0 52305063 6542670 5581122
#D 14 120 11027 340359
#D 6 0 318987773 0 260343457 0 203366023 0 985504855 0 121641014 22169313 15626643
#D 14 120 7573 146026 2188236
#D 7 0 299870203 0 184158805 0 138469125 0 900556368 0 113458872 34891307 12721994
@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
-Matthias Merzenich

moebius
Posts: 45
Joined: December 10th, 2015, 9:07 am

Re: Knight2

Post by moebius » December 19th, 2015, 8:31 pm

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

Bullet51
Posts: 663
Joined: July 21st, 2014, 4:35 am

Re: Knight2

Post by Bullet51 » December 20th, 2015, 12:45 am

I tried

Code: Select all

knight -p 6 -e -w 10 -h 1 -d 6
in order to search for 2c/6 spaceships, but what I get is

Code: Select all

.....**......**
.......*.**.*
...*..***..***..*
..*.....*..*.....*
...***.**..**.***
.......*....*
........*..*
......**.**.**
.......**..**
.....*.*....*.*
.....**......**
.....**.*..*.**
.........**
which is a c/3 spaceship.

When changing -w 10 into -w 6, the output seems quite normal:

Code: Select all

.**......**
.**......**
**........**
.
...*.**.*
...**..**
....****
.*........*
..***..***
..*..**..*
.****..****
*.*......*.*
.*........*
.**......**
...*.**.*
.....**
.....**
Is there anything wrong with the -h command?

EDIT: Changing the -h parameter into 5 works.
Still drifting.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Knight2

Post by Sokwe » December 20th, 2015, 6:26 am

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.
-Matthias Merzenich

moebius
Posts: 45
Joined: December 10th, 2015, 9:07 am

Re: Knight2

Post by moebius » December 20th, 2015, 3:26 pm

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

moebius
Posts: 45
Joined: December 10th, 2015, 9:07 am

Re: Knight2

Post by moebius » February 1st, 2016, 11:32 am

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:

Code: Select all

int BASEIN, CHOPIN;
At roughly line 203 in the processing of command line inputs change

Code: Select all

    case 'i':
      INTREE = 1;
      break;
to

Code: Select all

    case 'i':
      INTREE = 1;
      --argc;
      sscanf(*++argv, "%d", &BASEIN);
      --argc;
      sscanf(*++argv, "%d", &CHOPIN);
      break;
At about line 500 change

Code: Select all

  firsthit = onroad;
to

Code: Select all

  if (INTREE) onroad += BASEIN;
  firsthit = onroad;
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

Code: Select all

    onroad++;
to

Code: Select all

    onroad++;
    if (INTREE && (onroad >= (firsthit + CHOPIN))) onroad = offroad;
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

Code: Select all

  tempcpt = glist + 2*PERIOD;
to

Code: Select all

  INTREE = 0;
  tempcpt = glist + 2*PERIOD;
After the first phase processed is finished, turn off INTREE.

To use this suppose you run

Code: Select all

knight2 -p 4 -d 6 -o -t -w 11 > kn2out_1o4o_11
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

Code: Select all

#D 15 0 138365390 0 114825173 0 93710064 0 313203922 0 21022011 149266 40100
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:

Code: Select all

type kn2out_1o4o_11 | knight2 -p 4 -d 6 -o -i 0 5000 -t -w 11 > kn2out_1o4o_11_16a

Code: Select all

type kn2out_1o4o_11 | knight2 -p 4 -d 6 -o -i 5000 5000 -t -w 11 > kn2out_1o4o_11_16b
.
.
.

Code: Select all

type kn2out_1o4o_11 | knight2 -p 4 -d 6 -o -i 40000 5000 -t -w 11 > kn2out_1o4o_11_16i

Code: Select all

type kn2out_1o4o_11 | knight2 -p 4 -d 6 -o -i 45000 5100 -t -w 11 > kn2out_1o4o_11_16j
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

moebius
Posts: 45
Joined: December 10th, 2015, 9:07 am

Re: Knight2

Post by moebius » March 19th, 2016, 3:56 pm

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
Attachments
knightt.c
(92.59 KiB) Downloaded 446 times

Post Reply