Lua Joust

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.

Basic Rules

The Arena

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.

The Battle

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.

Matches

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 plus() and 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.)

API

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.
• test() returns true if the cell its warrior is in was non-zero at the start of the cycle, and false otherwise.

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. p() for plus(), m() for minus(), a() for advance(), r() for retreat(), w() for wait(), and t() for test().

If the warrior's program ends or encounters an errors, it will do nothing for all further turns.

Detailed Rules

In addition to the basic rules, there are some additional technical details that may be used by some programs.

Low-Level Interface

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.
• coroutine.yield(OP_TEST) returns true if the cell its warrior is in was non-zero at the start of the cycle, and false otherwise.
• 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.

Lua Environment

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:

• The dofile, load, loadfile, and require functions and the debug, io, os, and package tables are removed for sandboxing purposes.
• The print function does nothing. However, interpreters may still implement it to allow debugging of programs.
• The tostring function is modified to not reveal the address of tables, threads, functions, or userdata.
• The collectgarbage function is removed as being able to introspect the garbage collection may allow for non-deterministic behavior.
• The math.random and math.randomseed functions 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:

• The getmetatable and setmetatable functions may be modified to refuse to work on values that are not tables.

Unresolved Problems

• The enumeration order for the next and pairs functions can depend on the address of tables, threads, functions, or userdata values, and cause non-deterministic behavior.
• The __gc and __mode metamethods 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 string.format function.
• 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.

Resolved problems

• 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.

External resources

• Reference implementation