\documentclass[11pt,twoside]{article} \usepackage{latex-macros/course}

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\begin{document} 
\inclassproblems{6M}


\begin{problem}\label{game}
We don't ordinarily run into games with an infinite number of possible
moves, but in this problem we'll look at one that is simple, kind of fun,
and informative.

The game is for two players who alternate moves.  A move consists of
choosing an integer point $(x,y)$ in the nonnegative quadrant of the
plane, \emph{subject to the constraint} that no move may be $\geq$ to any
previous move in \emph{both} coordinates.  The player who first lands at
the origin $(0,0)$ is the loser.

For example, the first player might choose the point $(1,3)$; the second
player could now move to any point in the L-shaped region left after
excluding the quadrant with lower-left corner $(1,3)$.  Suppose the second
player chooses the point $(4,2)$.  The first player can now move anywhere
in the $x=0$ column, anywhere in the $y=0$ and $y=1$ rows, and anywhere in
the rectangle with corners at the origin and $(3,2)$.  (Draw a picture!)

\bparts

\ppart \label{win} Find a winning strategy for the first player.

\solution{
The first player has two winning strategies:

{\bf Strategy 1:} If the first player starts with $(1,1)$ then
whatever the second player picks, either $(0,n)$ or $(n,0)$ for some
$n$, the first player will respond with, respectively, $(n,0)$ or
$(0,n)$.  By symmetry, the first player will always have a valid move
whenever the second player had a move, except when the second player
picks $(0,0)$ and loses.


{\bf Strategy 2:} The second winning strategy is slightly more tricky:
The first player starts by picking $(2,0)$,\footnote{Of course,
picking $(0,2)$ would be equivalent, and the following argument will
hold for it as well, with x and y coordinates replaced} and then:
\begin{itemize}
\item
If the 2nd player picks $(0,n)$ for any $n\geq{1}$, 1st player responds with
$(1,n-1)$.
\item
If the 2nd player picks $(1,n)$ for any $n\geq{0}$, 1st player
responds with $(0,n+1)$.
\end{itemize}
And the above procedure should be repeated for all consecutive moves.
Notice that if player 2 had a valid move, so does player 1, unless
player 2 picked $(0,0)$ and lost.

Furthermore, there are no other winning strategies for player 1,
because if she starts with any other legal move, player 2 will be able
to adopt either of the two winning strategies and win for sure:
\begin{itemize}
\item
If player 1 picks some $(m,n)$ where $m,n\geq{1}$ and
$(m,n)\neq(1,1)$, then player 2 can pick $(1,1)$ next, and then use
the first strategy to win against player 1.
\item
If player 1 picks some $(0,n)$ or $(n,0)$ where $n\geq{3}$, then
player 2 can respectively pick $(0,2)$ or $(2,0)$ next, and then use
the second strategy to win against player 1.
\item
If player 1 picks $(1,0)$ or $(0,1)$ then player 2 picks the other one
and wins.
\end{itemize}
}

\ppart The winning strategy ensures any game must end with a win for the
first player.  Can the first player guarantee a bound on the number of
steps before she wins?

\solution{No.  The solution to part~\ref{win} shows that neither possible
winning strategy guarantees such a bound.}

\eparts

Of course if neither player has figured out a winning strategy, it's
harder to predict how a game might go.  It might even seem possible that a
game could continue indefinitely without anyone ever being forced to move
to the origin.  But in fact it is not possible.  Namely, we will see that
the game \emph{must} terminate, even if the two players conspire to play
as long as possible.  The proof involves a generalization of the technique
of proving process termination with a strictly decreasing natural-number
valued variable.

\medskip

At any point during play, the state of the game can be represented by the
set of moves made so far and the number of the player (one or two) who
moves next.  Given the state, a valid move $(a,b)$ is said to be
\emph{bounded} iff both $a$ is bounded above by the $x$-coordinate of some
previous move and $b$ is bounded above by the $y$-coordinate of some
previous move.

