Functions and Lists

This section of the tutorial describes two powerful new tools that were added in version 0.4: functions and lists.

Contents

Functions

Combinatorial Game Suite permits user-defined functions.  A function can be a simple mapping between objects or a more complicated recursive definition.  As a simple example, the following function sets up the mapping n -> n.^:

f(n_) := n.^

The underscore _ indicates that the function is being defined for all values of n, rather than for a single specific value.  After defining f, you can access its values by typing simply (for example):

f(2)

To construct a recursive definition, specify the general rule in conjunction with any number of base cases (typed in as separate statements).  For example, the following is an alternative way to specify the mapping n -> n.^:

g(0) := 0;
g(n_) := {0|g(n-1)+*}

Try typing g(2) to check that it works.  Notice that this is just the usual recursive definition of the canonical form of n.^.

Combinatorial Game Suite keeps track of all the previously computed values of a function.  It also remembers whether a value was entered manually (as a base case) or computed automatically (using a recursive definition).  If you change the function by entering new base cases, redefining old ones, or changing the recursive definition, then all of the calculated values will be cleared (but not the manually entered ones).

You can type clear(f) at any time to destroy any existing information about f.

Example: Blockbusting

One of the most useful applications of functions is to specify recursively the positions of a game.  As an example, we'll write a function that calculates the values of blockbusting positions.  Blockbusting is a simple game played on a 1xn or nx1 grid. Left, on his turn, places a bLue house on any empty square; Right places a Red house on any empty square. The game ends when no empty squares remain on the grid. Once play has finished, the players tally up their scores. If the grid is 1xn (horizontaL), then Left scores one point (that is, one free move) for each pair of adjacent bLue houses; if the grid is nx1 (veRtical), then Right scores one point for each pair of adjacent Red houses. For example, if the final position on a 1x10 grid is RRLLLLRRLL, then its value is 4: one point for the LL at the end, and three points for the LLLL (note that the four adjacent L's count as three pairs.) The value of the corresponding 10x1 position is -2. (Note that since Right can never score on a 1xn grid, no horizontal Blockbusting position has value < 0, and likewise no vertical Blockbusting position has value > 0.)

Notice that every horizontal Blockbusting position can be decomposed as the sum of "atomic" positions - those of the form LnL (a bLue house followed by n empty squares followed by another bLue house), LnR, or RnR, where n may be 0.  (RnL is equivalent to LnR by symmetry.)  Thus for example, R..LL...L = L2R + L0L + L3L.  This means we can completely solve blockbusting by writing functions LL(n), LR(n), and RR(n) that respectively calculate the values of LnL, LnR, and RnR (horizontal) blockbusting.

This is not quite as easy as specifying n.^ recursively, however: While n.^ has only one left option and one right option, Blockbusting positions of length n have n options available to each player.  The seq keyword, discussed next, provides a convenient way to specify large sets of options.

The seq Keyword and a Blockbusting Solution

You can use the seq keyword to specify a list of objects described by a parameter.  As a first example, try entering the following:

seq(2.n, n=0..5)

You'll see the following result:

[0,2,4,6,8,10]

The brackets [ ] indicate that a list of objects has been specified.  Notice that this list represents the sequence ( 2n : 0 <= n <= 5 ).  Generally speaking, typing

seq(expression, variable=m..n)

evaluates the expression as the variable ranges from m to n (inclusive), and places the results into a list.  This provides a way to specify the left and right options of the Blockbusting examples specified above.  Consider, for example, the case L4R.  Left can place his house into any of the four available positions.  His moves are to L0L + L3R, L1L+L2R, L2L+L1R, and L3L+L0R.  Generalizing, Left's moves from LnR are L0L+L(n-1)R, L1L+L(n-2)R, ..., L(n-1)L+L0R.  So Left's set of moves is { LkL+L(n-k-1)R : 0 <= k <= n-1 }.  In terms of the functions LL(n) and LR(n) that we wish to define, this suggests the following representation for Left's options from LnR:

seq(LL(k) + LR(n-k-1), k=0..n-1)

Typing this in directly will produce an error, though, since we haven't yet defined LL and LR.  But we can use it safely from within the definition of LR.  Likewise, Right's options from LnR are given by:

seq(LR(k) + RR(n-k-1), k=0..n-1)

So we can define LnR by:

LR(n_) := { seq(LL(k) + LR(n-k-1), k=0..n-1)
          | seq(LR(k) + RR(n-k-1), k=0..n-1) }

