slmake

[AlbertArmStain]

The old slmake is a greedy algorithm, and the new version that I'm currently writing (pslmake) is a parallelised beam search with heuristic similar to that in the A* search algorithm, where the cost estimate is based on a linear model fitted on diagnostics produced by the old slmake.

Which is still a greedy algorithm, but not as greedy or slow as slmake. It’s still greedy though.

I don't see how it's related to travelling salesman? The problem is to find a short path from a single block to the desired pattern in the (infinite) directed graph where each node is a constellation and each directed edge corresponds to a glider collision; this is a pathfinding problem. On the other hand, travelling salesman is about finding a minimum-length path/cycle that visits all nodes of a finite graph with weighted edges, which is a very different sort of problem (NP-complete as a function of the size of the graph, whereas pathfinding is polynomial-time in the size of the graph).

I was referring to a construction arm and finding a minimal path for the construction arm. Is there a route optimization for a 90 degree salvo? What about for a 0 degree single channel construction arm?

[AlbertArmStain]

Does pslmake have a feature where you can specify to construct left to right or vise versa?

[calcyman]

Does pslmake have a feature where you can specify to construct left to right or vise versa?

No, but the natural order is 'back to front' (and because pslmake works backwards, it handles the things at the front to begin with before gradually moving to the back). The left/right ordering is handled by the 'defragmentation' pass which is a postprocessing step, not part of the core algorithm.

[AlbertArmStain]

Does pslmake have a feature where you can specify to construct left to right or vise versa?

No, but the natural order is 'back to front' (and because pslmake works backwards, it handles the things at the front to begin with before gradually moving to the back). The left/right ordering is handled by the 'defragmentation' pass which is a postprocessing step, not part of the core algorithm.

So that’s why it’s so algorithmically greedy. It could possibly build a section back to front, then move to the next section, unless this is already implemented.

[Hippo.69]

So that’s why it’s so algorithmically greedy. It could possibly build a section back to front, then move to the next section, unless this is already implemented.

The order of gliders in the salvo can be permuted in many cases (whole blocks). Minimizing the size of salvo would have exponential number of solutions even when considering just these permutations of one salvo. This is why prefering order of targets mostly for example with slowly decresing x+y reduces number of equivalent salvos.

Final defragmentation chooses among the same upto permutation recipe one which is with high probability among cheapest to invoke by an arm.

Next postprocessing is considering the configurtions of nongliders among collisions be the recipe and replacing each glider in salvo by several options of lines and (phases mod small integer) ... to allow the arm choose cheaper variant of recipe.

What I am planning to do is considering final functional pattern as the goal and creating other clusters not interferring with the pattern not to be a problem. So usually some gliders/levels (destroying these clusters) in the recipe could be skipped and still obtain the same functional pattern.

[AlbertArmStain]

Does pslmake have a feature where it will pinpoint the location of the non-spartan objects?

[EvinZL]

Is pslmake released anywhere?

[EvinZL]

Doublepost, but here's what seems to be a bug in slmake.

Given this infile.mc:

Code: Select all

x = 114, y = 114, rule = LifeHistory
.A$A.A$.A.A$2.A.A$3.A.A$4.A.A$5.A.A$6.A.A$7.A.A$8.A.A$9.A.A$10.A.A$
11.A.A$12.A.A$13.A.A$14.A.A$15.A.A$16.A.A$17.A.A$18.A.A$19.A.A$20.A.A
$21.A.A$22.A.A$23.A.A$24.A.A$25.A.A$26.A.A$27.A.A$28.A.A$29.A.A$30.A.
A$31.A$32.3A.2A3.A$34.A.A3.A.A$34.A2.A3.A$33.2A3.A11.2A$35.3A12.A.A$
35.A15.2A3$52.2A$44.2A5.A.A$44.A.A5.A$45.A$51.2A$51.A.A$46.2A3.A$46.
2A61$112.A$111.A.A$107.2A.A2.A$107.2A.A.A$111.A!

slmake prints:

Code: Select all