For example, if the previous moves have been $(1,3),(3,1), (2,2)$, then
there are ten possible bounded moves:
$\set{(1,2),(2,1),(1,1),(0,3),(0,2),(0,1),(0,0),(1,0),(2,0),(3,0)}$.
There is also an infinite number of possible unbounded moves at this
point, namely, any move in the $x=0$ row or the $y=0$ column.

For any state, $S$, let $v(S)$ be the sum of the minimum of the
$x$-coordinate and minimum $y$-coordinate among the previous moves, and
let $b(S)$ be the number of possible bounded moves.  Define the
\emph{measure}, $M(S)$, of the state to be the pair $(v(S), b(S))$.

\begin{problemparts}

\ppart  Explain why the number of bounded moves is finite at any point in
the game.  Is the number of bounded moves a weakly decreasing variable?
weakly increasing?  Explain.

\solution{To start, there aren't any bounded moves.  After that, the
number of bounded moves is at most the minimum of the $x$-coordinates of
the previous moves times the minimum of the $y$-coordinates.

The number of bounded moves is neither weakly deceasing nor weakly
increasing.  It will increase if next move has larger $x$-coordinate but
smaller $y$-coordinate than any previous move.  It will decrease if the
next move is bounded.}

\problempart Show that $v$ is a weakly decreasing variable.

\solution{The \emph{minimum} $x$-coordinate among the moves can never
increase because of another move; likewise for the minimum $y$-coordinate.
So their sum cannot increase either.}

