Lua Joust is a competitive programming game, codified by Lymia with the help of ais523 in 2016, equivalent to BF Joust with arbitrary length programs. Instead of using brainfuck to control warriors, Lua Joust uses Lua 5.3 with several environment changes for determinism and sandboxing.
The arena consists of between 10 to 30 cells, which both programs manipulate through the warriors they control. Each cell in this arena holds a value between 0 and 255, inclusive. These values wrap, so that 255 plus 1 is 0 and 0 minus 1 is 255. 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, are called 'flags', and each warrior starts on its respective flag at the beginning of each round.
When a warrior advances "forwards" via the
advance() command, it moves in the direction from its flag towards the enemy's flag. Advancing it "backwards" moves in the opposite direction.
Each cycle of a match consists of one turn from both warriors. Every cycle, each program executes simultaneously until they decide on the move their warrior will make on its turn. This repeats until one or both of the programs have lost the battle, or 100,000 cycles have passed.
A programs loses when either of the following happens:
- Its own flag is set to zero for two consecutive cycles, or
- Its warrior leaves the arena (that is, it executes
advance()command at its enemy's flag or
retreat()at its own flag)
A program wins if the other program 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 arena ("committing suicide")
If both programs lose simultaneously, or the 100,000 cycle limit is reached, the game ends in a draw.
Tournaments should run 42 rounds between the two programs. Two things are varied each round: a round is run with an arena of every length between 10 to 30 inclusive, and one of the warriors may have its polarity exchanged. The effects of its
minus() commands are exchanged. The polarity where both warriors run on their original polarity is known as the "sieve" configuration, and the exchanged polarity as the "kettle" configuration.
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.)
Each program controls its warrior using the following API functions:
plus()increments the cell its warrior is in.
minus()decrements the cell its warrior is in.
advance()advances its warrior forwards one cell.
retreat()retreats its warrior back one cell
wait()does nothing for one turn.
trueif the cell its warrior is in was non-zero at the start of the cycle, and
Each of these functions use up a turn when they are called. More information can be found in the "The Battle" section below. All these functions except for
test() may be called with a single numeric parameter. This repeats the function that many times, taking another turn each time it executes. Each of these functions has a one character alias that does the same thing as the full command.
If the warrior's program ends or encounters an errors, it will do nothing for all further turns.
In addition to the basic rules, there are some additional technical details that may be used by some programs.
So that programs using functions in the
coroutine table behave consistantly between implementations, we define a low level API for them. The Lua Joust API functions should be implemented in terms of this interface.
Once the warrior's program is compiled into a chunk, it is wrapped into a coroutine. All communication between the implementation and the program is done through the
coroutine.yield function. Each time the program's coroutine yields, it uses a turn. It may pass the following commands through this interface, by calling
coroutine.yield(command) with a single constant. These constants are stored in the program's
_ENV table, and their exact value is unspecified.
coroutine.yield(OP_PLUS)increments the cell its warrior is in.
coroutine.yield(OP_MINUS)decrements the cell its warrior is in.
coroutine.yield(OP_ADVANCE)advances its warrior forwards one cell.
coroutine.yield(OP_RETREAT)retreats its warrior back one cell.
trueif the cell its warrior is in was non-zero at the start of the cycle, and
- If any other value, or no value at all is passed into
coroutine.yield, nothing happens. However, it still uses a turn.
If the coroutine containing the warrior's program terminates for any reason, the battle will continue and the warrior continues as if the program executed
coroutine.yield() on all further cycles.
Besides sandboxing concerns, the Lua environment must also be sanitized so all programs in it are deterministic. Otherwise, programs in it could not be converted into BF Joust programs. All functions normally present in a Lua 5.3 environment are present, with the following changes:
requirefunctions and the
packagetables are removed for sandboxing purposes.
tostringfunction is modified to not reveal the address of tables, threads, functions, or userdata.
collectgarbagefunction is removed as being able to introspect the garbage collection may allow for non-deterministic behavior.
math.randomseedfunctions are removed for obvious reasons. Not only is the starting seed non-deterministic, but the random algorithm is platform dependent.
In addition, in order to facilitate secure implementations in Lua, the following changes may be made:
setmetatablefunctions may be modified to refuse to work on values that are not tables.
- The enumeration order for the
pairsfunctions can depend on the address of tables, threads, functions, or userdata values, and cause non-deterministic behavior.
__modemetamethods depend on garbage collection and may cause non-deterministic behavior.
- Converting a floating point number to a string calls the libc sprintf or snprintf function, so the result depends on the libc. The number of digits in the exponent, the number of digits in the mantissa, and the format of infinity and nan values can depend on the libc. This is true whether you convert by implicit conversion through concatenation, explicitly with the tostring function, or formattedly with the
- Converting a floating point nan value to a string reveals its sign, and may also reveal its mantissa. The sign of a nan value you get from ordinary arithmetic can depend on the way lua is compiled and optimized. The easiest way to fix this would be to change stringification, since lua does not currently offer any other way to find out about the sign of nan values (in particular, there are no signbit or copysign functions in the standard library).
- We have to be careful with transcendent maths functions. Ideally, these should be reproducible and give the precise and correctly rounded result, but if the libc you compile with doesn't provide that, you could be in trouble. It may be possible to provide alternate implementations for those functions from another library, but it's probably easier to just remove them. The lua library functions that (may) matter here are: the built in ^ operator (possibly the most vulnerable), math.acos, math.asin, math.atan, math.cos, math.exp, math.sin, math.tan; and if compiled for compatibility to lua 5.2, which may be the default, also math.atan2, math.cosh, math.sinh, math.pow, math.log10, math.frexp . As a special case, the math.frexp implementation will be precise, but its return value on an infinite or nan output is undefined and may depend on the libc and compilation options.
- The manual doesn't define what the
#operator returns for a non-sequence table, but Lymia has read the implementation of tables and claims it's deterministic.