BF Joust

From Esolang
Jump to: navigation, search

BF Joust (also known as Brainfuck Joust) is a Brainfuck-based game, originally invented by Kerim Aydin, consisting of two programs in a Brainfuck-like language which attempt to modify a shared memory array in a particular way.

The Current Rules[edit]

Syntax[edit]

In BF Joust, two programs (called 'warriors', borrowing from the Core War parlance) square off against one another by synchronously modifying a shared memory array. Both programs are written in a variant of brainfuck, reduced to the following instruction set:

  • < move the tape pointer away from the opponent
  • > move the tape pointer toward the opponent
  • - decrease the tape element at the tape pointer
  • + increase the tape element at the tape pointer
  • [ jump to just after the matching ] if the current tape element is 0
  • ] jump to just after the matching [ if the current tape element is not 0
  • . do nothing

Like in brainfuck, unrecognised characters are just ignored, and can be used as comments. (Note that ()%* and digits are used for abbreviation syntax, though; and that the original version of BF Joust reserved , as well, although it's unlikely to be given a use after this long.)

The Battlefield[edit]

The battlefield is an array (or 'tape') which both warriors are able to modify; the tape is 10 to 30 elements long (either randomly, or running on every possible length). Each element (or 'cell') in this array can contain any of 256 values, which it is most helpful to consider as being in the range [-127,128]. Moreover, the cells wrap, so that 128 plus 1 is -127 and -127 minus 1 is 128. At the beginning of a battle, every cell is set to zero except for the ones at each end, which are set to 128. These cells, called 'flags' are where the warriors' data pointers are pointing at the beginning of each round. Thus, each warrior can pretend that, at the beginning of a round, its data pointer is pointed to cell zero (the first cell) where its own flag is located and its enemy's flag stands at the far right end of the tape.

The Battle[edit]

In each round of a match, both warriors simultaneously execute one of the above instructions at each time step (or 'cycle'). (Normally, applying two command effects simultaneously is not problematic, e.g. + and + on the same cycle increase a cell by two, and + and - on the same cycle cancel each other out and don't do anything. The potential ambiguity is with [ or ] on the same cycle as + or -; in such cases, the flow control command sees the value before, rather than after, the increment or decrement.) This repeats until one or both of the warriors have lost the battle, or 100,000 cycles have been executed.

A warrior loses when either of the following happens:

  • Its own flag is set to zero for two consecutive cycles, or
  • Its data pointer has left the tape (that is, it executes > at its enemy's flag or < at its own flag)

Note that reaching the end of the program (as opposed to the tape) is not a loss; rather, a program that does that takes no action on any future cycle, and thus loses, wins, or draws according to whether the opponent manages to zero its flag, commit suicide, or do neither. (This means that even an empty program can theoretically win, although it tends to do quite badly in practice.)

A warrior wins if the other warrior loses. That is, the goal is to either:

  • Zero the enemy's flag before it zeroes yours, or
  • Trick the enemy into moving off the end of the tape ("committing suicide")

If both warriors lose simultaneously, or the timeout of 100,000 cycles is reached, the game is a draw.

Matches[edit]

Rather than running a single run between two warriors (which would have a random tape length from 10 to 30), tournaments generally run 42 matches between the two warriors, in order to make the results deterministic. Two things are varied: the tape has one of 21 different lengths (the integers from 10 to 30 inclusive); and one of the warriors may have its polarity exchanged, i.e., exchanging the meaning of + and -. (It doesn't matter which warrior's polarity is exchanged, since the results are provably identical in either case. Polarity exchange removes the degenerate strategy of submitting programs which are nearly identical to existing programs except for the direction (+ or -) of their clears and/or decoys. The polarity where both programs run on their original polarity is sometimes known as "sieve", and the exchanged polarity as "kettle".)

A program is scored based on the number of configurations in which it won, minus the number of configurations in which it lost; thus +42 is a perfect score for an individual match, and -42 the worst possible. (Odd scores are possible if an odd number of matches are draws.)

Abbreviations[edit]

BF Joust supports a couple of abbreviations which work like a preprocessor, in order to enable long programs to be written more quickly, to be smaller, and to be more readable:

Run-length encoding
Any repeating piece of code can be abbreviated as long as the brackets in the repeated portion are matched; the syntax is to enclose the repeating piece in parentheses, then write an asterisk and a repeat count. For instance, (+-)*5 is equivalent to +-+-+-+-+-.
Nesting
For repetitions that nest inside each other (i.e. containing unmatched brackets), a separate syntax is provided which is best demonstrated by example: (+[{.}]-)%5 means +[+[+[+[+[.]-]-]-]-]-. (As a general definition, (a{b}c)%n would be equivalent to (a)*n b (c)*n if ()* allowed unmatched brackets.) Although it is legal to use this syntax without loops involved, there is not much point, e.g. (+{.}-)%5 is equivalent to (+)*5.(-)*5, which is probably clearer. Note that the various sorts of bracket still have to be matched as a whole, although unmatched [ are allowed between the ( and { as long as they are matched by a bracket between the } and ).

In some interpreters (including egojoust), giving a repeat count of -1 indicates that the enclosed section of code should be repeated until the match is over.

These abbreviations are merely syntactic sugar, and their semantics are identical to if they were expanded before the program started to run (and in fact, at least one interpreter does this in most cases). However, they are typically special-cased to run more efficiently (in terms of the length of time needed for an interpreter to determine the winner of a match, as opposed to anything that affects the result of the match itself), and thus are often worth using on that basis as well as the readability gains.

History[edit]

The original version of BF Joust lacked the special syntax for repeating code and the . instruction. Each match was a single round on a random tape length in only the "sieve" polarity. Moreover, the tapes were very long, containing at least 135 cells. Commensurate with the longer tape lengths, matches lasted longer, going to 384,000 cycles. Finally, the flag was considered down if it reached zero for even a single cycle.

User:ais523 added the . instruction, shortened the tape lengths to current values (see the section "Matches"), added the special syntax, and added the rule about the flag needing to be down for two consecutive cycles.

ehird added the requirement that a match be run on all tape lengths and both polarities for the version (egojoust) that was built in to EgoBot. At the same time, Gregor devised a scoring system for a tournament "hill", where beating better opponents improved your score as much as beating more opponents.

zem.fi BF Joust hill[edit]

Information about the current "official" BF Joust hill of #esoteric (on freenode) can be found at http://zem.fi/bfjoust/.

To add a program to the #esoteric BF Joust hill, join #esoteric on freenode, and type

!bfjoust <your program name> <your program source>

In a few seconds your score will be reported and the scoreboard will be updated. You may also send programs in private messages to zemhill, using the same syntax. If your program is too long to fit on a line of IRC, you can instead post it online and use a link starting with http:// in place of the program.

If you want to try out the system without recording your program for posterity (or tune constants etc.), the !bftest command is otherwise equivalent to !bfjoust, with the exception of not permanently modifying the hill.

The source code for most of the things related to the hill can be found at https://github.com/fis/chainlance/.

egojoust[edit]

EgoBot used to run the BF Joust hill on #esoteric on FreeNode until it was replaced by zemhill in September 2014.

For a long time it was named after the interpreter it used, egojoust. It later was changed to use gearlance instead, but "egojoust", a plausible name for a BF Joust hill running on EgoBot, was still often used to refer to the hill.

The final scoreboard for EgoBot's hill can be viewed at http://codu.org/eso/bfjoust/report.txt (with an explanation of the most recently added program's scoring at http://codu.org/eso/bfjoust/breakdown.txt).

All programs that were on the hill when it was replaced are available at http://codu.org/eso/bfjoust/in_egobot/, which may also be cloned as an hg repository for old programs.

EgoBot's scoring algorithm can be found at http://codu.org/eso/bfjoust/SCORES

The source code for EgoJoust and EgoBot are available in EgoBot's Mercurial repository at https://codu.org/projects/egobot/hg/ .

Latest changes[edit]

Due to ambiguity in the definitions of expandable repetitions, they are being further defined. Current thoughts are:

  • Parentheses must directly contain either one or zero braces after the expansion of all interior parentheses.
  • Braces may be nested within braces. The innermost parentheses match the outermost braces, and expanding that pair first makes the rest apparent. (a(b{c{d}e}f)%2g)%2 expands to abbcabbcdeffgeffg:
    • (a(b{c{d}e}f)%2g)%2
    • (abbc{d}effg)%2
    • abbcabbcdeffgeffg
  • Any parentheses which directly contain braces after expansion of all interior parentheses must be terminated by a %.
  • Any parentheses which do not contain braces after expansion of all interior parentheses must be terminated by a *.
  • Parentheses may be terminated by *0, in which case their content is ignored.
  • The behavior of braces within parentheses terminated by %0 is currently disputed, but since this is a worthless construct they may be left undefined.

Furthermore, it is currently disputed whether a program which lowers a flag to zero then on the next turn leaves the tape loses or ties. This is because it is unclear when the conditions for a flag being down for two cycles and the tape pointers being valid should be checked relative to each other; there is some controversy about whether it's simultaneous, or one happens before the other. (It seems that most interpreters, however, consider the pointer position check to happen before the flag value check, and thus lose first.)

Strategies[edit]

BF Joust is more involved than the simple rules might imply. Various strategies are detailed at BF Joust strategies.

External resources[edit]