This section of the tutorial describes two powerful new tools that were added in version 0.4: functions and lists.
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.
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.
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!
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.
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
.
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.
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.