Spaceship search program: lifelocallookahead

[mscibing]

Hi folks,

I've been working on a life search program for half a year, in the hope of finding a (2,1)c/6 knightship. I've uploaded it to:

https://gitorious.org/lifelocallookahead

It's very much inspired by David Eppstein's paper at http://arxiv.org/abs/cs.AI/0004003 . The actual approach is quite different.

The current approach combines a number of strategies:

The base search is just a depth-first exhaustive search inside a pre-defined area.

This is supplemented by a graph in the region ahead of the base search. This grahp consists of overlapping fragments smaller than the arena width. This was inspired by the de Bruijn graph discussion in the paper linked above. Not sure if I understood the discussion correctly, but in any event building a graph and using it to reject branches in the base search is providing a benefit over the base search alone. I have some enhancements in mind to make the code more efficient when using larger (15-20 cell) fragments.

This second layer is in turn suplemented by a "local look ahead". Basically an attempt is made for each candidate fragment/node in the graph to extend it a few more cells forward. If the attempt is successful the extension is discarted and the fragment/node retained, otherwise the node is ruled out and discarded.

The local look ahead portion has a further wrinkle: the search tree for the local lookahead is mutated as the search progresses. The idea is to bring cells that are good at rejecting search branches closer to the root of the seach tree. I'm sure I've read about this idea (mutating the search tree) elsewhere. I tried many different approaches, surprisingly a fairly simple-minded approach that is amost maximally mutating seems to work best.

The code does work, but so far I've only found quite low-period spaceships with it. If I find anything interesting with it I'll let people know.


Some of the ideas that haven't turned out:

* Divide and conquer: find left spacehips halves, find right spaceship halves, do an inner join on an overlap region in the middle to find spaceships. This approach requires finding spaceship halves in large numbers, which I haven't been able to do.

* Curved search fronts: convex or concave. There was no obvious speed-up here. But I haven't come up with a good performance metric yet so I may come back to this idea. Right now my base search front is a diagonal, and this seems to be working well.

- Andrew

[codeholic]

Hi, Andrew, great news, that there is another search program for spaceships out there! Hopefully one will find new spaceships with its assistance!

Would you please elaborate a little bit more on its usage? In particular, the config file looks kinda cryptic to me.

[mscibing]

Hi Ivan,

The code is a bit messy right now as I've been trying out different ideas. Please ignore the config file, it stems from the earlier divide and conquer approach.

Usage is (on linux):
make
./generatearena2.py | ./locallookahead > save1.txt

Interrupt with ctrl-C (^C)

resume from the saved file:
./locallookahead < save1.txt > save2.txt

The save file options are:
glider - The spaceship velocity sought.
n - cell coordinates of a node in the base search (first n is the coordinate of the leaves, last n is the coordinate of the root.).
l - lookahead node cell coordinate. These are the nodes for the lookahead search associated with the next n node in the file. Due do the implementation the "l" region contains the cell coordinates of all the "c" graph search cells as well.
c - graph fragment cell coordinate (The "c" stands for cache, this is just an implementation detail of how the graph code is implemented.) The graph fragment is associated with the following "n" base search node.

The graph fragments are linked by additional coordinates on the "n" nodes. As an example:
...
l 11, 9
l 11, 10
l 12, 9
l 13, 9
l 12, 10
l 11, 11
c 11, 10
c 12, 10
c 11, 11
n 11, 12, 12, 11, 13, 11
l 12, 9
l 13, 9
l 12, 10
c 12, 9
c 13, 9
c 12, 10
n 12, 11

Here the base search node at (11, 12) has an associated graph search fragment at (11, 10), (12, 10), (11, 11). Graph nodes for this fragment are joined to graph nodes for the fragment (12, 9), (13, 9), (12, 10) (associated with base search node (12, 11)), and the graph nodes associated with base search node (13, 11). This joining is implicit, there is no explicit edge list ever built.

Hope this makes sense.

After this part of the file is the stats line:
#stats cputime lookahead positive lookahead negative
stats 5.033035 8356 18200

This is just the stats for the last run.

This is followed by any solution rle's found (Solution Found! will also be printed to stderr).

The "startrle" line contains cumulative stats over all runs:
startrle 2706657.108972 11414404354 12625610174

This is then followed by the base search state encoded as a RLE, e.g.:
x = 63, y = 60, rule = B3/S23
47$58b2o$59bo$56bo2bo$56b3o$57bo$53b3o2$52bo$52bo$51b2o$51bo!

The rule is parsed and used, but as yet I've only tested the search with B3/S23.

generatearena2.py creates are random startrle each time, thus a distributed/multicore search is just a matter of spinning up a number of locallookahead instances each initialized by a different generatarena2.py invocation.

I'm about to push an update with some significant performance enhancements.

Then I'll be cleaning up some of cruft in the code.

regards,
Andrew

[mscibing]

With Gitorious being bought out, the program is now at https://gitlab.com/andrew-j-wade/lifelocallookahead.

The program did find the c/4 orthogonal spaceship below, so I know it does work to some extent. But I haven't found anything particularly interesting yet.

Code: Select all

x = 59, y = 54, rule = B3/S23
16$19b2o2b2o$16b2o3bob3o$16b2ob2o2b2o$14b3o$14bo5bo$19b2o$19b
o2bobo2b2o$20bo3bo2bo2bo$24bobo10bo$24bo5b2o4bobo$22b2o2b3o2b
obo3b2o$21bob2o2b2o2b2o2bo2bo$22bo10bobobo$33bo2bo2bob3o$35bo
bobo2bo$36b2obo2bo$39b2obobo2b2o$44b4obo$43bo5bo$44b3o$45b2o2b
2o$42b3o3b3o$40bo2bob2obo$39b5obo2b3o$39bo2bo3bob3o$39bob2o2b
obo2bo$43bo2bob2o$39bo3bo7bo$40bo2bobo2bo3bo$43bob2o4bo$45b2o
2b2o$42b4o$47b2o!

[Saka]

Umm... How do I use this? Do I need to compile first?

[mscibing]

Umm... How do I use this? Do I need to compile first?

Afraid so. Using cygwin if you're on windows. (Or with the timekeeping stuff commented out--it's not critical).
I'm probably not going to get around to a windows compile soon.
The other dependency is on python3 for the generatearena.py program.

Command line useage after compiling is:
./generatearena.py | ./locallookahead > savefile.txt
I'll display "Solution Found!" on stderr if it finds a spaceship and will save the rle for the ship in the savefile.

[Saka]

When I do ./generatearena.py it says:

Code: Select all

-bash: ./generatearena.py: /usr/bin/python3: bad interpreter: Permission denied

When I do ./lifelocallookahead (I am running from the directory)

Code: Select all

-bash: ./lifelocallookahead: No such file or directory