Instruction set AVX2 detected
Loading elbow recipes...
Snarkmaker string = 10762 bytes.
...elbow recipes loaded.
Signature: [ 109 ]
Wrong orientation; flipping pattern.
Calling sparsebuild on initial pattern comprising 109 cells
 -- data/bespoke/blocker-orient1.rle has period 8.
 -- data/bespoke/blocker-orient2.rle has period 8.
 -- data/bespoke/blocker-orient3.rle has period 8.
 -- data/bespoke/eater2-orient1b.mc has period 1.
 -- data/bespoke/eater2-orient1.mc has period 1.
 -- data/bespoke/eater2-orient2.mc has period 1.
 -- data/bespoke/eater2-orient3.mc has period 1.
 -- data/bespoke/figure8-orient1.rle has period 8.
 -- data/bespoke/figure8-orient2.rle has period 8.
 -- data/bespoke/figure8-orient3.rle has period 8.
 -- data/bespoke/mw2g-orient1.mc has period 1.
 -- data/bespoke/mw2g-orient2.mc has period 1.
 -- data/bespoke/mw2g-orient3b.mc has period 1.
 -- data/bespoke/mw2g-orient3c.mc has period 1.
 -- data/bespoke/mw2g-orient3.mc has period 1.
 -- data/bespoke/mw2g-orient4.mc has period 1.
 -- data/bespoke/snarkheart-eater-orient3.rle has period 1.
 -- data/bespoke/snarkheart-orient1.rle has period 1.
 -- data/bespoke/snarkheart-orient2.rle has period 1.
 -- data/bespoke/snarkheart-orient4.rle has period 1.
 -- data/bespoke/xs17-easy.rle has period 1.
 -- data/bespoke/xs17-eater2.rle has period 1.
 -- data/bespoke/xs17-next.rle has period 1.
 -- data/bespoke/xs17-third.rle has period 1.