\problempart
Define $\prec$ to be the \emph{lexicographical} ordering on pairs of
natural numbers:
\[(m,k) < (m',k') \iff [(m < m') \lor (m = m' \land k < k')\]

Prove that $\prec$ is a (nonreflexive) total order on
$\naturals^2$, and that any nonempty subset of $\naturals^2$ has a
$\prec$-least element.  (Lexicographic order is a \emph{well-order}.)

\solution{Let $S$ be some nonempty subset of $\naturals^2$.  Let $S_x
\eqdef \set{m \suchthat \exists n\ (m,n)\in S}$.  Then by the Least Number
Principle there is a smallest element $x_{min}$ in $S_x$.  Similarly,
$y_{min}$ be the least element in the $\set{n \suchthat (x_min,n) \in S}$

Then $(x_{min},y_{min})$ is the $\prec$-least element in $S$.}

\problempart Show that the measure $M$ is a strictly $\prec$-decreasing
state variable.  Conclude that the game will terminate, even if the
players conspire to play as long as possible.

\solution{
We first show that the measure $M(S)=(v(S),b(S))$ decreases with every
move according to the ordering in $\naturals^2$ defined above.

Suppose some move $(a,b)$ leads from a state $S$ to a state $S'$.  There
are three cases:

Case 1: $a >$ the maximum previous $x$-coordinate.  Since $(a,b)$ is a
valid move, $b$ must be less than the minimum previous $y$-coordinate.
So $v(S') < v(S)$ and therefore $M(S') \prec M(S)$.

Case 2: $b >$ the maximum previous $y$-coordinate.  Just like Case 1.

Case 3: Otherwise, $(a,b)$ is, by definition, a bounded point.  Since the
maximum $x$- and $y$-coordinates are unchanged, the set of bounded moves
in $S'$ is a subset of the bounded moves in $S$, and is a proper subset,
since it no longer includes $(a,b)$.  So $b(S') < b(S)$, and since $v$ is
nondecreasing, we conclude that $M(S') \prec M(S)$.

So in every case, $M$ decreases.

Now among the set of all states in a game, there must be a must be a
$\prec$-least state, since it is a well-order.  Since any move would
decrease the measure of this state, it must be a final state of the game.
}
\end{problemparts}

\end{problem}

\begin{problem}

Many two-person games in which players alternate moves---like chess,
checkers, and tic-tac-toe---can be represented abstractly by \emph{game
trees}.

The root of a game tree has children labeled with each of the possible
initial moves by the first player.  For example, in the game tree for
tic-tac-toe, the root has nine children corresponding to the nine
boxes that the first player could mark with an~X.  Each of these
nodes has eight children corresponding to the eight remaining boxes
which the second player could mark with an~O, and so on.

In general, each node corresponds to a situation in the game, and its
children correspond to each of the possible moves by the player whose
turn it is in that situation.  The leaves of the tree correspond to
situations where no moves are possible---the game is over.  The leaves
are labelled with \emph{win}, \emph{lose}, or \emph{draw}, indicating
the outcome for the first player.  (A win for one player is a loss for
the other---no ``everybody wins''-type games at MIT. \texttt{:-)})

A \emph{strategy} for a player in a game specifies which move the player
should make in any situation where it is that player's turn to move.  A
\emph{winning} stategy ensures that the player will win no matter what
moves the other player makes.  Similarly, a \emph{non-losing} stategy
ensures that the player will \emph{win or draw} no matter what moves the
other player makes.

For example, most elementary school children figure out non-losing
strategies in tic-tac-toe for \emph{both} the first and second players.
There is no winning strategy in tic-tac-toe for either player.  No one
knows if any player has a winning strategy for chess or checkers.
However, on general principles, we can be sure that at least one player
has a non-losing strategy.

We want our games to terminate with a definite outcome---they cannot go on
forever.  These are called \emph{terminating games}.  For example, chess
and checkers are terminating games because of a rule that the game is a
draw if the same board position repeats too many times.

So game trees for terminating games are exactly the \emph{finite-path
trees} with leaves $\set{\emph{win}, \emph{lose}, or \emph{draw}}$.

Prove by structural induction on the definition of finite-path trees that
for \emph{any} two-person terminating game, at least one of the players
has a non-losing strategy.

\solution{
\begin{proof}
The proof is by structural induction on the game tree.
Let $P(T)$ be the proposition that for a game tree, $T$, at least one
of the players has a non-losing strategy.

{\bf Base case:}
For the base case of a single-node tree, the node is labeled \emph{win},
\emph{lose}, or \emph{draw}.  If the node is labeled \emph{win} or
\emph{draw}, then the first player has a non-losing strategy.  If
the node is labeled \emph{draw} or \emph{lose}, then the second
player has a non-losing strategy.  In both cases, there is a player with
a non-losing strategy.

{\bf Structural Induction Step:} In the inductive step, we want to prove
that for any game tree, $T$, if $P(T')$ holds for each immediate
subgame, $T'$, of $T$, then $P(T)$ holds.

So suppose $T$ is a game tree and there is a non-losing strategy for at
least one of the players for every immediate subgame, $T'$, of $T$.

Let $A$ be the player who moves first in the game defined by $T$, and
let $B$ be the player who moves second.  If player $B$ has a non-losing
strategy for \emph{every} subgame, $T'$, of $T$, then $B$ also has a
non-losing strategy for the full game tree $T$: no matter what move
player $A$ makes, player $B$ simply follows his non-losing strategy for
the immediate subgame determined by $A$'s move.

On the other hand, suppose there is some immediate subgame, $T_0$, of
$T$, for which player $B$ does not have a non-losing strategy.  
Since, by induction hypothesis, \emph{some} player has a non-losing
strategy for $T_0$, it must be player $A$ that the non-losing strategy
for this subgame.  But then player $A$ has a non-losing strategy for the
full game tree $T$: namely, make the move that leads to subgame $T_0$
and then pursue the non-losing strategy for that subgame.

In either case, at least one of the players has a non-losing strategy.
This completes the proof of the induction step, and thus the whole proof
by structural induction.

We conclude that $P(T)$ holds for all games trees, $T$.
\end{proof}
}

\end{problem}

\end{document}
