\input psadobe
\documentstyle[12pt,epsf]{report}
\newcommand{\bigcenter}[1]{\begin{center} {\Large\bf #1} \end{center}}
\setlength{\oddsidemargin}{.25in}       
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}          
\setlength{\textheight}{8.5in}

\parskip=2ex

\parindent=0ex

\newcommand{\necpos}[1]{[\langle #1 \rangle]}

\input nofill.tex
\input texcom.tex

\begin{document}
\centerline{\bf \large 6.824 Artificial Intelligence, Fall 1993}
\centerline{\bf \large Problem Set 9 Solutions}
\medskip

{\bf Problem 1.} Consider a game with branching factor 2 and depth $d$
and where the max player moves first.
There are $2^d$ leaf nodes, with values $\delta$, $2\delta$, $3\delta$, $\ldots$ $2^d\delta=1$ assigned from left to right ($\delta=\frac{1}{2^d}$).

Because of the ordering of the leaves, whenever the max player moves, he
selects the right child (removing the left half of the remaining children), and 
whenever the min player moves, he selects the left child (removing the right
half of the remaining children.

In the limit as $d \rightarrow \infty$ the number of leaves approaches infinity
and the min max game essentially eliminates intervals in $[0,1]$.
If we want to find the value of the leaf we finally get to we can just
add up the size of the intervals removed by the max player.\\
at level 0 (root) an interval of size $\frac{1}{2}$ is removed\\
at level 1 the min player removes from the left, this has no effect\\
at level 2 an interval of size $\frac{1}{8}$ is removed\\
at level 3 no effect\\ 
at level 4 an interval of size $\frac{1}{32}$ is removed\\
and so on.

Summing up we get \\
$\frac{1}{2}+ \frac{1}{8}+\frac{1}{32}+\frac{1}{128}+\ldots = 
\frac{1}{2}(1+\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\ldots)= 
\frac{1}{2}\sum_{i=0}^{\infty}\frac{1}{4^i}= \frac{1}{2}\frac{1}{1-1/4}= \frac{2}{3}$

Similarly if the root is a min node we get\\
$\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\ldots = 
\frac{1}{4}(1+\frac{1}{4}+\frac{1}{16}+ \ldots)= 
\frac{1}{4}\sum_{i=0}^{\infty}\frac{1}{4^i}= \frac{1}{4}\frac{1}{1-1/4}= \frac{1}{3}$

{\bf Problem 2.} Consider a minmax game tree in which each max node has a branching
factor of $b\subbox{max}$ and each min node has a branching factor of
$b\subbox{min}$.  If an $\alpha$-$\beta$ search tries the best move first 
at each ply, an optimal
$\alpha$-$\beta$ search tree is generated.  This tree is the union of a min
and max strategy.  A min strategy is one where all $b\subbox{max}$ children of
the max nodes are traversed but only one child of every min node.  Since we are
only interested in the number of leaves of a $d$-ply tree we can collapse the
min strategy to a tree  with branching factor $b\subbox{max}$ of depth 
$\lfloor \frac{d+1}{2}\rfloor$ (the tree begins with a max node).  The number of 
leaves of this tree is $b\subbox{max}^{\lfloor \frac{d+1}{2}\rfloor}$.
Similar reasoning shows that the max stragety results in
$b\subbox{min}^{\lfloor \frac{d}{2}\rfloor}$ leaves.
Since there is one path in both the min and max strategies the total
number of leaves in the search tree is
$$b\subbox{min}^{\lfloor \frac{d}{2}\rfloor}+ b\subbox{max}^{\lfloor \frac{d+1}{2}\rfloor} -1$$

{\bf Problem 3.}  Consider a game tree with uniform branching factor
$b$ and depth $d$.  Suppose that each leaf is independendtly
assigned the value 1 or 0 where the probability of assigning a given
leaf the value 1 is $P$.  

At the leaves 
$$P(1|\;0,\;b,\; P) = P_0(1) = P$$
$$P(0|\;0,\;b,\; P) = P_0(0) = 1-P$$

Assuming that the max player moves {\em last} at the next level
$$P(1|\;1,\;b,\; P) = P_1(1) = 1- (1-P)^b$$
$$P(0|\;1,\;b,\; P) = P_1(0) = (1-P)^b$$

Continuing up the tree we get the following recurrences:
\begin{itemize}
\item at a MAX node
$$P(1|\;2d+1,\;b,\; P) = P_{2d+1}(1) = 1- (1-P_{2d}(1))^b$$
$$P(0|\;2d+1,\;b,\; P) = P_{2d+1}(0) = (1-P_{2d}(1))^b$$

\item at a MIN node
$$P(1|\;2d,\;b,\; P) = P_{2d}(1) = P_{2d-1}(1)^b$$
$$P(0|\;2d,\;b,\; P) = P_{2d}(0) = 1- P_{2d-1}(1)^b$$
\end{itemize}
Note that at a max node $P_{2d+1}(1)$ is the probability of a max victory and
$P_{2d+1}(0)$ is the probability of a min victory.  similarly at a min node
$P_{2d}(1)$ is the probability of a min victory, and $P_{2d}(0)$ is the 
probability of a max victory.

The values $P(1|\;d,\;b,\; P)$ up the tree either increase, decrease or
stay the same.  I conjecture that if the probability increases then
the probability that the root has value 1, $P(1|\;d,\;b,\; P)$, goes to
$1$ in the limit as $d$ goes to infinity.   
If the probability decreases then
$P(1|\;d,\;b,\; P)$ goes to
$0$, 
otherwise the probability remains constant throughout the tree,
$P(1|\;2d+1,\;b,\; P) = 1-P$, and similarly $P(1|\;2d,\;b,\; P) =P$.

I will now prove this conjecture.  Namely I will show that the
only possible points of convergence of the recurrences above are in the
third condition, thus if the probabilities either increase or decrease 
they must converge to $1$ or $0$ respectively.

{\bf Claim} The equation $(1 - (1-x)^b)^b = x$ (the probabilities of a $1$ at
two nearest min nodes) has exactly three solutions.\\
proof:  
By graphing the two functions $f(x) = x$ and $g(x) = (1 - (1-x)^b)^b$ we can show that
these two functions have the same value in exactly three places. 
\epsfxsize 2in
\centerline{\epsffile{ps9-fig1.ps}}
From the derivatives of the function $g$ we know that it has the above
shape.
$$g^{\prime}(x) = b^2((1-x)(1 - (1-x)^b))^{b-1}$$
$$g^{\prime\prime}(x) = b^2(b-1)((1-x)(1 - (1-x)^b))^{b-2}((1-x)^b(1+b)-1)$$
The second derivative is $0$ at $x=0$, $x=1$, and $(1-x)^b(1+b) =1$ for 
$0 \leq x \leq 1$.

Furthermore, by examination of the recurrences above, the
probabilities of the value 1 going up the tree remain constant at the
following values of $P$ and $b$ $P = 0$, $P= 1$, and $P = (1-P)^b$.
(The last solution corresponds to a min win at a leaf and a node at
the next level, $P_{0}(1) = P_{1}(0)$.)\\

To summarize:
\begin{itemize}
\item if $(1-P)^b < P$ or $P=1$ then
$$\lim_{d\rightarrow \infty} P(1|\;d,\;b,\;P) = 1$$
\item if $(1-P)^b > P$ or $P=0$ then
$$\lim_{d\rightarrow \infty} P(1|\;d,\;b,\;P) = 0$$
\item if $(1-P)^b = P$ then
$$\lim_{d\rightarrow \infty} P(1|\;2d+1,\;b,\;P) = 1- P$$
\end{itemize}

{\bf Problem 4.} Consider a game tree in which each node is associated
with a static value.  For any node $n$ we let $s(n)$ denote the static
value of $n$.  We consider a game where at any max position $n$ with
child $m$ we have that $s(m)$ is either $s(n)$ or $s(n)+1$.  If $s(m)$
is $s(n)+1$ then we say that the child node $m$ is {\em generated by a
capture move} from the max position $n$.  The dual conditions apply at
min nodes --- if $n$ is a min node and $m$ is a child of $n$ then
$s(m)$ is either $s(n)$ or $s(n)-1$ and in the latter case we say that
the child $m$ is generated by a capture move from the min node $n$.
Children other than those generated by capture moves will be said to
be generated by noncapture moves.

The following tree has branching factor $2$ and begins with a max node.
The static values are calculated as above with capture moves drawn to
the right.  The $\alpha-\beta$ values are then computed bottom up.
The leaves in the min and max defenses and their conspiracy depth are
computed as in notes.

\epsfxsize 5in
\centerline{\epsffile{ps9-fig2.ps}}

\end{document}