Phrasing a winning criterion to avoid excluding solutions

Question

Every so often old challenges are found which no longer meet our requirements, resulting in them being closed. Since there is renewed interest in this question it is in danger of suffering the same fate.

I find the question interesting, and a number of people are actively working on a collaborative solution. However, it does not have a winning criterion. More strictly, it has a winning criterion of "first person to create a demonstrably working example".

I see this as a question that could continue to receive solutions after the first one, provided there were a way for them to compete with the first. Currently, once a working solution is received the competition is over.

The challenge author seems open to the possibility of introducing a winning criterion, but this needs to be done carefully in order to avoid invalidating the solution that is currently being worked on. For example, introducing a winning criterion that rendered the current solution as not making sufficient effort would restrict the competition rather than opening it up.

How can a winning criterion be stated that allows a working solution to the underlying problem to be valid, while still leaving open the possibility of finding further solutions that are "better" according to the criterion? For challenges that are sufficiently difficult/time consuming, is it enough to simply state in the challenge "Due to the difficulty, any working solution is a valid answer, even if it is likely to be non-competitive after further research"?

Or does our current requirement that solutions be competitive already allow for this to some extent?

Answer 1

As a member of the team working on the current solution, I can say that of the proposed winning criteria I've seen, bounding box is generally the best. I'll list each criteria I've seen and their relative merits (or lack thereof).

• Fewest live cells - our solution will likely have live cells for RAM and/or ROM, so this criterion would probably be unnecessarily restrictive and/or annoying. It's an okay criterion though.
• Fastest execution - this problem is already hard, okay? :P Seriously though, it's pretty hard to speed up a cellular-automaton-based computer, since you usually have to have precise timings between all components.
• Long-term behavior (intended to penalize stuff like escaped gliders) - this is pretty much irrelevant since we're using OTCA metapixels, which are structures in Game of Life that allow simulation of any Life-like rules, and they don't have any escaping spaceships.
• Bounding box - as I've already said, I think this is the way to go. You can do some really interesting stuff with moving components around and connecting them in different ways, and in fact, this kind of golfing has already happened. PhiNotPi created a 55x33 serial adder, then golfed it to 33x22.

Hence, my suggestion is to change the winning criterion to the smallest bounding box, or possibly the smallest not-necessarily-rectangular region that wholly contains the GoL program.