BF Joust

From Esolang
(Redirected from Zemhill)
Jump to navigation Jump to search

BF Joust (also known as BFJoust and 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

Syntax

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

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

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 cell and cycle increase the cell by two, and + and - on the same cell and cycle cancel each other out and don't do anything. The potential ambiguity is with [ or ] on the same cell and 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

Rather than running a single round (which would have a random tape length from 10 to 30), tournaments generally run 42 rounds (or "jousts") 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 rounds are draws.)

Abbreviations

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

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.

Competitive hills

There is currently one "official" BF Joust hill: it has a website at http://zem.fi/bfjoust/ and is run by the IRC bot zemhill.

The easiest way to submit a program to the hill is the web form on http://zem.fi/bfjoust/ . You can also submit a program to the hill using the #esolangs IRC channel (on Libera.Chat). To test the waters, write !ztest, followed by a program name, and the program's source; so, for example, !ztest bad < to test the program that always loses immediately, named bad. If the program is long, the source code section can also be a link (starting with http://or https://) to a plain text file on the Internet; note that many pastebins will not let you paste plain text. The bot will respond by telling you what score the program would get on the hill, without actually committing it. Once you're happy with the results, do the same thing but with the command !zjoust instead: this will make the submitted program replace the previously worst-scoring one. If the program and its name fits in one IRC line then you can also try to say perlbot ztest followed by a program name and the program's source, eg. perlbot ztest bad < , or similarly submit using perlbot zjoust.

Source for the hill, and the programs currently and previously on it, is available at:

There have also been past BF Joust hills, most prominently the "egojoust" hill, which used to be at http://codu.org/eso/bfjoust/ (dead link).

Latest changes

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

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

External resources

Retrieved from "https://esolangs.org/w/index.php?title=BF_Joust&oldid=144123"