\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}
\medskip
\medskip

\centerline{Due:  Beginning of class Wednesday, November 24}

{\bf Problem 1.} Consider a game with branching factor 2 and depth $d$
and where the max player moves first.
Note that there are $2^d$ leaf nodes.  Let $\delta$ be $\frac{1}{2^d}$.
Suppose that the leaf nodes are assigned the value $\delta$, $2\delta$, $3\delta$, $\ldots$ $2^d\delta=1$.
In the limit as $d \rightarrow \infty$ the min max value of trees of this
form approaches a certain value.  What is that value?  Explain your answer.
What would the limit be if the min player moved first?

{\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}$.  Now consider an $\alpha$-$\beta$ search in which the
best move is tried first at each ply and so that an optimal
$\alpha$-$\beta$ search tree is generated.  In a $d$-ply tree starting
at a max node how many leaf nodes will be examined?  Your answer
should be given in terms of the parameters $d$, $b\subbox{max}$, and
$b\subbox{min}$.

{\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$.  Assume that the max player moves {\em last}.
Let $P(1|\;d,\;b,\; P)$ be the probability that the root value is 1 given that
the max player moves {\em last}, the tree has depth $d$, the branching factor is $b$,
and the probability that a leaf has value 1 is $P$.  For any value of $P$
and $b$ one of the three following conditions hold.

$$\lim_{d\rightarrow \infty} P(1|\;d,\;b,\;P) = 1$$
$$\lim_{d\rightarrow \infty} P(1|\;d,\;b,\;P) = 0$$
$$0 < \lim_{d\rightarrow \infty} P(1|\;2d+1,\;b,\;P) < 1$$

Give conditions on $P$ and $b$ under which each of the above conditions
hold.  Note that in the third condition only odd values of $d$ are considered.
Hint:  Think about whether the probability of a min-max value of 1 at a max
node gets larger or smaller as one gets farther from the leaves.

{\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.

Construct a four ply game tree with branching factor 2 such that the
root node is a max node and every node has one child generated by a
capture move and one child generated by a noncapture move.  The root
value of the four ply tree has minmax value 0.
For each of the 16
leaf nodes indicate whether it is in the max defense for avoiding -1,
whether it is in the min defense for avoiding +1, and for those leaves
which are in one of these two defenses indicate its conspiracy depth
in each of the defenses that it belongs to.

\end{document}