5
\$\begingroup\$

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?

\$\endgroup\$
  • 3
    \$\begingroup\$ "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." In the specific context given, any answer surely constitutes sufficient effort. \$\endgroup\$ – Peter Taylor May 30 '16 at 11:27
  • \$\begingroup\$ @PeterTaylor I agree, which is why I'm trying to make sure the wording of a winning criterion doesn't change that. For example, if the winning criterion was "fewest live cells in the starting configuration", I'd want to welcome any solution that didn't have obvious opportunities for improvement (like large groups of redundant live cells). Similarly to a hard challenge scored by golf, where only obvious golfing opportunities like long variable names would make the solution unwelcome. \$\endgroup\$ – trichoplax May 30 '16 at 11:56
5
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ I'm in favor of fastest execution and bounding box. The bonus is that reducing the bounding box can often decrease the execution time. \$\endgroup\$ – Nathan Merrill May 31 '16 at 12:54
  • \$\begingroup\$ BTW, when you say "smallest bounding box", are you using area or largest dimension as the size measure? \$\endgroup\$ – Joe Z. Jun 9 '16 at 1:56
  • 1
    \$\begingroup\$ @JoeZ.: Area is probably the better way to go. \$\endgroup\$ – El'endia Starman Jun 9 '16 at 2:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .