Home » forums » LtU Forum

BF Bignum: A Program Synthesis Game

BF Bignum is a program synthesis game: the goal is to synthesize a BF program smaller than a given size that outputs the largest integer possible before halting within a given time limit. A synthesizer's score is the value of the target integer divided the total number of BF operations executed in the search for the target program.

Bignum is much harder than it sounds, and requires synthesizers to learn modular and hierarchical program representations.

  • Your BF program must be smaller than a given size, and halt within the given time limit. Time is defined as the number of BF operations executed during the production of the target integer. Synthesizers compete in a size/time class akin to weight classes in martial arts.
  • Your BF program must use `.` to produce its output. Your BF program may have any number of outputs; the largest output is the one incorporated in to your synthesizer's score. Note that since there is no input, the instruction `,` is simply ignored.
  • Your synthesizer must keep track of the total work done in the search. Work is defined as the number of BF operations executed during the search for the target program, e.g. while computing a candidate program's fitness. Note that two operations done in parallel is still two operations.

    It's not clear that this is the best measure of work, and there may be borderline cases such as static analysis that may or may not be considered execution of a BF program.

  • The BF tape contains big integers, not bytes. Your BF program is scored on the largest single integer it outputs; the sequence of integers is not interpreted as a string like in some BF examples.
  • You are writing a program that writes a program. You are not writing the bignum program yourself, that's too easy. Of course there are ways to cheat, like including some high fitness program within the source code of your synthesizer. Don't do that.

A synthesizer's score is target / work: the number output by the target program divided by the number of BF operations performed during the search.

By xkapastel at 2018-08-13 03:50 | LtU Forum | previous forum topic | next forum topic | other blogs | 3020 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Rule 4 is too vague

This seems interesting, but rule 4 is too vague.

The solution space contains a spectrum with mutation and selection of primitive operations on one side, and just outputting a pre-written solution on the other. (In the middle you might find mutation and selection of pre-written pointer-manipulation operations.) The optimal solution is to get as close as possible to the latter end of the spectrum, because it tremendously reduces the search space. For BigNum and for harder problems.

Since this is presented as a contest, and rule 4 is open to interpretation, the object of your game is now: "How close can I get to just outputting a pre-written program without tripping over rule 4?" And that seems a bit awkward.

So my first thoughts are that you should either [a] make rule 4 a lot more explicit, [b] toss rule 4 and use a harder problem, or [c] present this as a fun exercise instead of a benchmark / contest with leaderboards.

By Michiel Helvensteijn at Mon, 2018-08-13 08:58 | login or register to post comments

I guess I have to choose [c]

I'm not sure how not cheating could be made more explicit, and I would hope that the motivation here is not to get the highest score but to explore program synthesis techniques. Who cares about getting your name at the top? It's about developing artificial intelligence. I suppose I'll remove talk about "leaderboards" and just present this as a fun challenge for developers.

By xkapastel at Mon, 2018-08-13 13:12 | login or register to post comments