A similar analysis of LnL and RnR leads to the following complete definition of Blockbusting, which you can copy and paste into the worksheet (it's safe to paste the whole thing onto a single line):

LL(0) := 1;

LL(n_) := { seq(LL(k)+LL(n-k-1), k=0..n-1)
          | seq(LR(k)+LR(n-k-1), k=0..n-1) };

LR(n_) := { seq(LL(k)+LR(n-k-1), k=0..n-1)
          | seq(LR(k)+RR(n-k-1), k=0..n-1) };

RR(n_) := { seq(LR(k)+LR(n-k-1), k=0..n-1)
          | seq(RR(k)+RR(n-k-1), k=0..n-1) };

Notice that although we specified a base case LL(0) := 1, we don't need to specify explicit base cases for LR and RR, since LR(0) and RR(0) will automatically evaluate to empty sets of options for both players.

Try typing LL(20) to test the new definition!

Organizing Results with tabulate

The tabulate keyword provides a way to organize results into nicely-formatted tables.  The use of tabulate is very similar to seq and is best illustrated with an example.  First read through the previous section and make sure you've entered the definitions of LL, LR, and RR provided there.  Then type:

tabulate(n, LL(n), LR(n), RR(n), n=1..15)

This produces a table with 15 rows and 4 columns; each row contains n together with the values of LnL, LnR, and RnR Blockbusting.  In general, typing

tabulate(expression1, expression2, ..., variable=m..n)

evaluates each expression as the variable ranges between m and n (inclusive), and places the results into a table.  There can be as many expressions as you need.

More about Lists

Recall that seq(2.n, n=0..5) creates a list of integers: [0,2,4,6,8,10].  There are various other ways that lists can arise.  For example, typing LeftOptions(G) creates a list containing all left options of G; so LeftOptions(^*) returns [0,*].

Individual list elements can be referenced using brackets: If L is a list, then L[n] is the nth element of L.  Lists can also be entered directly by enclosing the elements in brackets.  An example:

L := [*,vv,1/2]

Then L[1] is *, L[2] is vv, and L[3] is 1/2.

If L is a list, then Length(L) gives the number of elements in L.

Example: Partizan Subtraction Games

Here's a more complicated example that combines functions and lists.  A partizan subtraction game begins with a heap of n beans.  On his turn, Left must remove k beans from the heap, where k is chosen from some fixed finite set L of integers.  Right must do likewise, choosing from some (possibly different) set R.  The first player unable to move loses.  We denote this game by SL,R,n.  Note that Left's options from SL,R,n consist of SL,R,n-k for all k in L with k <= n.  The subtraction sets remain the same, and only the heap size changes.

In this example we'll define a single recursive function subtgame(L,R,n) that specifies all partizan subtraction games.  The function takes three parameters - two lists, L and R, representing Left's and Right's subtraction sets, and an integer n, specifying the size of the heap.  For example, the subtraction game S{1,3,5},{2,4},10 would be entered as subtgame([1,3,5],[2,4],10).We'll specify the Left options of subtgame(L,R,n) using seq, as in the Blockbusting example.  This time, we'll let the variable k index the list L.  From subtgame(L,R,n), Left can move to subtgame(L,R,n-L[k]) as k ranges between 1 and the length of L.  So we want something like the following:

seq(subtgame(L,R,n-L[k]), k=1..Length(L))

There's one catch, however.  n-L[k] might be negative if n is very small.  The solution is to tack on an optional third parameter to seq: A condition that determines individually which elements to include.  Here's a correct description of Left's options:

seq(subtgame(L,R,n-L[k]), k=1..Length(L), L[k] <= n)

Right's options are specified similarly, leading to the following definition of subtgame, which you can copy-paste into the worksheet:

subtgame(L_,R_,n_) :=
  { seq(subtgame(L,R,n-L[k]), k=1..Length(L), L[k] <= n)
  | seq(subtgame(L,R,n-R[k]), k=1..Length(R), R[k] <= n) };

Try typing subtgame([1,3,5],[2,4],10) to evaluate the example described above.

Exercises

1. Tabulate the values of S{1,2},{2,3},n, S{1,3},{2,4},n and S{2,3},{3,4},n for 1 <= n <= 10.

2. The game Seating Boys and Girls is described in Winning Ways.  Left seats boys around a circular table with n chairs, and Right seats girls, with the restriction that no child may be seated next to one of the opposite sex.  Assuming at least one child has been seated, the position is the sum of LnL, LnR, and/or RnR for various n, just as for Blockbusting.  Write functions LL, LR, and RR that compute positions in Seating Boys and Girls and tabulate the values up to n=10.  Compare your answers to those given in Winning Ways.  Try computing L15R separately (not in a table) and note that the game is very complicated indeed!

3. Rewrite subtgame using functions rather than lists, to allow for possibly infinite subtraction sets.  The result should be a function fsubtgame(f,g,n) that takes as parameters two functions, f and g, and the heap size n.  Left can remove f(k) beans from the heap for any k >= 1, and likewise Right can remove g(k) beans.  You may assume that Left's options from a heap of size n are limited to (at most) f(1), ..., f(n), and likewise for Right.  (This sacrifices no generality: We can represent any infinite subtraction set by a function f that is strictly increasing, whereupon necessarily f(n) >= n for all n.)  Test your function by tabulating some values of the odd-even subtraction game where Left can remove an odd number of beans from the heap, and Right an even number.  Verify that even heap sizes are numbers, while odd heap sizes have mean and temperature 1/2.


Continue on to Writing Scripts