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