A new spaceship search approach

For scripts to aid with computation or simulation in cellular automata.
mscibing
Posts: 89
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » January 3rd, 2021, 12:31 pm

AforAmpere wrote:
December 31st, 2020, 7:59 pm
Why was this shorter ship not found on the width 16 search even though it is of a smaller width? Is this something to be concerned about?
Yes this is something to be concerned about.
Dylan Chen wrote:
December 31st, 2020, 10:21 pm
The first LSSS search I did was the w15o on Dec21. That time all 00-15seed report Negtive.(even before i got sleep, so that is minor than 5hrs)

The version is the same Oct version I forked from LSSS.
Thanks for the report. This has me quite baffled. I'm going to checkout the version from Oct and see if I can reproduce issues with w15o. My thinking is that different results from different runs is pointing to a data race somehow. The non-determinism from the threading can affect file sizes and the partials chosen, but if the contents of slice_counts.csv is different for different runs of the same parameters then something's gone wrong.

Update: I'm seeing differences in slice_counts.csv from run to run. They're small differences and they sometimes take a few hours to show up, but they're there. It may take me some time to figure out what's gone wrong, but right now no negative results from lsss can be trusted.
-- Andrew Wade

Dylan Chen
Posts: 113
Joined: March 27th, 2020, 8:07 am
Contact:

Re: A new spaceship search approach

Post by Dylan Chen » January 6th, 2021, 1:27 am

1. do you mean "if the search was started with gutter symmetry and switched at some point" in the other post ?
the anwser is no. I haven't tried gutter before. the symmetry is odd without change.

2. yes, the trust issue of "negtive result" got us some trouble. but it have a little bit of "advantage" that it would be good leaving some room(chance) for the future new-bees.
Like the discovery of loafer (2013)

I would never mind because currently I'd like to "figure out which width argument is sweet zone and which one is unfeasible". to get a better decision of what to do in next phase.
Tools should not be the limit.
Whether your obstacle is a script, an stdin, or Linux environment computing resouces.
check New rules thread for help.

mscibing
Posts: 89
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » January 7th, 2021, 10:32 pm

Dylan Chen wrote:
January 6th, 2021, 1:27 am
1. do you mean "if the search was started with gutter symmetry and switched at some point" in the other post ?
the anwser is no.
That's what I meant, yes. Ah well. I though I was on to something when I saw the slice counts change, but now I'm just stuck. I do have some comments I'll be adding to the source code for future reference. Maybe I'll start plugging away on an automated test suite, but that's not going to happen soon.
-- Andrew Wade

Dylan Chen
Posts: 113
Joined: March 27th, 2020, 8:07 am
Contact:

Re: A new spaceship search approach

Post by Dylan Chen » January 11th, 2021, 10:44 pm

Hi Andrew!

When it comes to knight search, how does LSSS slices the partials ?


is there any tips to run that?

if it is vertical to the "main moving direction", would it be slower to get a potential ship?
Attachments
vertical file1.png
vertical file1.png (15.93 KiB) Viewed 2805 times
orth file1.png
orth file1.png (13.87 KiB) Viewed 2805 times
Tools should not be the limit.
Whether your obstacle is a script, an stdin, or Linux environment computing resouces.
check New rules thread for help.

mscibing
Posts: 89
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » January 17th, 2021, 8:59 pm

Dylan Chen wrote:
January 11th, 2021, 10:44 pm
Hi Andrew!

When it comes to knight search, how does LSSS slices the partials ?
Hi Dylan,

The slices run perpendicular to the direction the partials are advanced. So a (2,1)c/6 search would correspond to your second picture with the slices vertical, and the overall search top to bottom.

I strongly suspect a (1,2)c/6 search will run slower than a (2,1)c/6 search, but I haven't tested this. If you do run a (1,2)c/6 search use the latest version of the program; there are some recent bugfixes that will impact that velocity.
-- Andrew Wade

User avatar
LaundryPizza03
Posts: 1350
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: A new spaceship search approach