Reading file data/edgy/xs4_33/xs4_33__xs5_253...
...data/edgy/xs4_33/xs4_33__xs5_253 successfully read.
Reading file data/edgy/xs4_33/xs5_253...
...data/edgy/xs4_33/xs5_253 successfully read.
Reading file data/edgy/xs6_696/xs5_253...
...data/edgy/xs6_696/xs5_253 successfully read.
Reading file data/edgy/xs4_252/xs5_253...
...data/edgy/xs4_252/xs5_253 successfully read.
Reading file data/edgy/xs4_33/xs4_252...
...data/edgy/xs4_33/xs4_252 successfully read.
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Reading file data/longmove/xs4_33...
...data/longmove/xs4_33 successfully read.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 3
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 9
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 27
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 81
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Attempting to construct xs4_33 with 8 gliders (2856 recipes)
Attempting to construct xs4_33 with 9 gliders (3648 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 243
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Attempting to construct xs4_33 with 8 gliders (2856 recipes)
Attempting to construct xs4_33 with 9 gliders (3648 recipes)
Attempting to construct xs4_33 with 10 gliders (4645 recipes)
Attempting to construct xs4_33 with 11 gliders (4056 recipes)
Attempting to construct xs4_33 with 12 gliders (5092 recipes)
Attempting to construct xs4_33 with 13 gliders (6445 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 729
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Attempting to construct xs4_33 with 8 gliders (2856 recipes)
Attempting to construct xs4_33 with 9 gliders (3648 recipes)
Attempting to construct xs4_33 with 10 gliders (4645 recipes)
Attempting to construct xs4_33 with 11 gliders (4056 recipes)
Attempting to construct xs4_33 with 12 gliders (5092 recipes)
Attempting to construct xs4_33 with 13 gliders (6445 recipes)
Attempting to construct xs4_33 with 14 gliders (6549 recipes)
Attempting to construct xs4_33 with 15 gliders (7692 recipes)
Attempting to construct xs4_33 with 16 gliders (8655 recipes)
Attempting to construct xs4_33 with 17 gliders (8928 recipes)
Attempting to construct xs4_33 with 18 gliders (9604 recipes)
Attempting to construct xs4_33 with 19 gliders (10513 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 2187
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 8 gliders (2856 recipes)
Attempting to construct xs4_33 with 9 gliders (3648 recipes)
Attempting to construct xs4_33 with 10 gliders (4645 recipes)
Attempting to construct xs4_33 with 11 gliders (4056 recipes)
Attempting to construct xs4_33 with 12 gliders (5092 recipes)
Attempting to construct xs4_33 with 13 gliders (6445 recipes)
Attempting to construct xs4_33 with 14 gliders (6549 recipes)

• At the start, it says "4 objects of < 32 cells" when there are 5.
• It can't construct a block, when it should be very easy to do so.
• Why is it constructing a block first?

I tested it out with only the tub+big sl and it seems to work fine.

[calcyman]

Doublepost, but here's what seems to be a bug in slmake.

Given this infile.mc:

Code: Select all

x = 114, y = 114, rule = LifeHistory
.A$A.A$.A.A$2.A.A$3.A.A$4.A.A$5.A.A$6.A.A$7.A.A$8.A.A$9.A.A$10.A.A$
11.A.A$12.A.A$13.A.A$14.A.A$15.A.A$16.A.A$17.A.A$18.A.A$19.A.A$20.A.A
$21.A.A$22.A.A$23.A.A$24.A.A$25.A.A$26.A.A$27.A.A$28.A.A$29.A.A$30.A.
A$31.A$32.3A.2A3.A$34.A.A3.A.A$34.A2.A3.A$33.2A3.A11.2A$35.3A12.A.A$
35.A15.2A3$52.2A$44.2A5.A.A$44.A.A5.A$45.A$51.2A$51.A.A$46.2A3.A$46.
2A61$112.A$111.A.A$107.2A.A2.A$107.2A.A.A$111.A!

Can you try that but with the input glider shifted SE by, let's say, (5, 5)? It separates gliders from everything else by computing (x & x[8]), so if gliders collide within the first 8 generations, it won't be parsed correctly.

Is pslmake released anywhere?

Not yet: I was abroad this last week and didn't have access to my laptop until today. I need to make some user-friendliness adjustments (such as making everything command-line arguments instead of hardcoded in the source, and including a Python script for downloading pslmake databases).

Does pslmake have a feature where it will pinpoint the location of the non-spartan objects?

I don't understand the question; please could you elaborate?

[dvgrn]

Does pslmake have a feature where it will pinpoint the location of the non-spartan objects?

I don't understand the question; please could you elaborate?

I read that more or less as "some easy way to see where pslmake is getting stuck, if it gets stuck".

E.g., have a progress.rle file updated after every reduction, showing the remaining constellation. Could run a script in Golly to monitor that file and update a display when it changes... that would probably not _always_ highlight a problem area clearly, though -- maybe there's a better way to point out the region where pslmake might be working that it's having trouble with.

[Tawal]

Hi,

I'm on Linux and tried to compile slmake.
I get this error :

Code: Select all

$ ./slsparse.cpp 
Downloading lifelib...
Sous-module 'lifelib' (https://gitlab.com/apgoucher/lifelib.git) enregistré pour le chemin 'lifelib'
Clonage dans '/home/tawal/Term/Test/slmake/lifelib'...
Chemin de sous-module 'lifelib' : 'af0c7910e6a6c8fe276222ef5bcecec3e1495f2f' extrait
Sous-module 'cpads' (https://gitlab.com/hatsya/open-source/cpads.git) enregistré pour le chemin 'lifelib/cpads'
Clonage dans '/home/tawal/Term/Test/slmake/lifelib/cpads'...
Chemin de sous-module 'lifelib/cpads' : '07fea42b10e3a54f4b40f8e7fcc388d5726a446a' extrait
Compiling...
...compiled.
ven. 13 oct. 2023 10:19:11 CEST
Instruction set SSE3 detected
./slsparse.cpp : ligne 10 : 242731 Instruction non permise "$exename" "$@"
ven. 13 oct. 2023 10:19:11 CEST
$
$ ./slsparse
Instruction set SSE3 detected
Instruction non permise
$

Sorry for the French's output.
Instruction non permise = Instruction not allowed

Where's the matter ?
CPU capabilities ? (AMD Athlon X2 QL-62 (2) @ 2.000GHz)
Missing packages ?
Other ?

Thanks to help me.

Edit:
The error seems to be in the execution of slparse, not in the compilation.
My Linux : Debian GNU/Linux 12 (bookworm) x86_64

[confocaloid]

Code: Select all

Instruction set SSE3 detected
./slsparse.cpp : ligne 10 : 242731 Instruction non permise "$exename" "$@"

Sounds like the program requires some CPU capabilities. On my system it outputs the following:

Code: Select all

Instruction set SSE4.2 detected
Loading elbow recipes...
Snarkmaker string = 10762 bytes.
...elbow recipes loaded.
Signature: [ 252 ] 
Wrong orientation; flipping pattern.
Calling sparsebuild on initial pattern comprising 252 cells
(output trimmed)

[Tawal]

Thanks for your response.

But the error you quoted is not very important i think.
It comes from the bash hack at the beginning of the slsparse.ccp file.
I've tried to remove this trick and launch the compilation command directly.
The compilation is right, no errors. It output well a slsparse executable file.
But the execution of the slsparse get this error :

Code: Select all

$ ./slsparse
Instruction set SSE3 detected
Instruction non permise
$

How to verify which CPU capabilities is necessary ? (to be sure ...)

Thanks.

Edit:

Linux folks will probably be clever enough to adjust the instructions to leave out the Cygwin-related details that they don't need.

I've not the level of cleverness