This is a progress report for my project in Experimental Mathematics,
Spring 2012.

I'd prefer if you did not post a link to this project for now.

DESCRIPTION

The objects I am interested in studying are the following games. Let A
be an alphabet (or a set of colors). Two players alternate placing the
letters of the alphabet into a word. One player, Maker, has a set of
desired patterns which she must attempt to form. If she forms even one
of these patterns, she wins. The other player, Breaker, attempts to
prevent Maker from forming any of these patterns, and if Breaker
succeeds at this goal, he wins. To make things a little more
interesting, Maker and Breaker may be restricted in the letters they
have access to. For example, if A = {1,2,3,4}, perhaps Maker has
access to all the letters, but Breaker only has access to the letters
1 and 2.

* Examples:

A very simple game is then one with A = {0,1} and Maker's set of
desired patterns =  {[0,0,0]}, and both players have access to the
entire alphabet. Here is an example of the game being played on a
board of length 5, with
Maker going first:

[_ _ _ _ _]
[_ _ 0 _ _] Maker plays 0 in position 3
[_ _ 0 1 _] Breaker plays 1 in position 4
[_ 0 0 1 _] Maker plays 0 in position 2
[1 0 0 1 _] Breaker plays 1 in position 1

At this point Maker concedes the game, because she cannot win.

This game is, of course, boring. Obviously Maker is only going to play
0s, and Breaker is only going to play 1s. Also, after many weeks of
intensive testing of the game, Maker and Breaker have come to the
conclusion that this game is somewhat biased towards Breaker, in the
sense that no matter how long the board is, Maker can never win if
Breaker has a clue. So let us make the game a little more interesting
by changing Maker's set of desired patterns to {[0,0,0], [1,1,1]}.

Here is a simple example to show that the game is, in fact, more
interesting:

Breaker to play

[_ _ _ _]
[1 _ _ _] Breaker plays 1 at position 1
[1 _ _ 0] Maker plays 0 at position 4 (!)

Breaker now must concede the game. A little analysis shows that
Breaker's other moves also lose. On the other hand, if Maker starts
the game, she has no good first move, and loses. So this game is a
second-player win.

* Analyzing the "more interesting game":

The Maple package includes functions that can analyze these games
automatically. To define a player, we use the Player object provided
in the package. So the following are the two players:

Maker := Player({0,1}, {[0,0,0], [1,1,1]});
Breaker := Player({0,1}, {});

Now we just have to run the following:

AnalyzeGame({0,1}, B, Maker, Breaker, 5)

and we will get output indicating who wins on a
board of length 5, assuming Maker goes first. As it happens, Maker
wins this game. We can also run

AnalyzeGame({0,1}, B, Breaker, Maker, 5)

and in this case we see that Breaker wins. So actually, the game is a
first-player win on this board. A little more investigation suggests
that the first player wins on boards of odd length, while the second
player wins on boards of even length. While it is easy to demonstrate that
Maker wins going first on boards of odd length and going second on
boards of even length, it is not quite as easy to show by human means
that Breaker can ever win.

* What does this have to do with Szemeredi's theorem?

I'm glad you asked. One natural game is to craft Maker's set of
desired patters to include all "arithmetic progressions" of length k;
that is:

[0,0,...,0,0]
[0,B,0,B,...,0,B,0]
[0,B,B,0,B,B,...,0,B,B,0]
...
[1,1,...,1,1]
[1,B,1,B,...,1,B,1]
[1,B,B,1,B,B,...,1,B,B,1]
...

where B is a blank. (Of course one could also make the alphabet
larger, but for now we will stick to 2 symbols.) Now, because either
the set of 1s or the set of 0s is of positive density, Szemeredi's
theorem says that any sufficiently long word in this alphabet contains an
arithmetic progression of arbitrary length. So for sufficiently large
boards, Maker wins this game even if she delegates the task of making
the moves to a monkey with darts. On the other hand, for sufficiently
small boards, Breaker wins with proper play.

Let's call this game the "k-Van der Waerden game".

A natural question is, what happens in between? Part of the answer is
provided by the following lemmas:

Lemma: If Maker, playing first, wins the k-Van der Waerden game on a board
of length n, then Maker, playing first, wins the k-Van der Waerden
game on a board of length n+2. The same is true if you replace "first"
with "second."

Proof: To win on a board of length n+2, Maker pretends that the two
ends of the board do not exist. As long as Breaker respects the illusion
that the ends of the board do not exist, Maker does too, by playing
according to her strategy on the board of length n and not touching
the ends. This will
result in a Breaker loss, so if Breaker wants to win at some point he
will have to play at an end of the board. Then Maker will just play at
the other end, and Breaker is now forced to play in the center,
once again allowing Maker to use her strategy for the board of length n. (Note
that the two additional letters at the ends of the word can never hurt
Maker.) QED.

Lemma 2: If Maker, playing second, wins the k-Van der Waerden game on
a board of length n, then Maker, playing first, wins the k-Van der
Waerden game on a board of length n+1.

