Knight2
Re: Knight2
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
Code: Select all
-p 8 -d 4 -v -n -w 9
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
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
Re: Knight2
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
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
Re: Knight2
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.
Code: Select all
knight -p 6 -e -w 10 -h 1 -d 6
Code: Select all
.....**......**
.......*.**.*
...*..***..***..*
..*.....*..*.....*
...***.**..**.***
.......*....*
........*..*
......**.**.**
.......**..**
.....*.*....*.*
.....**......**
.....**.*..*.**
.........**
When changing -w 10 into -w 6, the output seems quite normal:
Code: Select all
.**......**
.**......**
**........**
.
...*.**.*
...**..**
....****
.*........*
..***..***
..*..**..*
.****..****
*.*......*.*
.*........*
.**......**
...*.**.*
.....**
.....**
EDIT: Changing the -h parameter into 5 works.
Still drifting.
Re: Knight2
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?moebius wrote:So "-p 8 -v" is operating at an internal period of 10 and an internal period of 10 does not work correctly.
@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
Re: Knight2
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
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
Re: Knight2
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
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;
Code: Select all
case 'i':
INTREE = 1;
break;
Code: Select all
case 'i':
INTREE = 1;
--argc;
sscanf(*++argv, "%d", &BASEIN);
--argc;
sscanf(*++argv, "%d", &CHOPIN);
break;
Code: Select all
firsthit = onroad;
Code: Select all
if (INTREE) onroad += BASEIN;
firsthit = onroad;
At about line 2065 change
Code: Select all
onroad++;
Code: Select all
onroad++;
if (INTREE && (onroad >= (firsthit + CHOPIN))) onroad = offroad;
At about line 2068 change
Code: Select all
tempcpt = glist + 2*PERIOD;
Code: Select all
INTREE = 0;
tempcpt = glist + 2*PERIOD;
To use this suppose you run
Code: Select all
knight2 -p 4 -d 6 -o -t -w 11 > kn2out_1o4o_11
Code: Select all
#D 15 0 138365390 0 114825173 0 93710064 0 313203922 0 21022011 149266 40100
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
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
Re: Knight2
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
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