Post by LaundryPizza03 » January 19th, 2021, 12:41 pm

Partial printout is broken. Error message:

Code: Select all

error: UnrecognizedOption("min_distance")
search2.sh: line 297: [: -eq: unary operator expected

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 31531 spaceships and 1293 oscillators from outer-totalistic rules. You are invited to help!

Dylan Chen
Posts: 113
Joined: March 27th, 2020, 8:07 am
Contact:

Re: A new spaceship search approach

Post by Dylan Chen » January 22nd, 2021, 7:57 pm

some final 4c9 partial.

Code: Select all

#1
dev/shm/04/data# cat 0525.partial.txt(g14-4c9)

#2
gutter15-4c9/04/data# cat 0535.partial.txt

#3
w14o-4c9/04/data# cat 0535.partial.txt
you can see the similarity of g14(#1)&g15(#2).
and coincidently, gutter15 (#2) and odd14(#3) stopped at the same number 0535.

Code: Select all

x = 61, y = 111, rule = B3/S23
56b2o$39bo15bobo$23b2o11b2obo6bo3b6o$13b4o2b3ob5o7bo9b2ob2ob3o3b2o$12b
o4b2obo4b4o5bo4b2o4bo6bo2bobo$5bo2bo3bo9b3o2b2o4bo3bob2o2bo2bo3b2o5bo$
4bo5bo5b2o6bob2o5bo5bo2b3obo3bo3b2obo$2bo7bo2b2o4bob3o5b2ob3ob2o3b3o6b
3ob2ob2o$bo2b2o5bobo5bo6bo3bo6bo10b2o8bo$o4b3o3bob3ob2ob3o6bobobo3bo7b
o2b2o8bo$bo2bob2o2bo4b2o5bobobobo3b4ob2o3b4o6b3ob3o$2b3ob2o9bo4bobobo
4bo2bob2obobobo2b2o3b3obobo$4bob2o10b5o3bo6b2ob2o3b2o10bob2o$22b4o7b2o
3b5o2$22b4o7b2o3b5o$4bob2o10b5o3bo6b2ob2o3b2o10bob2o$2b3ob2o9bo4bobobo
4bo2bob2obobobo2b2o3b3obobo$bo2bob2o2bo4b2o5bobobobo3b4ob2o3b4o6b3ob3o
$o4b3o3bob3ob2ob3o6bobobo3bo7bo2b2o8bo$bo2b2o5bobo5bo6bo3bo6bo10b2o8bo
$2bo7bo2b2o4bob3o5b2ob3ob2o3b3o6b3ob2ob2o$4bo5bo5b2o6bob2o5bo5bo2b3obo
3bo3b2obo$5bo2bo3bo9b3o2b2o4bo3bob2o2bo2bo3b2o5bo$12bo4b2obo4b4o5bo4b
2o4bo6bo2bobo$13b4o2b3ob5o7bo9b2ob2ob3o3b2o$23b2o11b2obo6bo3b6o$39bo
15bobo$56b2o11$58bo$56b2o$39bo15bob2o$23b2o11b2obo6bo3b6obo$13b4o2b3ob
5o7bo9b2ob2ob3o2b2obo$12bo4b2obo4b4o5bo4b2o4bo6bo4b2o$5bo2bo3bo9b3o2b
2o4bo3bob2o2bo2bo3b2o7bo$4bo5bo5b2o6bob2o5bo5bo2b3obo3bo3b2o$2bo7bo2b
2o4bob3o5b2ob3ob2o3b3o6b3ob2o2b2o$bo2b2o5bobo5bo6bo3bo6bo10b2o7b2o$o4b
3o3bob3ob2ob3o6bobobo3bo7bo2b2o9bo$bo2bob2o2bo4b2o5bobobobo3b4ob2o3b4o
6b3o4bo$2b3ob2o9bo4bobobo4bo2bob2obobobo2b2o3b3ob2obo$4bob2o10b5o3bo6b
2ob2o3b2o10bob2o2bo$22b4o7b2o3b5o16bo2$22b4o7b2o3b5o16bo$4bob2o10b5o3b
o6b2ob2o3b2o10bob2o2bo$2b3ob2o9bo4bobobo4bo2bob2obobobo2b2o3b3ob2obo$b
o2bob2o2bo4b2o5bobobobo3b4ob2o3b4o6b3o4bo$o4b3o3bob3ob2ob3o6bobobo3bo
7bo2b2o9bo$bo2b2o5bobo5bo6bo3bo6bo10b2o7b2o$2bo7bo2b2o4bob3o5b2ob3ob2o
3b3o6b3ob2o2b2o$4bo5bo5b2o6bob2o5bo5bo2b3obo3bo3b2o$5bo2bo3bo9b3o2b2o
4bo3bob2o2bo2bo3b2o7bo$12bo4b2obo4b4o5bo4b2o4bo6bo4b2o$13b4o2b3ob5o7bo
9b2ob2ob3o2b2obo$23b2o11b2obo6bo3b6obo$39bo15bob2o$56b2o$58bo15$38bo
15bo2bobo$14b2o4bob2o2bo9bobo7b4obo2bo2bobo$13b11o4bo6b2ob3o4b7o3bobob
o$12bob5obo13bo3b3o3b2ob3o2bo5b2o$11bo4bobo4b2o8b2o6b3ob2o5bobo$9bobob
o7bo2b4obo6b2obo4bo5bo3bobo2bo$3b3o4b5o3bobob2ob3ob6ob3o2bo5bobo6bo2bo
$bo2b2o4b2o3bo3bo3bo10bo2b2o3bob3o2b2o2bo3bo$2o5bo2b2obobob7obobob3obo
3bo5bo3b2obo2bo2bo$b2obo3bo6bo2bo3bo4bo2b2o3bo6b4o2b2o3bo$2bobo3bo7b5o
bo3bo13b2o2bo2b2o5bo4b2o$4bob2o10b3o5bo5bo3bo6bo3b2o7b5o$19b2ob4o7b3ob
4obo3bo8bo3b2o$46bo2bo6bo2b2o$19b2ob4o7b3ob4obo3bo8bo3b2o$4bob2o10b3o
5bo5bo3bo6bo3b2o7b5o$2bobo3bo7b5obo3bo13b2o2bo2b2o5bo4b2o$b2obo3bo6bo
2bo3bo4bo2b2o3bo6b4o2b2o3bo$2o5bo2b2obobob7obobob3obo3bo5bo3b2obo2bo2b
o$bo2b2o4b2o3bo3bo3bo10bo2b2o3bob3o2b2o2bo3bo$3b3o4b5o3bobob2ob3ob6ob
3o2bo5bobo6bo2bo$9bobobo7bo2b4obo6b2obo4bo5bo3bobo2bo$11bo4bobo4b2o8b
2o6b3ob2o5bobo$12bob5obo13bo3b3o3b2ob3o2bo5b2o$13b11o4bo6b2ob3o4b7o3bo
bobo$14b2o4bob2o2bo9bobo7b4obo2bo2bobo$38bo15bo2bobo!


have a nice search voyage~
Tools should not be the limit.
Whether your obstacle is a script, an stdin, or Linux environment computing resouces.
check New rules thread for help.

Dylan Chen
Posts: 113
Joined: March 27th, 2020, 8:07 am
Contact:

Re: A new spaceship search approach

Post by Dylan Chen » January 26th, 2021, 8:29 am

some personal notations of LSSS/search.sh

for the reading of source code

Code: Select all


[7] # echo 0000 > data/stopafter
# to cease the search program

[68] mem=4000000000 #byte
# allocate proper memory for you search

[114]  for s in `seq -w 1 29`
# from 01,02,03 ... to 29

[139]    echo $token > $data/token || exit 1
#     '||' means that, right sentence would executed only when left sentence failed 
#  'exit 1'   tells you, the program exit due to some err

[80-140] # this part made the folder 'data/0010'

[144] # the following part would make folder 'data/{0011..9999}'

[149] # remember in line 139 we have made $token='0010/done'

[152] # 'du' would return the size of folder, as well as its sub-folder 
# data/search.log would store the date and the size of folders

[153]# this is the 0010/done you saw on the terminal

[154]# if greater than 'data/stopafter' then exit

[157]# we join the slices in lsss


it's a joy to see the fluctuate of the program
Attachments
LSSS htop - disk write and read.png
LSSS htop - disk write and read.png (95.13 KiB) Viewed 2546 times
Tools should not be the limit.
Whether your obstacle is a script, an stdin, or Linux environment computing resouces.
check New rules thread for help.

Dylan Chen
Posts: 113
Joined: March 27th, 2020, 8:07 am
Contact:

Re: A new spaceship search approach

Post by Dylan Chen » January 27th, 2021, 10:58 am

sorry to post again.

my spot price machine got some trouble, the program ceased.

<err code>

Code: Select all

 ./new-search.sh 
0132/13
mkdir: cannot create directory ‘data/0132/12’: File exists
error: Custom { kind: UnexpectedEof, error: "Invalid Header in data/0132/13/r_000.slice" }

the r_000.slice in that folder is empty, the whole data folder is 59GB,

is there any way to resume the search ?


edit 1
20210128

current files preserved on the disk

Code: Select all

token=0132/13


folder:

0132/{15..14}  13 is empty

0131/{00..12}  no 13 folder

that not a good news. maybe the 13 is in the memory right at the time the machine ceased.
Tools should not be the limit.
Whether your obstacle is a script, an stdin, or Linux environment computing resouces.
check New rules thread for help.

mscibing
Posts: 89
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » January 31st, 2021, 12:15 pm

Unfortunately there is no way to recover the search in that situation.

EDIT: Actually there may be something I can do. I'll try to come up with a script to recover the missing slices from their neighbours.

I'm testing out an approach and should have it ready by the end of Wednesday.
-- Andrew Wade

Dylan Chen
Posts: 113
Joined: March 27th, 2020, 8:07 am
Contact:

Re: A new spaceship search approach

Post by Dylan Chen » February 6th, 2021, 5:01 am

My search 'tool' is some rented cloud machines, at spot price. (In order to save cost, they maybe released at any time. )
Recent days,I found that their NAS has the same speed to an HDD (R/W at 150+MB/s) , and the speed will increase linearly with the total storage, so I could get 200+MB/s when the LSSS data folder reach 300GB.


The NAS can be attached to multiply machines. Is it possible, to cluster some instance(like multiply 16v32G machines), using the shared NAS as an interchange,to search LSSS spaceships ?

(it is basically impolitely asking you to make a supercomputer based on some distribued machines :oops: )


Edit1: the inner net of these instance/machines is 10Gbps, that is roughly 1.25GB/s,could this be help?
Edit2: the best way to learn program:do some search in CA (I am reading the book, yes the rust introduction book)
Edit3: everyone should check the the new commit of LSSS, it has recover-script now. (Tks Andrew, we really appreciate that)

Edit4: yes, the mem= and flush in search.sh should be set higher, the value I set is usually to half of the memory. eg: 16000000000(15GB) in a 32G(30.4GB) instance.
Last edited by Dylan Chen on February 6th, 2021, 10:41 pm, edited 2 times in total.
Tools should not be the limit.
Whether your obstacle is a script, an stdin, or Linux environment computing resouces.
check New rules thread for help.

mscibing
Posts: 89
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » February 6th, 2021, 10:09 pm

Dylan Chen wrote:
February 6th, 2021, 5:01 am
Is it possible, to cluster some instance(like multiply 16v32G machines), using the shared NAS as an interchange,to search LSSS spaceships ?
Ah, well, it's not impossible exactly, but difficult enough that I'm probably not going to implement it.
Dylan Chen wrote:
February 6th, 2021, 5:01 am
(it is basically impolitely asking you to make a supercomputer based on some distribued machines :oops: )
No, that's fine, running on a cluster is something I've pondered, but I didn't have a cluster on hand so I didn't code for one. If I turn off the adaptive chunk size (which will increase disk usage), the join operation could probably be made to run under MapReduce without excessive difficulty. But I'm sure it would be a pain to install the needed parts of Hadoop on the instances and I'm not that familiar with Hadoop myself.

BTW if you notice the search not using all the cores try increasing the mem= value in the search script. The search program will use as much memory as it needs to but if it exceeds the mem= value it will temporarily block some of threads until the usage goes down. I tried to pick sensible defaults so you probably won't run into this.
-- Andrew Wade

User avatar
LaundryPizza03
Posts: 1350
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: A new spaceship search approach

Post by LaundryPizza03 » April 28th, 2021, 10:55 am

LSSS no longer works as is in macOS Big Sur.

Code: Select all

> bash search.sh
search.sh: line 97: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 132: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
search.sh: line 124: target/release/life_slice_ship_search: No such file or directory
0010/done
search.sh: line 157: target/release/life_slice_ship_search: No such file or directory

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 31531 spaceships and 1293 oscillators from outer-totalistic rules. You are invited to help!

mscibing
Posts: 89
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » May 2nd, 2021, 9:17 pm

LaundryPizza03 wrote:
April 28th, 2021, 10:55 am
LSSS no longer works as is in macOS Big Sur.
It looks like the executable doesn't exist. Try running the command:
cargo build --release
before running the search script.
-- Andrew Wade

User avatar
LaundryPizza03
Posts: 1350
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: A new spaceship search approach

Post by LaundryPizza03 » May 5th, 2021, 11:59 pm

mscibing wrote:
May 2nd, 2021, 9:17 pm
LaundryPizza03 wrote:
April 28th, 2021, 10:55 am
LSSS no longer works as is in macOS Big Sur.
It looks like the executable doesn't exist. Try running the command:
cargo build --release
before running the search script.
Thanks, although it is very sensitive about requiring bash.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 31531 spaceships and 1293 oscillators from outer-totalistic rules. You are invited to help!

AforAmpere
Posts: 1272
Joined: July 1st, 2016, 3:58 pm

Re: A new spaceship search approach

Post by AforAmpere » May 25th, 2021, 3:04 pm

I don't know if anyone else has experienced this, but on my machine (running in Ubuntu in WSL) no matter what I set the threads to in search.sh, it always uses all available anyway.
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules.

Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule

dexter1
Posts: 27
Joined: February 26th, 2020, 8:46 am

Re: A new spaceship search approach

Post by dexter1 » May 25th, 2021, 4:29 pm

AforAmpere wrote:
May 25th, 2021, 3:04 pm
I don't know if anyone else has experienced this, but on my machine (running in Ubuntu in WSL) no matter what I set the threads to in search.sh, it always uses all available anyway.
Native Ubuntu honors the threads keyword. In WSL, try forcing the number of threads by setting OMP_NUM_THREADS to the desired value.
Frank Everdij

shuich01
Posts: 19
Joined: March 27th, 2021, 8:40 pm
Location: PRC

Re: A new spaceship search approach

Post by shuich01 » June 16th, 2021, 3:00 am

I finally realized that the "odd-midline" option search for a width 2n+1 spaceship in LSSS(n is the margin).
so that's why Anura is actually 33 cells wide instead of 31 cells wide.
Just for the life...

mscibing
Posts: 89
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » June 20th, 2021, 10:08 pm

I've fixed up the use of the threads variable in the latest search.sh

Whereas before you would need to use the non-obvious:

threads="--threads 8"

It's now just:

threads=8

If you don't specify anything it defaults to the number of hardware threads.

Compiling the program now requires the latest version of rust, but the updated search.sh should work fine with older versions.
-- Andrew Wade

Post Reply