%\chapter{Appendices}
\addcontentsline{toc}{chapter}{Appendices}

\appendix

%\begin{small}
\twocolumn
\chapter{A Strategy}
\label{chap:atree}

The following \texttt{dot} file 
%(\texttt{5inputfeasfavstrat.dot}) 
was used to prepare 
Figure \ref{fig:atree}.
Every game state node is labelled with the move sets by the two players.
Every edge between game state nodes is labelled with a move, response pair.

\begin{scriptsize}
\verbatiminput{5inputfeasfavstrat.dot}
\end{scriptsize}

This strategy is special. It can be converted into Boolean formulas (using
our conversion method) that can then be ``simplified'' or ``manipulated''
into formulas that have conjunctions with no more than five literals.
The result of this conversion process (expressed in PLA form) 
is the following set of formulas.

\begin{scriptsize}
\verbatiminput{5inputfeasfavstrat.pla}
\end{scriptsize}

\onecolumn

While the PLA-form fully describes a set of formulas, there are more readable
formats. What follows is the formulas expressed in C.

\begin{scriptsize}
\verbatiminput{5inputfeasfavstrat.c}
\end{scriptsize}

The formulas can also be expressed in mathematical terms as follows.

\input{5inputfeasfavstrat.tex}

\chapter{Our Tools, Their Locations, and Their Uses}
\label{chap:tools}

