A new spaceship search approach

For scripts to aid with computation or simulation in cellular automata.
mscibing
Posts: 105
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: 114
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: 105
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: 114
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 9013 times
orth file1.png
orth file1.png (13.87 KiB) Viewed 9013 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: 105
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: 2295
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

Dylan Chen
Posts: 114
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: 114
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 8758 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: 114
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: 105
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: 114
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: 105
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: 2295
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

mscibing
Posts: 105
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: 2295
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

AforAmpere
Posts: 1334
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.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
dexter1
Posts: 71
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: 36
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.
Still wandering ...

mscibing
Posts: 105
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

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

Re: A new spaceship search approach

Post by AforAmpere » October 9th, 2021, 5:15 am

In hope that this may help identify what is causing LSSS to miss things, for May13's latest search here, I tried to replicate this, except having margin=75, seedcolumn=35, and maxwidth at a constant 18, instead of reducing it at some point. This ended up finding this ship, which is significantly longer:

Code: Select all

x = 83, y = 33, rule = B256/S4568
16bo$15bobo$16bobo$12bo6b3o$12bo2bo$9bo11bobo9bo$7bobo6bo3b2obobo7bo$
5bo2bob2o2bo5bob2o10bo6bobo2bo6bobo$5bo3bobobo4bobo3bo5bob3o3bo2bo8bo
2b3o$5bo7bo4bo2bobo5bo5b2o2b2obo2b2ob2ob6o2bo$4bobo5bo3bo2b3obo6bobobo
b6ob4o3b4ob3o$2bo3bobobo4bob3o2bo2bo2bo4b2ob7ob8o4b3o$2bo2bo4b3o3b7ob
2o3bob2o5b4o2b2o2bob8o4bobo2bo$3b3o3b2o2b8obo4bo9bo2b3ob3obob2o4bo7b2o
$2bobobobob12o3bo2b2o3bo7bob2ob7obo2b2obo3bo3bo$o5bobo11b5o4bo4b2o5bob
2ob6ob5ob2o$2bobo2bobo5bo5b3o2b2obo5bob3o3b9ob2ob10o2bo$3bo2b2o16b2o2b
o2bo3bo3b2ob2o2b2o3b2ob2ob9obo$ob2o2bobo16bo10bo6b2o2b4ob2ob2o2b3obob
3o2bo$3bobo22bo10bo3b5ob4o2b5o2b8obo$3bo36bo7b8obob3ob2ob3o8bobo$2b3o
38bo4bo6b5ob3o2b3o2bo9bo$bo52bob2o3bob8o3bo2bobo$56b9o2b2o3bo3bob2o2bo
$62b5o3bo2bo$64b2ob6obobo2b2o$64bo3b4o4bo3bo$75bo$74bo3bobo$78b2o$79b
3o$78bo$81bo!
I'm not sure why it missed the original ship, but this search isn't nearly as long as the Soba one was, so maybe figuring out why it is missing things could be easier with this search
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

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

Re: A new spaceship search approach

Post by mscibing » October 10th, 2021, 11:59 pm

AforAmpere wrote:
October 9th, 2021, 5:15 am
I'm not sure why it missed the original ship, but this search isn't nearly as long as the Soba one was, so maybe figuring out why it is missing things could be easier with this search
Hi AforAmpare, thanks for the report. Unfortunately I think in this case the discrepancy is probably just due to oddities in the way the --max-width works. I wasn't very accurate in the help text for --max-width, it's actually the maximum width of windows of a few rows in space extending across all phases. But the more relevant oddity here is that --max-width can miss excluding some partials that temporarily go over width. And exactly which partials it excludes could be affected by such things as the amount of memory allocated to each thread. I can't really do anything about --max-width missing partials since lsss never assembles rows. I could make it insensitive to the memory allocation, but only at the cost of making it less effective.

I am going to run some experiments with the search though to try and confirm or refute my understanding.

Edit: Are you using a version < 3.7.0 (target/release/life_slice_ship_search --version)? I reduced the window that --max-width applied to by one row in that version and that change has a bigger impact than I expected.
-- Andrew Wade

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

Re: A new spaceship search approach

Post by AforAmpere » October 11th, 2021, 6:45 pm

