It has been suggested by Jerry that we introduce the capability for using code snippets in Rule Game rules, which can potentially significantly expand the universe of possible rule sets. In this document I discuss a possible way of doing that, in what likely will become Game Server 4.*.
One can imagine several use cases for that:
Both in the original GS 1.* syntax and in the expanded GS 3.* syntax, the operation of rule sets can be described as follows:
In order to simplify the use of code snippets, we propose that code snippets be used as condition within rule atoms. Each code snippet will have the form of the body of a method (function) in some popular programming language (to be decided upon later), e.g. a function expected to return a "boolean-interpreted" value (0 or 1) in Perl, or a method with a boolean return value in Java. The job of the code snippet would be compute this return value; higher-level logic (the conjunction of this return value with any other components of the atom to obtain the atom's acceptance decision; disjunction of the atom's acceptance decision with those of other atoms in the line; managing all counter variables; transfer control between rule lines) will remain the responsibility of the game engine.
To do useful work, the code snippet will, of course, need access to some data about the current board state and the intended move. We will discuss this later in this document.
At this point, I have not committed to any specific language that can be used in the snippets. It's likely that eventually the choice will be for Java syntax, since the Game Engine is written in Java, and the Java enviroment provides access to some tools for compiling additional Java code.
For illustrative purposes, most of the exaxmples below will use Perl syntax.
Regardless of the language used for the snippet, an important queston to ask is: What kind of data we would need to make available to the "code snippets" in order for the snippets to be able to describe all the currently (GS 3.*) expressable rules? And what data would we need to make available to the "code snippets" in order for the snippets to be able to describe a much wider, but still sensible, universe or rules?
Let's answer the fiest question first, i.e. what data snippets would need to be able to access in order to express all rules expressable in GS 3.*?
An atom of GS 3.* rules, in the GS 3.* syntax, can be written as
It appears that access to the above-listed variables and functions is sufficient for code snippets to express the semantics of any atom supported in GS 3.*. If that's all we wanted to support, the snippets themselves won't need any "memory" capacity, i.e. a snippet won't need to "remember" anything about previous calls to the same snippet. In other words, snippets can be stateless.
While it appears from the example above that an atom with a code snippet is more cumbersome than an equivalent atom in the traditional format, one can see that a single code snippet can replace mutltiple atom. Consider, for example, a rule line with the following functionality (on a board with objects of GS 1.* legacy shapes and colors):
Pick 5 squares, of any colors, and put them into buckets in accordance with their colors (buckets 0, 1, 2, 3 taking colors black, red, blue, and yellow, respectively).
Pick up to 3 squares and up to 2 triangles, of any colors, and in any order, and put them into buckets in accordance with their colors (buckets 0, 1, 2, 3 taking colors black, red, blue, and yellow, respectively). After that, go to the next rule line.
Some of the motivation for using code snippets is that they could allow describing game rules that are not expressable in the current syntax (that of GS 3.*). Those are not necessarily "more complex" rules -- some of them may be intuitively simple rules (so they can, for example, be thought up by students or M-Turkers participating in the experiments), but they are outside the universe of rules supported by the GS 3.* rule syntax.
For example, on 2021-02-28 (email Subject: Can one code a certain concept in the Rule Game), Paul described the following rule:
At move 1, the player may put anything anywhere. Say he puts a blue square in the top left. After that, he has to put all the squares in the top row, and all the blue things on the left side, but either bucket on the given edge is allowed.
If the player wants to move piece Q with color Q.color and shape Q.shape, find out what was the first successfully moved piece A with the matching shape, and what was the first successfully moved piece B with matching color. If A exists, then Q can be received in the same bucket in which A was received, or the other bucket in the same row; if B exists, then Q can be also received in the same bucket in which B was received, or the other bucket in the same column. If neither A nor B exist, then Q can be received in any bucket.
To implement this rule, the code snippet would need to access to some historical information that is not supplied to the rule atoms in the current syntax.
Generally, what kind of information would we want to make available to code snippets to provide for a wide, but still fairly sensible, universe of rules?
The above collection of information can, of course, be also described in a slightly different away; e.g., instead of "the initial board + the history of successful moves" one can give the snippet access to "the current board + the history of successful moves". The two collections of information provide equivalent knowledge.
In addition, if one desires to code stochastic (non-deterministic) rules, the code snippets may have access to a random number generator, as provided by the appropriate APIs of the snippet language (e.g. In this proposal, I suggest that we do not give the snippets access to the following data:
The information that we do want to provide to the snippet can be packed in various data structures. E.g. in Java, one can have the current board as a 2-D array of For the next two examples, we will work with the set of objects representing playing cards, with the properties suit (the values being hearts, spades, etc) and value (the values being integers from 1 (for the ace) to 13 (for the king).
We illsutrate the use of the current board information (accessible as
A card can only be moved if it has the highest value in its column. Such a card can be moved to any bucket.
In the following example, the rules are as follows:
The player's task is to sort the cards by the suit into the four buckets, placing the cards of each suit in the increasing-value order (i.e., a higher-value card may only be put in the bucket after a lower-value card).
A snippet implementing the above rule can be written just using the history array ( This code can be made a bit shorter if we provide code snippet authors with an API that will allow them to do certain commonly needed by operations with a single function call, rather than e.g. looping through a data structure.
Suppose we have families that can contain as many as 6 images which form a "natural graded sequence." Examples might be circles of increasing size, or squares of increasing opacity. We may suppose that the names of the images include their sequence numbers. However, we might want a rule such as: if the objects in a row are in monotonic order, that row should be cleared to the right; but if they are not in monotonic order, they should be cleared to the left..
These rules can be formulated with a reference to the history of successful moves. Every time the player wants to remove a game piece from row $r$, the code snippet invoked by the game engine checks whether the episode's history contains any moves of pieces from row $r$. If no such moves has been recorded, the code examines all pieces in row $r$, and, dependent of whether their values form a monotonice sequence; depening on that, the code will only accept the current move attempt if the piece currently being moved is the leftmost or rightmost (as appropriate) piece in row $r$. On the other hand, if some pieces from row $r$ have already been removed, we know that the remaining peices may only be removed in the same order, which allows us to know whether the leftmost or rightmost piece is to be picked now.
With the use of random number generators available in programming languages such as Perl or Java, the code snippets would be able to create non-deterministic rules. In the following example, the code snippet randomly picks one bucket as an allowed destination at every move attempt:
All the above examples were stateless: while they knew something about the history of the episode, all historical information was supplied by the game engine via a certain number of variables. Thus, the game engine strictly controlled what the snippet was allowed to know about its history.
We can allow the game designer to overcome this restriction by allowing him to use state variables which preserve their value between invocation of snippets. Those exist in many languages, such as Java does not have static local variables, but an equivalent functionality can be achieved by declaring e.g. an instance variable in the class into which the game engine will wrap the game-designer-created snippet and allowing the player to use that variable in the snippet; if the game engine calls the snippet from the same instance of the class during a given episode, its values will be preserved between snippet invocations. The variable can be declared as e.g. a Use of such static variables has a practical advantage, in that in some cases it allows the game designer to express the same rules in more concise or more logical way, or it allows to avoid repeating some computations. (E.g., the
monotonic vs. non-monotonic rows example above can be re-written in an easier-to-understand way with static variables).
On the other hand, unrestricted use of static variables will also allow to design games that make use not only the history of successful moves, but that of unsuccessful moves as well. So this will, for example, allow to create a snippet implementing the following rule:
The player must pick a piece and attempt to place it into the same bucket 3 times in a row; only then will it be accepted.
Additionally, if game designers are allowed to use static variables, they can, in principle, completely obviate the use of the high-level flow control provided by the game engine (counter variable management and transfer of control between rule lines), but, instead, put all functionality into one large snippet, with static variables used to manage the change of the snippet's behavior between invocations.
I will leave it to the PIs to decide if we want the "stateful snippet" capability.
If desired, it is also possible to enable game designers to use static variables shared by multiple snippets within the same rule set, or possibly even define functions that can be used in multiple snippets. One use of this feature may be fairly trivial, e.g. to avoid duplicating the same code in several snippets. However, it can also be used to provide a way to write more interesting snippets.
(count:count, property1:valueList1, property2:valueList2, ..., pos:positionList, bucket:bucketList)
, with all fields being optional. The bucketList may contain an arbitrary set-arithmetic expression involving several variables. This atom encodes a conjunction of expressions, each of which applies to a single property, or a single variable. So, for example, an atom
(count:4, species:[rabbit,hare], color:white, pos:T, bucket:p.species)
can be rewritten in the following was with a code snippet (written as a function body in a Perl-like language):
(For readability, line breaks are introduced in the code snippet. There is no explicit reference to the counter in the snippet because the counter testing and incrmenting will be performed by the game engine after the code snippet returns it return value). The code snippet above has access to the following built-in variables and functions:
(count:4, code:{my $accepted =
($prop{'species'} eq 'rabbit' || $prop{'species'} eq 'hare') &&
($prop{'color'} eq 'white') &&
&isLeading( $predefinedOrderings{'T'}, $pos) &&
($bucket == $lastBucket{'species'}{$prop{'species'}});
return $accepted;})
%prop -- an associative array (hash table) that contains the values of all defined properties of the game piece the player wants to move;
$pos -- an integer variable (in the range 1 to 36) indicating the board position of the game piece the player wants to move;
$bucket -- an integer variable (in the range 0 to 4) indicating the bucket to which the player wants to move the game piece;
&isLeading($ordering,$pos) -- a function which tests whether the specified position ($pos) on the board is the first (or one of the first) occupied positions with respect to the specified ordering. The argument $ordering is described as a one-dimensional or two-dimensional array of integers (so that orderings with ties could be supported);
$T = [[31,32,33,34,35,36], [25,26,27,28,29,30], ...];
%lastBucket -- an associative array (hash table) that contains, for each property name p and each possible value v of that property, the number of the bucket into which a piece with the appropriate value of that property was most recently placed. E.g. $lastBucket{'shape'}{'black'} contains the number of the bucket that received the black square most recently removed from the board.
One can express this by a rule line of 4 atoms, with a global counter:
On the other hand, this can be written in a single atom with a snippet:
5 (shape:square, color:black, bucket:0) (shape:square, color:red, bucket:1) (shape:square, color:blue, bucket:2) (shape:square, color:yellow, bucket:3)
Furthermore, even with only the limited capabilities allowed in this section, code snippets can be used to express some rules not expressable with the traditional syntax. In the traditional syntax, for example, there seems to be no way to write a rule line with the following functionality:
5 (code:{my %h=('black'=>0, 'red'=>1, 'blue'=>2, 'yellow'=>3); return ($prop{'shape'} eq 'square') && ($bucket==$h{$prop{'color'}})})
With snippets, this is doable:
(For readability, we use the backslash character as the line continuation character. The text above form a single rule line).
(count:3 code:{my %h=('black'=>0, 'red'=>1, 'blue'=>2, 'yellow'=>3); return ($prop{'shape'} eq 'square') && ($bucket==$h{$prop{'color'}})}) \
(count:2 code:{my %h=('black'=>0, 'red'=>1, 'blue'=>2, 'yellow'=>3); return ($prop{'shape'} eq 'triangle') && ($bucket==$h{$prop{'color'}})})
Towards a more general universe of rules
We can formalize this rule as follows:
In other words, as the player goes along, each color become permanently associated either with the buckets on the left side of the board or those on the right side, and each shape becomes permanently associated either with the buckets on the upper edge of the board or those on the bottom edge. The player can create arbitrary associations whenever he picks a piece neither whose shape nor whose color have been previously assigned.
java.util.Random in Java).
Piece objects, each Piece containing the property information; the history of moves can be in an array of Move objects, each one containing information about the piece being removed and its destination bucket. Similar structures exist in Perl as well. Based on those structures, the snippet can obtain all information it needs. As an example, the snippet to implement the rules suggested by Paul on 2021-02-28, may look as follows (in Perl syntax):
Here, in addition to the variables we have introduced in the previous section, the code snippet has access to the array {
my %h = (); #-- the set of accepting buckets for this move
for my $move ($moves) { #-- scan the history
my $moved = $move->{'moved'}; #-- the piece that was moved
if ($moved->{'shape'} eq $prop{'shape'}) { #-- was same color as current piece?
my $b = int($moved->{'bucket'}/2) * 2;
$h{$b} = 1; #-- add buckets in the same row
$h{$b+1} = 1;
}
if ($moved->{'color'} eq $prop{'color'}) { #-- was same color as current piece?
my $b = int(($moved->{'bucket'}+1)/2) * 2;
$h{$b % 4} = 1; #-- add buckets in the same column
$h{($b+3)%4} = 1;
}
if (scalar(%h)==0) { for my $j (0..3) { $h{$j}=1;}}
return (%h{$bucket}? 1 : 0);
}
@moves, representing the history of successful moves, in chronological order.
@board, with $board[$row][$col] referring to the piece in the appropriate row and column) in the following example, where the rules are as follows:
The appropriate snippet may look as follows:
{
my $val = $prop{'value'};
my $row = 1+int(($pos-1)/6), $col= 1+(($pos-1) % 6);
for my $y (1..6) {
if (defined ($board[$row][$y]) && $board[$row][$y]->{'value'} > $val) { return 0; }
}
return 1;
}
Note a difference from the universe of the currently allowed rules. In the current rule universe, for a given set of rules and given initial board, one of the two always holds: either the game is not solvable (that is, there is no sequence of move attempts that will clear the board), or it is always solvable (that is, even if the player knows nothing about the rules, and regardless of the moves he has already made, he can clear the board by a simple pre-defined strategy, e.g. trying to move every piece into every bucket, cyclically). With a rule such as given above, for every initial board there is a way to clear it, but also there may be sequences of moves which will prevent the player from ever completing the clearing. For example, if the board has a queen of spades and the king of spades, and the player removed the king first, there is no way for him to ever remove the queen thereafter.
@moves):
{
my $suite = $prop{'suite'};
my %acceptingBuckets = ('hearts'=>0, 'spades'=>1, 'clubs'=>2, 'diamonds'=>3);
my $b = $acceptingBuckets{$suite};
if ($bucket ne $b) { return false; } #-- wrong destination bucket
#-- find the topmost card in the destination bucket
my $lastCardVal= undef;
for(my $j = $#moves; $j>=0; $j--) {
if ($moves[$j]->{'bucket'} == $b) {
$lastCardVal = $moves[$j]->{'value'}; break;
}
}
if (!defined $lastCardVal) { return 1; } #-- the bucket is still empty
return ($lastCardVal <= $prop{'value'}) ? 1 : 0;
}
Example: monotonic vs. non-monotonic rows
For the next example, consider the rules proposed by Gary on 2021-04-24 (as relayed by Paul):
Let's assume that the property whose monotonicity the palyer needs to notice is named value, similar to our playing card examples.
{
my $N=6;
my $row = int(($pos-1)/$N);
my $col = ($pos-1)%$N + 1;
#-- Does the piece being moved happen to be leftmost or rightmost or neither?
my $leftMost=1, $rightMost=1;
for my $c (1..$N) {
if (defined $board[$row][$c]) { #-- there is a piece at (row,c)
if ($c<$col) { $leftMost=0; }
elsif ($c>$col) { $rightMost=0; }
}
}
#-- have any pieces been removed in this row yet?
my $fromLeft= 0, $fromRight=0;
for(my $j = $#moves; $j>=0; $j--) {
my $moved = $move->{'moved'}; #-- the piece that was moved
my $p = $moved->{'pos'};
my $r = int(($p-1)/$N);
if ($r == $row) {
my $c = ($p-1)%$N + 1;
if ($c < $col) { $fromLeft=1;}
elsif ($c > $col) { $fromRight=1;}
}
}
if (!$fromLeft && !$fromRight) { #-- still-untouched row. Is it monotonic?
my $lastVal = undef, $lastD = undef, $isMono = 1;
for my $c (1..$N) {
if (defined $board[$row][$c]) { #-- there is a piece at (row,c)
my $v = $board[$row][$c]->{'value'};
if (defined $lastVal) {
my $d = $v-$lastVal;
if (defined $lastD) {
$mono = $mono && ($d * $lastD >= 0);
}
$lastD = $d;
}
$lastVal = $v;
}
}
if ($mono) { $fromLeft=1;}
else { $fromRight=1;}
}
return $fromLeft? $leftMost : $rightMost;
}
Randomness
To play this game, the player can simply keep trying to put the same game piece into any bucket (say, bucket 0), until it is accepted. On average, 1 out of 4 attempts will succeed, which means that the player will need, on average, 2.5 attempts to remove a piece.
{
my $b = int(rand()*4);
return ($b == $bucket) ? 1 : 0;
}
Stateful snippets with static variables
Stateful snippets
own variables in Algol-60, local static variables in PL/1, C, and C++, or state variables in Perl.
HashMap, so that the snippet can use it for storing arbitrary data. One can also make a distinction between such variables only accessible within a given snippet, and those shared between snippets. In the latter case, the game designer can create its own custom functionality of the kind that's available in the array %lastBucket introduced earlier in this documenty (the code-snippet equivalent of pc and ps of GS 1.*).
{
state lastTryPos = undef, lastTryBucket=undef, tryCnt=0;
if (!defined $lasTryBucket) ....
my $b = int(rand()*4);
return ($b == $bucket) ? 1 : 0;
}
Sharing information between snippets