To win on a board of length n+1, Maker starts by playing at one end of
the board, and then treats the remainder of the board as a board of
length n on which she goes second, on which she wins. QED.

So this shows a kind of parity property (which incidentally explains
the result in the "more interesting game" above). If Maker wins going
second on a board of length n, then Maker will win going second on
every longer board with the same parity, and will win going first on
every longer board with opposite parity.

Now, as we mentioned above, Maker must eventually win whether she goes
first or second, by Szemeredi's theorem (or Van der Waerden's
theorem). So at some point, there must be an n such that, with proper
play, Maker wins the k-Van der Waerden game on a board of length n
even if Breaker gets to choose who goes first. Call this n the upper
threshold for the game, and denote it U(k).

Here are the examples which I have been able to compute so far:

U(2) = 3
U(3) = 5
U(4) = 11
U(5) <= 178 (this is W(2, 5), the Van der Waerden number; the true value
is likely much lower)

Similarly, since Breaker wins on very short boards, there must be a
first n such that Maker can force a win if she gets to choose who goes
first. Call this n the lower threshold for the game, and denote it
L(k).

Here are the examples which I have computed so far:

L(2) = 2
L(3) = 4
L(4) = 6
L(5) >= 13

* Another Interesting Game:

To illustrate the versatility of the Maple package, even in its
current form, here is another interesting game that can be analyzed by
the same tools.

Maker and Breaker work at a movie studio. There are currently four
different movies being made at the studio, each of which requires use
of the main set in order to shoot. Access is provided in
uninterrupted blocks of 1 hour. Two of the movies are high-budget and
two are low-budget.

According to the Actor's Guild, actors are not allowed to be in the
studio for more than 3 hours straight. After that time, they have to
get a 1 hour break. So no movie can be scheduled for access to the
main set for 4 hours in a row.

Also, there are only two "green rooms" for the actors and crews to sit
in while waiting for their turn to shoot. The actors must show up 3
hours before shooting so that their makeup and costumes can be put on
-- this requires the use of a green room. Also, they cannot leave the
studio premises without taking off their makeup and costumes, which would
then require another 3 hours to be replaced. So if there are less than
3 hours before their next scheduled shoot, the actors have to be either on
stage, or in a green room.

Now, Maker and Breaker are creating tomorrow's schedule in the
following way. The studio is open between 8 AM and 8 PM, so there are
12 hour-long time slots. Maker and Breaker take turns assigning movies
to the time slot of their choice. Maker, being the senior scheduler,
is authorized to schedule all 4 movies, while Breaker, being the
trainee, is only authorized to schedule the two low-budget
movies. Now, Breaker really wants to do a good job and avoid any
scheduling disasters. But Maker is feeling resentful of the studio
(her pay was recently cut in order to accomodate this new trainee) and
wants to cause them trouble, so she is trying to create a scheduling
disaster (either putting one movie on the main set for 4 hours, or
requiring too many green rooms), which will be a headache for the
studio to handle.

The question is: Who wins?

We can find out as follows:

with(combinat):
Maker := Player({1,2,3,4}, {[1,1,1,1], [2,2,2,2], [3,3,3,3],
[4,4,4,4]} union permute(4)):
Breaker := Player({1,2}, {}):

AnalyzeGame({1,2,3,4}, B, Maker, Breaker, 12);
# (if Maker goes first)
AnalyzeGame({1,2,3,4}, B, Breaker, Maker, 12);
# (if Breaker goes first)

* Generalizations

I would like to investigate more games. One possibility is to have
Maker-Maker games, in which both players are trying to make different
sets of patterns. Another is to have Maker-Breaker games with scoring,
where Maker gets 1 point for every time one of the desired patterns
occurs in the final position. Then, to balance the game, we can
require Maker to score some predetermined number of points in order to
beat Breaker.

More elaborate scoring systems can also be devised. For example, some
patterns could be worth more than others, or the use of some letters
could cost points. However, once the games become this complex they
quickly move beyond the realm of analyzability. 

OVERVIEW OF PROGRESS

This project is incomplete. The things I would still like to do, in
approximate order of difficulty, are:

1. Redesign all functions to accomodate more general winning
   conditions and scoring functions, as described in the section
   "Generalizations".

2. Rewrite everything in C so that larger games can be analyzed. Maple
   is taking too long.

3. Find interesting sequence-coloring games.

4. Discover and implement an intelligent way to sort candidate moves
   for alpha-beta pruning, so that the best moves can be made
   first. This will allow larger games to be analyzed.

5. Discover heuristic "evaluation functions" for positions so that the
   game need not be completely solved. These could be invented "by
   hand" or automatically, and proved to be accurate by computers.

6. Investigate the relationship between the upper and lower
   threshold values and the probability of a forbidden pattern
   occuring in a random coloring.

7. Investigate the relationship between the Van der Waerden
   numbers and the upper threshold values. (This is probably very
   hard!)