mscibing wrote:
October 10th, 2021, 11:59 pm
Edit: Are you using a version < 3.7.0 (target/release/life_slice_ship_search --version)? I reduced the window that --max-width applied to by one row in that version and that change has a bigger impact than I expected.
Yes, I was using 3.6.1, I'll test it with the updated version. I probably should have been doing that regardless.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: A new spaceship search approach

Post by Scorbie » November 24th, 2021, 5:38 am

May I ask how you profiled your program and made the search CPU bound instead of I/O bound, namely analyzing I/O patterns and stuff?
I'm hoping to write a similar program but am not sure where to start regarding profiling.
Maybe I'll revisit after writing such program

Also have you thought of using sqlite instead of making files?

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

Re: A new spaceship search approach

Post by mscibing » January 23rd, 2022, 9:50 pm

Scorbie wrote:
November 24th, 2021, 5:38 am
May I ask how you profiled your program and made the search CPU bound instead of I/O bound, namely analyzing I/O patterns and stuff?
I used the unix perf program for cpu profiling, and tweaked the compilation options so I had source information for perf to work with. With regards to I/O had an earlier version of the search (that didn't work very well) where the sort was a separate program, and from that I found that mergesort could still perform well with a fan-out in the hundreds.

So when I started this version I knew I wouldn't need to do multiple mergesort passes. The large RAM sizes of modern computers help coming and going: I could sort multi-GB data files in memory before writing them out to keep the number of data files under control; and the OS had plenty of buffer memory it could devote to read-ahead when reading the files back into memory. I'm assuming read-ahead is why I didn't end up with excessive seeking when reading hundreds of files in parallel. I was still a bit surprised that I didn't end up I/O bound.

But what I really didn't expect was just how much memory each unit of work would take. What I probably should have done is have a very small fixed chunk size and just accept I would have a lot of overhead. Instead I ended up with complicated adaptive chunk size scheme.
Scorbie wrote:
November 24th, 2021, 5:38 am
Also have you thought of using sqlite instead of making files?
I did. I'm not sure it would work all that well; there is correlation from one key generated to the next but the keys are not generated in order so the btree might end up fairly fragmented. And the join I'm doing is different enough from an inner join that I would end up doing the join manually anyway. Something like hbase should work well, but that's awfully heavyweight for something I'm not planning on running on a cluster.
-- Andrew Wade

User avatar
May13
Posts: 786
Joined: March 11th, 2021, 8:33 am

Re: A new spaceship search approach

Post by May13 » February 2nd, 2022, 6:40 am

While searching for 2c/3 spaceship in B267/S34, I got message about potential spaceship, but I found no spaceship in file.

Code: Select all

0511/00
0511/01
0511/02
0511/03
0511/04
0511/05
0511/06
0511/07
0511/08
0511/09
0511/10
0511/11
0511/12
0511/13
0511/14
0511/15
0511/16
0511/17
0511/18
0511/19
0511/20
0511/21
0511/22
0511/23
0511/24
0511/25
0511/26
0511/27
0511/28
0511/done
0512/29
0512/28
0512/27
0512/26
0512/25
0512/24
0512/23
0512/22
0512/21
0512/20
0512/19
0512/18
0512/17
0512/16
0512/15
0512/14
0512/13
0512/12
0512/11
0512/10
0512/09
0512/08
0512/07
0512/06
0512/05
0512/04
0512/03
0512/02
0512/01
0512/done
0513/00
0513/01
0513/02
0513/03
0513/04
0513/05
0513/06
0513/07
0513/08
0513/09
0513/10
0513/11
0513/12
0513/13
0513/14
0513/15
0513/16
0513/17
0513/18
0513/19
0513/20
0513/21
0513/22
0513/23
0513/24
0513/25
0513/26
0513/27
0513/28
Potential Spaceship found, check latest partial!
0513/done
0514/29
0514/28
0514/27
0513.partial.txt:

Code: Select all


                                                                                                                                                                           
                                                                                                                                                                           
                                                                                                                                                                           
                                                                                                                                                                           
                                                              *                                                                                                            
                                                                                                          *       *                                                        
                                  *               *  *   *   **                                              *   *                                                         
              *   *             ***  *                 * ** * *                                         **    * * *                                                *       
       *      * **     *     *  *  **   *     *       *  * **                                  *        * *  ** *    *                                         *     *     
      * *  **  **  *           * ***         * ** * ** * *      *                            **  *    **    *   * *   *                                      *    *      * 
   *   * *     * *  *        * ** ****    *         * ** *      * *          * *           ** *  * *  * *   * **  ***                                          **     ***  
     ***      * * ** *   *  *   **  * ****    *    **  ****  *   ** *       ** ***         *   *   **    *    * * *   *                                      *  *  * *   * 
   *  *     **     *  ** * *  *     * *  * **                 * **        * *   *        * * *     * *  * *    **** *    *    *                   *        *        *      
   ** ** *  ****  ** * *           * *  *  *  * *             *   *    *  **    ****   *****  *                  *   **  * *                   *** *      * **  *  *       
     *  * * ***      * * *    *       * *    ** **  *         **    *     ** *   *****     *   ****************   *     *   * **              ** * ***      *  *           
 *  * ** ****     ** *     ** *       *          * *                ** * ***   *  *   *  **   * **  **  **  * * * **      ** *      *    *     *  *     *     * **         
* *   ***   *  ***  *        *     *          *   * *           **      *  *   *  *      **   *************  *           * *  *  *   *****  * **  ****  *  **  *  *        
   * * *   * **  *   **   * *   * *   ***  * * ** **   *    *   ** *   *  ** ***  *        *                 *      *   *   ** * **   *   *  *      * ***  ** *            
*****  * * * * *  ** *  *   *  *   * * *  **   *        *      *     *    **  * *  **           *       * *  **  * *  ***    **  * * *   *  *   * *** *   **  *   *        
*  *      *  *   * *      *     ****  *   **       **   *  **     ** ***  * *   * *  *     *     ** *  ** *   *  * **      *     ** * *  ****      **        ***           
    **      *     *  *   **     * * *** * *   *  *   * *  * *       * *    *  * ** *  * * ** ** * *    * *       *      *        * ** *  ***    *    *  **     *           
* *** *   * *     *  *  ** *      *       * ** * *  *** * *    * *       *   ****    * * ***      ***  * *  *   * *  **  **  *  *          *  *    *  * *     ** *         
 *  *         *  *  * *   *  * ** *   *       * * * ** *** * * *  *       **      *    **   *  * ** *  *** *** *  *    * *         ****    *   *** *  ***   *              
 * * * *   *  *     *   ***      *   ***   *  ** * *      * *   *         *  * * * ** * *        * *   * *  **  *                ***  *        *   *   *  * *              
 *    *    *  * *    **     *    *      * *     * **   *   *  ** *   *  ***  ** ******    *      **           *  *     *  *  ***  *    *       ** ***  **    *             
 **         *    * *     ** * * * ** * ******    * ***    *    * *     *    * **      **        *        * *   * *   *** **    *     *    * **    * **   *  * *            
   * *    * *        **  *     * ** * *         **   *      * * *    * ***    *  *      * * * *   *   ***  *  *   *   * *            * *        ** * *                     
        **  *     *     *  * **      *  **    **        * ***       ***                   * * * * ***     *     ** *     *   **** ***  *  **  *   * *  *  **               
        **  *     *     *  * **      *  **    **        * ***       ***                   * * * * ***     *     ** *     *   **** ***  *  **  *   * *  *  **               
RLE:

Code: Select all

x = 170, y = 48, rule = B267/S34
62bo$106bo7bo$34bo15bo2bo3bo3b2o46bo3bo$14bo3bo13b3o2bo17bob2obobo41b
2o4bobobo48bo$7bo6bob2o5bo5bo2bo2b2o3bo5bo7bo2bob2o34bo8bobo2b2obo4bo
41bo5bo$6bobo2b2o2b2o2bo11bob3o9bob2obob2obobo6bo28b2o2bo4b2o4bo3bobo
3bo38bo4bo6bo$3bo3bobo5bobo2bo8bob2ob4o4bo9bob2obo6bobo10bobo11b2obo2b
obo2bobo3bob2o2b3o42b2o5b3o$5b3o6bobob2obo3bo2bo3b2o2bob4o4bo4b2o2b4o
2bo3b2obo7b2ob3o9bo3bo3b2o4bo4bobobo3bo38bo2bo2bobo3bo$3bo2bo5b2o5bo2b
2obobo2bo5bobo2bob2o17bob2o8bobo3bo8bobobo5bobo2bobo4b4obo4bo4bo19bo8b
o8bo$3b2ob2obo2b4o2b2obobo11bobo2bo2bo2bobo13bo3bo4bo2b2o4b4o3b5o2bo
18bo3b2o2bobo19b3obo6bob2o2bo2bo$5bo2bobob3o6bobobo4bo7bobo4b2ob2o2bo
9b2o4bo5b2obo3b5o5bo3b16o3bo5bo3bob2o14b2obob3o6bo2bo$bo2bob2ob4o5b2ob
o5b2obo7bo10bobo16b2obob3o3bo2bo3bo2b2o3bob2o2b2o2b2o2bobobob2o6b2obo
6bo4bo5bo2bo5bo5bob2o$obo3b3o3bo2b3o2bo8bo5bo10bo3bobo11b2o6bo2bo3bo2b
o6b2o3b13o2bo11bobo2bo2bo3b5o2bob2o2b4o2bo2b2o2bo2bo$3bobobo3bob2o2bo
3b2o3bobo3bobo3b3o2bobob2ob2o3bo4bo3b2obo3bo2b2ob3o2bo8bo17bo6bo3bo3b
2obob2o3bo3bo2bo6bob3o2b2obo$5o2bobobobobo2b2obo2bo3bo2bo3bobobo2b2o3b
o8bo6bo5bo4b2o2bobo2b2o11bo7bobo2b2o2bobo2b3o4b2o2bobobo3bo2bo3bob3obo
3b2o2bo3bo$o2bo6bo2bo3bobo6bo5b4o2bo3b2o7b2o3bo2b2o5b2ob3o2bobo3bobo2b
o5bo5b2obo2b2obo3bo2bob2o6bo5b2obobo2b4o6b2o8b3o$4b2o6bo5bo2bo3b2o5bob
ob3obobo3bo2bo3bobo2bobo7bobo4bo2bob2obo2bobob2ob2obobo4bobo7bo6bo8bob
2obo2b3o4bo4bo2b2o5bo$ob3obo3bobo5bo2bo2b2obo6bo7bob2obobo2b3obobo4bob
o7bo3b4o4bobob3o6b3o2bobo2bo3bobo2b2o2b2o2bo2bo10bo2bo4bo2bobo5b2obo$b
o2bo9bo2bo2bobo3bo2bob2obo3bo7bobobob2ob3obobobo2bo7b2o6bo4b2o3bo2bob
2obo2b3ob3obo2bo4bobo9b4o4bo3b3obo2b3o3bo$bobobobo3bo2bo5bo3b3o6bo3b3o
3bo2b2obobo6bobo3bo9bo2bobobob2obobo8bobo3bobo2b2o2bo16b3o2bo8bo3bo3bo
2bobo$bo4bo4bo2bobo4b2o5bo4bo6bobo5bob2o3bo3bo2b2obo3bo2b3o2b2ob6o4bo
6b2o11bo2bo5bo2bo2b3o2bo4bo7b2ob3o2b2o4bo$b2o9bo4bobo5b2obobobob2obob
6o4bob3o4bo4bobo5bo4bob2o6b2o8bo8bobo3bobo3b3ob2o4bo5bo4bob2o4bob2o3bo
2bobo$3bobo4bobo8b2o2bo5bob2obobo9b2o3bo6bobobo4bob3o4bo2bo6bobobobo3b
o3b3o2bo2bo3bo3bobo12bobo8b2obobo$8b2o2bo5bo5bo2bob2o6bo2b2o4b2o8bob3o
7b3o19bobobobob3o5bo5b2obo5bo3b4ob3o2bo2b2o2bo3bobo2bo2b2o$8b2o2bo5bo
5bo2bob2o6bo2b2o4b2o8bob3o7b3o19bobobobob3o5bo5b2obo5bo3b4ob3o2bo2b2o
2bo3bobo2bo2b2o$3bobo4bobo8b2o2bo5bob2obobo9b2o3bo6bobobo4bob3o4bo2bo
6bobobobo3bo3b3o2bo2bo3bo3bobo12bobo8b2obobo$b2o9bo4bobo5b2obobobob2ob
ob6o4bob3o4bo4bobo5bo4bob2o6b2o8bo8bobo3bobo3b3ob2o4bo5bo4bob2o4bob2o
3bo2bobo$bo4bo4bo2bobo4b2o5bo4bo6bobo5bob2o3bo3bo2b2obo3bo2b3o2b2ob6o
4bo6b2o11bo2bo5bo2bo2b3o2bo4bo7b2ob3o2b2o4bo$bobobobo3bo2bo5bo3b3o6bo
3b3o3bo2b2obobo6bobo3bo9bo2bobobob2obobo8bobo3bobo2b2o2bo16b3o2bo8bo3b
o3bo2bobo$bo2bo9bo2bo2bobo3bo2bob2obo3bo7bobobob2ob3obobobo2bo7b2o6bo
4b2o3bo2bob2obo2b3ob3obo2bo4bobo9b4o4bo3b3obo2b3o3bo$ob3obo3bobo5bo2bo
2b2obo6bo7bob2obobo2b3obobo4bobo7bo3b4o4bobob3o6b3o2bobo2bo3bobo2b2o2b
2o2bo2bo10bo2bo4bo2bobo5b2obo$4b2o6bo5bo2bo3b2o5bobob3obobo3bo2bo3bobo
2bobo7bobo4bo2bob2obo2bobob2ob2obobo4bobo7bo6bo8bob2obo2b3o4bo4bo2b2o
5bo$o2bo6bo2bo3bobo6bo5b4o2bo3b2o7b2o3bo2b2o5b2ob3o2bobo3bobo2bo5bo5b
2obo2b2obo3bo2bob2o6bo5b2obobo2b4o6b2o8b3o$5o2bobobobobo2b2obo2bo3bo2b
o3bobobo2b2o3bo8bo6bo5bo4b2o2bobo2b2o11bo7bobo2b2o2bobo2b3o4b2o2bobobo
3bo2bo3bob3obo3b2o2bo3bo$3bobobo3bob2o2bo3b2o3bobo3bobo3b3o2bobob2ob2o
3bo4bo3b2obo3bo2b2ob3o2bo8bo17bo6bo3bo3b2obob2o3bo3bo2bo6bob3o2b2obo$o
bo3b3o3bo2b3o2bo8bo5bo10bo3bobo11b2o6bo2bo3bo2bo6b2o3b13o2bo11bobo2bo
2bo3b5o2bob2o2b4o2bo2b2o2bo2bo$bo2bob2ob4o5b2obo5b2obo7bo10bobo16b2obo
b3o3bo2bo3bo2b2o3bob2o2b2o2b2o2bobobob2o6b2obo6bo4bo5bo2bo5bo5bob2o$5b
o2bobob3o6bobobo4bo7bobo4b2ob2o2bo9b2o4bo5b2obo3b5o5bo3b16o3bo5bo3bob
2o14b2obob3o6bo2bo$3b2ob2obo2b4o2b2obobo11bobo2bo2bo2bobo13bo3bo4bo2b
2o4b4o3b5o2bo18bo3b2o2bobo19b3obo6bob2o2bo2bo$3bo2bo5b2o5bo2b2obobo2bo
5bobo2bob2o17bob2o8bobo3bo8bobobo5bobo2bobo4b4obo4bo4bo19bo8bo8bo$5b3o
6bobob2obo3bo2bo3b2o2bob4o4bo4b2o2b4o2bo3b2obo7b2ob3o9bo3bo3b2o4bo4bob
obo3bo38bo2bo2bobo3bo$3bo3bobo5bobo2bo8bob2ob4o4bo9bob2obo6bobo10bobo
11b2obo2bobo2bobo3bob2o2b3o42b2o5b3o$6bobo2b2o2b2o2bo11bob3o9bob2obob
2obobo6bo28b2o2bo4b2o4bo3bobo3bo38bo4bo6bo$7bo6bob2o5bo5bo2bo2b2o3bo5b
o7bo2bob2o34bo8bobo2b2obo4bo41bo5bo$14bo3bo13b3o2bo17bob2obobo41b2o4bo
bobo48bo$34bo15bo2bo3bo3b2o46bo3bo$106bo7bo$62bo!
After that, LSSS no longer wrote "Potential Spaceship found, check latest partial!" (currently I have 0529.partial.txt), program works as usual.
I have never encountered a false message while doing other searches (most likely I just never tried 2c/3 searches).
The latest version of hex-gliders.db have 668 gliders from OT hexagonal rules. Let's find more!
My CA (13 rules)
My scripts: new-glider.py v0.2 (new version), nbsearch2a.py, collector.py v0.3

Post Reply