\chapter{Introduction}

\label{chap:introduction}

Computer science has always been about revolutionary ideas. Alan Turing
modeled his first ideas of computers around his understanding of the 
process behind the work of mathematicians (infinite time and tape) 
\cite{Turing1936}. 
More
recently Adleman demonstrated a technique of computation that solves any
instance of an NP-hard problem in linear time (if you set enough chemicals up
first)
\cite{Adleman1994}. 
Some might say that this is a form of 
``brute-forcing'' the solution.

This complaint of ``brute force'' could certainly not be made if instead
of encoding the edges of the graph 
into strands of DNA (as Adleman did \cite{Adleman1994})
someone had encoded
a machine of simple Boolean logic gates to solve the same problem. 
And that
is the jumping-off point of this work. 
%In 
%\cite{Stojanovic2001A, Stojanovic2002, Stojanovic2003TicTacToe},
%a chemical computation paradigm is put forth that simulates
%Boolean logic at the individual gate level (meaning the Boolean logic gates
%are what is actually synthesized). 
A chemical computation paradigm has been introduced that simulates
Boolean logic at the individual gate level (meaning the Boolean logic gates
are what is actually synthesized) 
\cite{Stojanovic2001A, Stojanovic2002, Stojanovic2003TicTacToe}.
%With this new paradigm comes very little in the way of 
%attention-grabbing applications. 
%This work aims to correct
%this defect in two ways. 
We will explore what we can do with this new
technology (what limits must be placed on the Boolean functions to be
simulated) and describe research into a field of possible applications:
automata that play games.

\section{Research Progression}

Some time ago we set out to expand on the results printed in the MAYA paper 
\cite{Stojanovic2003TicTacToe}. 
MAYA is a tic-tac-toe playing automaton that begins the game by playing
in the center square and allows its opponent to play only in the 
top-left corner
or left-center position after the first move.
We wanted to demonstrate a complete strategy for the game of tic-tac-toe. 
In order to do this we needed to understand 
%the intricacies of 
how the chemical computation paradigm represented Boolean functions. 
We knew that
the representation did not perfectly simulate Boolean functions. 
Specifically, there is no way to remove
inputs from solution, and there is no way to stop a vat from 
fluorescing.\footnote{These performance restrictions are a byproduct of the
closed systems the reactions currently operate in.}
In essence, we are dealing with ``monotonic'' Boolean functions. 
Once they evaluate to true, they will always ``report'' true.
This monotonicity actually served to help us as we defined a process for
converting strategies into correctly-functioning Boolean formulas.

%Generating strategies for tic-tac-toe that can then be 
%simulated
%using our chemical computation paradigm is not too straightforward a task.
Generating strategies for tic-tac-toe that can 
%then be 
subsequently be 
converted into correctly-functioning Boolean formulas
%using our chemical computation paradigm 
is not too straightforward a task.
A strategy is correct if it simply makes proper moves. 
At the beginning
of this work it was unknown what constraints needed to be applied to
strategies to allow them to be represented correctly by Boolean formulas.
This thesis
describes the refinement process we went through in order to correctly
define the criteria for a strategy that was a candidate for this conversion
process.
This strategy-theoretic knowledge is discussed before
its application to the game of tic-tac-toe.

Once a strategy has been generated and it has been converted into disjunctive
normal form (DNF) Boolean formulas, each of its 
disjuncts  %checked June 12
must be mapped to gates that can be represented in the chemistry. 
Because of the scope of our problems, it became clear that we should develop
a special-purpose Boolean formula manipulation program.

Thus, our approach was the following:
We wrote programs to generate strategies for the game of tic-tac-toe. 
We went on to write programs to generate Boolean formulas from the 
strategies.\footnote{In order to do this properly,
we had to develop a method for doing this for strategies not just for the
game of tic-tac-toe but for any game.}
Next, we wrote programs to check those strategies. 
Finally, we needed to tackle the problem of 
attempting to fit formulas 
to the current technological constraints of the chemical 
computation paradigm.


%\section{Some Progressions and Interactions}
%\label{sec:intro:interactions}

