Bucket expression arithmetic

This document describes in detail the syntax and semantics of expressions used in determining the set of buckets into which a piece can be moved. These expressions appear as the last field of each "atom" in rule sets.

Set-based evaluation

Whenever a given "atom" of a rule matches the position, shape, and color of a piece which the player attempts to move, the game engine evaluates the expression in the "bucket" field of the atom, obtaining the list of buckets into which this piece can be moved. The move is allowed only if the destination bucket chosen by the player is among the buckets on this list.

The expression in the bucket list is always evaluated to a set. It can be an empty set (which means that the piece cannot be moved), a set with one element (i.e. there is only one possible destination), or a set with several elements.

Syntax

Formally, the syntax of the expression in the bucket field can be described by the following grammar:

• Any expression:
  E ::= E₅
• A logical expression can be composed of 2 additive expressions:
  E₅ ::= E₄ | E₄== E₄
• An additive expression can be composed of any number of multiplicative expressions:
  E₄ ::= E₃ | E₄ additiveOp E₃
• additiveOp ::= + | -
• A multiplicative expression can be composed of any number of elementary expressions:
  E₃ ::= E₂ | E₃ multOp E₂
• multOp ::= * | / | %
• A unary expression consists of a unary operator (of which we have only one, the negation) preceding an elementary expression or a unary expression:
  E₂ ::= E₁ | unaryOp E₂
• unaryOp ::= !
• An elementary expression is an ID, a Number, a parenthesized expression, or a bracket list:
  E₁ ::= ID | Number | [E₅ {, E₅}⁺ ] | (E₅)
• An ID is one of the 5 predefined variable names (case-sensitive):
  ID ::= p |pc |ps |Nearby |Remotest
• A Number is a non-negative integer number, written as a sequnce of decimal digits:
  Number ::= digit⁺
• digit := 0|1|2|3|4|5|6|7|8|9

The table above also shows the precedence of operators (i.e. the order of execution): operators composing any E₁-type expressions have the highest precedence, following by those composing E₂-type expressions, etc.

As in most languages, additive and multiplicative expressions are evaluated from the left to the right, i.e. p-pc+ps-3 is the same as (((p-pc)+ps)-3)

Semantics

The arithmetic is performed on sets, but, as long as all sets involved have exactly one value, the process looks entirely like the evaluation of an expression in a language such as Java or C++, with an exception for the equality and negation operations (discussed below).

• A number (a numerical constant) represents a set of one value.
• An ID may be evaluated to an empty set (e.g. for p, pc, or ps early in the episode), a set of one value (usually), or (potentially, in the future) to a set of several values (e.g. Nearby or Remotest for some cells on an odd-sized board)
• A parenthesized expression evaluates to whatever the expression inside the parentheses evaluates; the parentheses simply serve to control the order of operations.
• A bracket list is evaluated to the union of the sets to which the elements are evaluated. E.g. [[0, 2], [2, 3], 0] evaluates to [0, 2, 3.
• An additive or multiplicative operation on set-valued arguments produces a cross-product. E.g. S₁+S₂ produces a set that includes every value x₁+x₂ with an x₁ in S₁ and x₂ in S₂₁. For example, [1,2,10]*[5,10] = [5,10,20,50,100]; [0,1,2]+[0] = [0,1,2]; [0,1,2]+[] = [].
• The division (/) and the remainder operation (%) are performed like integer operatins in Java or C, with rounding toward zero. For example, [2,5,10]/[3] = [0,1,3]; [-4,4]%[3]=[-1,1].
• A division by zero (or remainder from division by zero) produces no result; in other words, no expression for the pair involved is included into the result set. For example, [7]/[0,2] = [3]; [0]/[0]=[].
• Unlike C++ or Java, the equality operation S₁==S₂ is also computed as a crossproduct, producing an empty set if S₁ has not a single element that's equal to an element from S₂, or a set with one element, [1], if S₁ has an element that's equal to an element from S₂. For example, [0,2]==[1,3] produces [], while [0,2,3]==[3] produces [1]. Somewhat counterintuitively, []==[] produces [] as well.
• The negation operator works as follows: if E is an empty set, !E evaluates to [1]; otherwise, to [].

As in most programming languages, one can insert additional (unnecessary) parentheses around high-precedence subexpressions without affecting their meaning. So, for example, !!p has the same meaning as (!(!(p))), and 2*3-1, as ((2*3)-1).

Final modulo-4 processing

Since buckets are numbered 0 thru 3, a bucket number outside of this range makes no sense. Therefore, after the bucket expression is computed, every memeber of the resulting set is translated to the [0..3] range by a modulo-4 transformation, i.e. n := ((n%4)+4)%4. (It is not simply (n%4) because the % operation in Java or C, or in our language, produces a negative result on a negative argument; e.g. (-5)%4=(-1)). Therefore, it is safely, for example, to write simply p+1, instead of (p+1)%4, to mean "the next bucket (in the clockwise order) after the bucket into which accepted the previous moved piece".

Examples

Rule set examples

Example 1

(1,*,*,*,[!p*[0,1,2,3], !!p*(p-1)])
(*,*,*,*,(p==Nearby)*p)

• The first piece can be put into any bucket. (First line, where !p evaluates to [1]).
• After that, the second line becomes active; the player then must pick every piece in the quadrant of the board adjacent to the bucket that was used for the first piece, and put them into the same bucket.
• After that, the control reverts to the first line, where !!p evaluates to [1], which means that the player can put any piece and put it the bucket that is the next one, in counterclockwise order, to the first used bucket.
• Contol goes to the second line again; the player now must pick all pieces in the quadrant adjacent to the last-used bucket, and put them into that bucket. Etc.

Try it!

You can test your arithmetic in this form: Expression entry form.