All of the tools described in this thesis may be found on the author's home
page\footnote{\texttt{http://www.cs.unm.edu/\~{}bandrews/thesis-research}}, 
as well as on the CD-ROM that contains the complete thesis.

\section{\texttt{Stratgen}}

\texttt{Stratgen} is our strategy generation toolset. 
There are actually four tools in the family:
\begin{itemize}
\item \texttt{treegen} - generates strategy trees for the game of tic-tac-toe
\item \texttt{favgen} - generates favorable strategy trees for the game of tic-tac-toe
\item \texttt{feasgen} - generates feasible strategy trees for the game of tic-tac-toe
\item \texttt{feasfavgen} - generates feasible, favorable strategy trees for the game of tic-tac-toe
\end{itemize}

\subsection{Usage and Output}

Running any one of these tools with no arguments will result in a ``usage''
message. 
All of these tools take one command line parameter.
The tools when run with an integer parameter $i$ will produce strategies until
they have produced $i$ strategies.

All of the strategy generation tools are set up to produce strategies as
\texttt{Minimo} input files.
The tools print their output to stdout.

%It is possible to change the output format of any or all of the tools by
%changing compile-time flags. 
%Details about this functionality may be found in the Makefile.

\section{\texttt{Stratcounter}}

\texttt{Stratcounter} is our toolset for counting the number of 
strategies for the game of tic-tac-toe.
From one \texttt{C} file, we produce four executables:
\begin{itemize}
\item \texttt{counter} - counts the number of tic-tac-toe strategies after a given starting move
\item \texttt{counter-debug} - counts the number of tic-tac-toe strategies after a given starting move and prints debugging information
\item \texttt{favcounter} - counts the number of favorable tic-tac-toe strategies after a given starting move
\item \texttt{favcounter-debug} - counts the number of favorable tic-tac-toe strategies after a given starting move and prints debugging information
\end{itemize}

\subsection{Usage and Output}

Running any of the executables with no arguments produces no results.
Running the executables with an argument between zero and eight calculates and
prints to stdout the desired number. 
In the case of the ``-debug'' variations, 
there will be some amount of extra calculations printed.

\section{\texttt{Checker}}

\texttt{Checker} is our strategy-checking tool. 
After a formula is converted to PLA-form, it is compiled into this tool.
This tool plays out all the possible games against a strategy.

\subsection{Usage and Output}

This tool must be recompiled for every strategy to be checked.
Once compiled, it is run with ``\texttt{./cheat-checker}''.
If the strategy being checked is a valid strategy, then the tool will print
a \texttt{dot} representation of the strategy to stdout.
If the strategy is not a valid strategy, then the tool prints debugging
information to stdout.

\section{\texttt{CandBuild}}

\texttt{CandBuild} builds candidate conjunctions for technology mapping.
The easiest way to use this tool is to build candidates lists recursively.
First, generate the list of candidates that fit the desired shape that have
one literal.
Next, generate the list of candidates that fit the desired shape that have
two literals and append this to the list of candidates with one literal.
Using this method, you are assured to have a list of candidates with
increasing numbers of literals.

\subsection{Usage and Output}

Running ``java CandBuild'' produces a candidates file that can be used with
\texttt{Minimo}.

\section{\texttt{Minimo}}

\texttt{Minimo} is our Boolean formula mapping tool.

\subsection{Usage}

\texttt{Minimo} requires two input files in order to run:
a file containing strategies (in PLA form), and a file containing
candidate conjunction shapes.
If the candidates list is ordered by increasing numbers of literals,
then the output from Minimo is guaranteed to produce the minimal 
representation within the candidates list.

\subsection{Output}

\texttt{Minimo} is constantly trying to map strategies to the candidates.
The output from \texttt{Minimo} is somewhat sporadic.
As it attempts to map strategies to candidates, it prints the generated
formula disjuncts until the tool fails to match for the strategy.
If and when the word ``found'' is printed, then the tool has found a mapping,
and the formulas printed just before the ``found'' represent that set of
formulas.

The output formulas are printed in \texttt{C}. 
They are written in such a way that they can compile with the \texttt{checker}
tool.

%\section{File Formats}

%\subsubsection{Strategy Tree Output Formats}

%A strategy tree for the game of tic-tac-toe can be represented in several
%ways: graphically, as a set of Boolean formulas (feasible strategies), 
%and as an input to Minimo.
%Our strategy generation software can print strategies for any of these
%representational styles.
%Specifically, the tool can generate a dot file that can be used to produce
%a graphical representation of the strategy.
%When used to produce a set of Boolean formulas,
%the output is designed to fit into our checker program.
%This output builds C code that represents the formulas as variables being
%assigned values according to inputs in a DNF formula.

\section{\texttt{Minimo} Strategy Input File}

A \texttt{Minimo} strategy input file 
contains some number of strategies expressed as Boolean
formulas (with a blank line separating two strategies). 
Every line in a strategy must contain the same number of characters.
Every line begins with some number of zeroes and ones representing
an input vector.
The input vector is followed by a single space and an output vector.
An output vector 
%is comprised of 
consists of
the characters zero, one, and hyphen
(representing that an input vector is in the DON'T CARE-set of a particular
function).

A \texttt{Minimo} candidates input file contains some number of lines, 
each representing
a possible disjunct to be considered for covering a function.
Every line must contain the same number of characters.
Every line is composed of some number of zeroes, ones, and hyphens.
A hyphen as the $i$th character in a line indicates that the $i$th input
does not appear in that conjunction.

\chapter{Computing Values For $f$}
\label{chap:f}

%The printed version of this thesis document omits Sections C.1, C.2, and C.3.
%They can be found on the enclosed CD-ROM or on the author's web 
%page\footnote{\texttt{http://www.cs.unm.edu/\~{}bandrews/thesis-research}}.

The following was stated in Section \ref{sec:numofstrat}:
\begin{eqnarray*}
f([\ ], [\ ]) &\approx& (1.90478 \cdot 10^{123} \cdot 4) + 
                          (7.45027 \cdot 10^{122} \cdot 4) + 
		          (3.6333 \cdot 10^{123})\\
		&\approx& 1.4233 \cdot 10^{124}.
\end{eqnarray*}
This chapter is meant to provide a demonstration of how this figure was
derived. From Section \ref{sec:numofstrat}, we know that 
$ f([\ ], [\ ]) = \sum_{i = 0}^{8} f([\ ], [i]).$
Surely the number of strategies that begin with a move in one of the 
``corner'' positions on the board should not depend on \emph{which} corner
the move is in.
Similarly, the number of strategies that begin with a move in one of the 
``side'' positions should be equal to the number of strategies that begin 
in any of the other side positions.
With this in mind, we only really need to perform three computations to 
compute $f([\ ], [\ ])$.
Specifically, we need to compute 
$f([\ ], [0])$, $f([\ ], [1])$, and $f([\ ], [4])$.

\newpage

\section{Computing the Value of $f([\ ], [0])$}
\begin{scriptsize}
\input{fzero}
\end{scriptsize}

\section{Computing the Value of $f([\ ], [1])$}
\begin{scriptsize}
\input{fone}
\end{scriptsize}

\section{Computing the Value of $f([\ ], [4])$}
\begin{scriptsize}
\input{ffour}
\end{scriptsize}

\chapter{Computing Values For $g$}
\label{chap:g}

%The printed version of this thesis document omits Sections D.1, D.2, and D.3.
%They can be found on the enclosed CD-ROM or on the author's web 
%page\footnote{\texttt{http://www.cs.unm.edu/\~{}bandrews/thesis-research}}.

Similarly, we will demonstrate the derivation of the function $g$.

\newpage

\section{Computing the Value of $g([\ ], [0])$}
\begin{scriptsize}
\input{gzero}
\end{scriptsize}

\section{Computing the Value of $g([\ ], [1])$}
\begin{scriptsize}
\input{gone}
\end{scriptsize}

\section{Computing the Value of $g([\ ], [4])$}
\begin{scriptsize}
\input{gfour}
\end{scriptsize}

%\end{small}