%In some ways, this research was conducted from the top down.
%We began with an idea of how we wanted the chemicals to represent the Boolean
%formulas and an idea of how we wanted to convert a strategy into 
%Boolean formulas.
%We did not know, however if these ideas would be sufficient for a strategy 
%of any non-trivial complexity. %replaced (vague)
%with more than two or three moves in sequence.

\section{Representing Boolean Formulas in Chemistry}
\label{sec:intro:boolchem}

As previously stated, our chemical computation paradigm is capable of
simulating logic gates up to a certain point.
In its current (closed-system) form, the paradigm has some limitations.
The ``computation'' is performed in a vat or test tube.
The computation begins when the molecules representing the logic gates are
added to the solution in the vat.
After the gates are added, the chemicals representing the inputs to the gates
may be added.
The molecules representing the gates fluoresce when they are activated.
This corresponds to the gate reporting that it has evaluated to true.

Let us say that we have a system in which we are representing the Boolean
formula $y = a \lor (b \land c)$.
We 
%would 
represent this formula in a vat with two kinds of gate molecules.
The first kind of gate molecule 
%might 
will fluoresce in the presence of the
molecule representing $a$ while the second 
%might 
will fluoresce in the presence
of the molecules representing $b$ and $c$.
An input to the formula is considered to have a value of true if its
corresponding input molecule has been added to the vat.
The chemical computation paradigm will correctly represent the formula so long
as the inputs to the formula ($a$, $b$, and $c$) make state changes only
from false to true.
Once the chemical representing $a$ has been added to the vat, it can not be
removed.

A vat will represent a Boolean formula in disjunctive normal form.
Each gate molecule will ``work'' independently.
As a consequence, only one kind of gate molecule in a certain vat need
fluoresce for the entire vat to fluoresce.
Each gate molecule, then, will be representing a conjunction of inputs.
The presence of more than one type of gate molecule in a vat will result
in the implicit ``OR''-ing of the values of the gates.

\section{Representing Game Strategies with Boolean Formulas}
\label{sec:intro:stratbool}

This work began with a predefined idea of how we wanted to represent a
strategy using Boolean formulas.
This work did not begin, however, knowing whether or not this representation
(and the implicit conversion) would be able to 
provide enough freedom to represent a game strategy 
%of any non-trivial complexity. %replaced (vague)
with more than two or three moves in sequence.

The chemical logic gates will represent a strategy's play.
The inputs to those logic gates will represent the 
%strategy's 
opponent's play.
From here on, we will refer to these two players as ``the strategy''
(or ``automaton'') and ``the opponent'' (or ``the human'').
A formula will represent a field of the game board.
If the formula evaluates to true then the strategy wishes to play in that field.
When the human wishes to play in a field $X$, the human 
sets the variable representing that field to true.
Again, this corresponds to adding a chemical
representing the input field $X$ to all\footnote{
Adding the chemical input to all of the vats changes the make-up of
all of the vats. After any move by the opponent, all of the vats have a chance
to respond to a change in their chemical make-up. We could add the chemical
representing input field $x$ to only the vat that we are expecting to be the
automaton's next play, but this would presuppose that we know what the 
automaton's next play is going to be.}
of the vats.

\section{A Final Introductory Word}

This work has a practical application in the laboratory. While most of the
work is idealized, 
we would like to be able to perform experiments demonstrating our ideas. 
There are current technological limitations to
the sizes and shapes of the gates that can be simulated in the chemistry.
This affects the disjunct 
sizes (number of positive and negative literals) 
in the (DNF) Boolean formulas to be simulated.
After we have converted a strategy into a set of Boolean formulas, we will
attempt to find an equivalent representation of those formulas 
%in the set of formulas that 
using only such formulas as
can be simulated under the current technological limitations.

\section{Organization of the Thesis}

Chapter \ref{chap:background} 
%sets the stage by describing 
describes the setting
for the application of the end results of this work.
Chapter \ref{chap:strategy} formalizes the process of converting
strategy trees into Boolean formulas. 
Chapter \ref{chap:boolean} describes the development and
implementation of a special-purpose Boolean formula manipulator 
(\texttt{Minimo})
inspired by the algorithm used in the BOOM Boolean formula minimizer 
\cite{hlavicka01boom}.
Chapter \ref{chap:tictactoe} describes our application of this theory to
the game of tic-tac-toe.