\documentstyle[jair,twoside,11pt,theapa]{article}

\newtheorem{theorem}{Theorem}[subsection]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{procedure}[theorem]{Procedure}
\newtheorem{conjecture}[theorem]{Conjecture}
%\input{elart}
%\input{tlart}
\newcommand{\secn}[1]{Section~\ref{s.#1}}
\newcommand{\fig}[1]{Figure~\ref{f.#1}}
\newcommand{\defn}[1]{Definition~\ref{d.#1}}
\newcommand{\thm}[1]{Theorem~\ref{t.#1}}
\newcommand{\prop}[1]{Proposition~\ref{p.#1}}
\newcommand{\lem}[1]{Lemma~\ref{l.#1}}
\newcommand{\cor}[1]{Corollary~\ref{c.#1}}
\newcommand{\alg}[1]{Algorithm~\ref{a.#1}}
\newcommand{\proc}[1]{Procedure~\ref{p.#1}}
\newcommand{\eq}[1]{(\ref{e.#1})}

\newcommand{\type}[1]{\mbox{\tt #1}}
\def\set#1{\{#1\}}
\def\proofend{\mbox{\nobreak\qquad\square}}
\def\square{\framebox[6pt]{\hspace{6pt}}}
\def \proof{\noindent{\bf Proof.}\enspace}
\def\powset{{\cal P}}
\def\R{\rlap{\rm I}\,{\rm R}}
\newcommand{\cirl}{{\sc cirl}}
\newcommand{\Cirl}{{\sc Cirl}}
\def\emptyset{{\hbox{\rm \O}}}

\jairheading{14}{2001}{303--358}{10/00}{6/01}
\ShortHeadings{GIB: Imperfect information in a computationally challenging game}
{Ginsberg}
\firstpageno{303}


\begin{document}

\title{GIB: Imperfect Information in a Computationally Challenging Game}

\author{\name Matthew L.~Ginsberg \email ginsberg@cirl.uoregon.edu \\
       \addr CIRL \\ 1269 University of Oregon \\ Eugene, OR  97405 USA}


\newcommand{\gib}{{\sc gib}}
\newcommand{\Gib}{{\sc Gib}}
\newcommand{\rcps}{{\sc rcps}}
\newcommand{\swo}{{\sc swo}}
\newcommand{\Rcps}{{\sc Rcps}}
\newcommand{\Swo}{{\sc Swo}}
\newcommand{\acbl}{{\sc acbl}}
\newcommand{\imps}{{\sc imp}s}
\newcommand{\imp}{{\sc imp}}
\newcommand{\sd}{$\spadesuit$}
\newcommand{\hs}{$\heartsuit$}
\newcommand{\di}{$\diamondsuit$}
\newcommand{\cl}{$\clubsuit$}
\newcommand{\bdd}{{\sc bdd}}

\newcommand{\ab}{$\alpha$-$\beta$ pruning}
\newcommand{\abc}{\alpha\beta}
\newcommand{\new}[1]{#1_{\mbox{\scriptsize new}}}
\newcommand{\best}[1]{#1_{\mbox{\scriptsize best}}}
\newcommand{\all}[1]{#1_{\mbox{\scriptsize all}}}
\newcommand{\ans}[1]{#1_{\mbox{\scriptsize ans}}}
\newcommand{\win}[1]{#1_{\mbox{\scriptsize win}}}
\newcommand{\minimax}{\type{minimax}}
\newcommand{\pair}[1]{\langle #1\rangle}
\newcommand{\ev}{\type{ev}}
\newcommand{\evc}{\type{ev}_c}
\newcommand{\tmax}{\type{max}}
\newcommand{\tmin}{\type{min}}

\newcommand{\tictac}[9]{\footnotesize\setlength{\arrayrulewidth}{.8pt}
\addtolength{\arraycolsep}{-2pt}\begin{array}{c|c|c}
\bf #1 & \bf #2 & \bf #3 \\
\hline
\bf #4 & \bf #5 & \bf #6 \\
\hline
\bf #7 & \bf #8 & \bf #9
 \end{array}}

\maketitle

\begin{abstract} 
  This paper investigates the problems arising in the construction of
  a program to play the game of contract bridge.  These problems
  include both the difficulty of solving the game's perfect
  information variant, and techniques needed to address the fact that
  bridge is not, in fact, a perfect information game.  \Gib, the
  program being described, involves five separate technical advances:
  partition search, the practical application of Monte Carlo
  techniques to realistic problems, a focus on achievable sets to
  solve problems inherent in the Monte Carlo approach, an extension of
  alpha-beta pruning from total orders to arbitrary distributive
  lattices, and the use of squeaky wheel optimization to find
  approximately optimal solutions to cardplay problems.
  
  \Gib\ is currently believed to be of approximately expert caliber,
  and is currently the strongest computer bridge program in the world.

\end{abstract}

\section{Introduction}

Of all the classic games of mental skill, only card games and Go have
yet to see the appearance of serious computer challengers.  In Go,
this appears to be because the game is fundamentally one of pattern
recognition as opposed to search; the brute-force techniques that have
been so successful in the development of chess-playing programs have
failed almost utterly to deal with Go's huge branching factor.
Indeed, the arguably strongest Go program in the world (Handtalk) was
beaten by 1-dan Janice Kim (winner of the 1984 Fuji Women's
Championship) in the 1997 AAAI Hall of Champions after Kim had given
the program a monumental 25 stone handicap.

Card games appear to be different.  Perhaps because they are games of
imperfect information, or perhaps for other reasons, existing poker
and bridge programs are extremely weak.  World poker champion Howard
Lederer (Texas Hold'em, 1996) has said that he would expect to beat
any existing poker program after five minutes'
play.$^\dag$\footnote{Many of the citations here are the results of
personal communications.  Such communications are indicated simply by
the presence of a $^\dag$ in the accompanying text.}  Perennial world
bridge champion Bob Hamman, seven-time winner of the Bermuda Bowl,
summarized the state of bridge programs in 1994 by saying that, ``They
would have to improve to be hopeless.''$^\dag$

In poker, there is reason for optimism: the {\sc gala} system
\cite{Koller:poker}, if applicable, promises to produce a computer
player of unprecedented strength by reducing the poker ``problem'' to
a large linear optimization problem which is then solved to generate a
strategy that is nearly optimal in a game-theoretic sense.  Schaeffer,
author of the world champion checkers program {\sc Chinook}
\cite{Schaeffer:jump}, is also reporting significant success in the
poker domain \cite{Schaeffer:poker}.

The situation in bridge has been bleaker.  In addition, because the
American Contract Bridge League (\acbl) does not rank the bulk of its
players in meaningful ways, it is difficult to compare the strengths
of competing programs or players.

In general, performance at bridge is measured by playing the same deal
twice or more, with the cards held by one pair of players being given
to another pair during the replay and the results then being
compared.\footnote{The rules of bridge are summarized in Appendix
\ref{a.rules}.}  A ``team'' in a bridge match thus typically
consists of two pairs, with one pair playing the North/South (N/S)
cards at one table and the other pair playing the E/W cards at the
other table.  The results obtained by the two pairs are added; if the
sum is positive, the team wins this particular deal and if negative,
they lose it.

In general, the numeric sum of the results obtained by the two pairs
is converted to International Match Points, or \imps.  The purpose of
the conversion is to diminish the impact of single deals on the total,
lest an abnormal result on one particular deal have an unduly large
impact on the result of an entire match.

Jeff Goldsmith$^\dag$ reports that the standard deviation on a single
deal in bridge is about 5.5 \imps, so that if two roughly equal pairs
were to play the deal, it would not be surprising if one team beat the
other by about this amount.  It also appears that the difference
between an average club player and an expert is about 1.5 \imps\ (per
deal played); the strongest players in the world are approximately 0.5
\imps/deal better still.  Excepting \gib, the strongest bridge playing
programs appear to be slightly weaker than average club players.

Progress in computer bridge has been slow.  An incorporation of
planning techniques into Bridge Baron, for example, appears to have
led to a performance increment of approximately 1/3 \imp\ per deal
\cite{Nau:bridge}.  This modest improvement still leaves Bridge Baron
far shy of expert-level (or even good amateur-level) performance.

Prior to 1997, bridge programs generally attempted to duplicate human
bridge-playing methodology in that they proceeded by attempting to
recognize the class into which any particular deal fell: finesse, end
play, squeeze, etc.  Smith et~al.'s work on the Bridge Baron program
uses planning to extend this approach, but the plans continue to be
constructed from human bridge techniques.  Nygate and Sterling's early
work on {\sc python} \cite{Nygate:python} produced an expert system
that could recognize squeezes but not prepare for them.  In
retrospect, perhaps we should have expected this approach to have
limited success; certainly chess-playing programs that have attempted
to mimic human methodology, such as {\sc paradise}
\cite{Wilkins:paradise}, have fared poorly.

\Gib, introduced in 1998, works differently.  Instead of modeling its
play on techniques used by humans, \gib\ uses brute-force search to
analyze the situation in which it finds itself.  A variety of
techniques are then used to suggest plays based on the results of the
brute-force search.  This technique has been so successful that all
competitive bridge programs have switched from a knowledge-based
approach to a search-based approach.

GIB's cardplay based on brute-force techniques was at the expert level
(see \secn{monte}) even without some of the extensions that we discuss
in \secn{achieve} and subsequently.  The weakest part of \gib's game
is bidding, where it relies on a large database of rules describing
the meanings of various auctions.  Quantitative comparisons here are
difficult, although the general impression of the stronger players
using GIB are that its overall play is comparable to that of a human
expert.

This paper describes the various techniques that have been used in the
\gib\ project, as follows:

\begin{enumerate}
  
\item \Gib's analysis in both bidding and cardplay rests on an ability
  to analyze bridge's perfect-information variant, where all of the
  cards are visible and each side attempts to take as many tricks as
  possible (this perfect-information variant is generally referred to
  as {\em double dummy\/} bridge).  Double dummy problems are solved
  using a technique known as {\em partition search\/}, which is
  discussed in \secn{partition}.
  
\item Early versions of \gib\ used {\em Monte Carlo methods\/}
  exclusively to select an action based on the double dummy analysis.
  This technique was originally proposed for cardplay by Levy
  \cite{Levy:MonteCarlo}, but was not implemented in a performance
  program before \gib.  Extending Levy's suggestion, \gib\ uses Monte
  Carlo simulation for both cardplay (discussed in \secn{monte}) and
  bidding (discussed in \secn{bidding}).
  
\item \secn{achieve} discusses difficulties with the Monte Carlo
  approach.  Frank et~al.~have suggested dealing with these problems
  by searching the space of possible plans for playing a particular
  bridge deal, but their methods appear to be intractable in both
  theory and practice \cite{Frank:bridge,Frank:bridge2}.  We instead
  choose to deal with the difficulties by modifying our understanding
  of the game so that the value of a bridge deal is not an integer
  (the number of tricks that can be taken) but is instead taken from a
  distributive lattice.
  
\item In \secn{alpha}, we show that the alpha-beta pruning mechanism
  can be extended to deal with games of this type.  This allows us to
  find optimal plans for playing bridge end positions involving some
  32 cards or fewer.  (In contrast, Frank's method is capable only of
  finding solutions in 16 card endings.)

\item Finally, applying our ideas to the play of full deals (52 cards)
requires solving an approximate version of the overall problem.  In
\secn{swo}, we describe the nature of the approximation used and our
application of {\em squeaky wheel optimization\/}
\cite{Joslin:squeak} to solve it.

\end{enumerate} 
Concluding remarks are contained in \secn{conclude}.

\section{Partition search}
\label{s.partition}

Computers are effective game players only to the extent that
brute-force search can overcome innate stupidity; most of their time
spent searching is spent examining moves that a human player would
discard as obviously without merit.

As an example, suppose that White has a forced win in a particular
chess position, perhaps beginning with an attack on Black's queen.  A
human analyzing the position will see that if Black doesn't respond to
the attack, he will lose his queen; the analysis considers places to
which the queen could move and appropriate responses to each.

A machine considers responses to the queen moves as well, of course.
But it must also analyze in detail every {\em other\/} Black move,
carefully demonstrating that each of these other moves can be refuted
by capturing the Black queen.  A six-ply search will have to analyze
every one of these moves five further ply, even if the refutations are
identical in all cases.  Conventional pruning techniques cannot help
here; using \ab, for example, the entire ``main line'' (White's
winning choices and all of Black's losing responses) must be analyzed
even though there is a great deal of apparent redundancy in this
analysis.\footnote{An informal solution to this is Adelson-Velskiy
et~al.'s {\em method of analogies\/}~\cite{AV:chess}.  This approach
appears to have been of little use in practice because it is
restricted to a specific class of situations arising in chess games.}

In other search problems, techniques based on the ideas of dependency
maintenance~\cite{Sussman:ddb} can potentially be used to overcome
this sort of difficulty.  As an example, consider chronological
backtracking applied to a map coloring problem.  When a dead end is
reached and the search backs up, no information is cached and the
effect is to eliminate only the specific dead end that was
encountered.  Recording information giving the reason for the failure
can make the search substantially more efficient.

In attempting to color a map with only three colors, for example,
thirty countries may have been colored while the detected
contradiction involves only five.  By recording the contradiction for
those five countries, dead ends that fail for the same reason can be
avoided.

Dependency-based methods have been of limited use in practice because
of the overhead involved in constructing and using the collection of
accumulated reasons. This problem has been substantially addressed in
the work on dynamic backtracking \cite{Ginsberg:dynamic} and its
successors such as {\sc relsat} \cite{Bayardo:relsat}, where
polynomial limits are placed on the number of nogoods being
maintained.  

In game search, however, most algorithms already include significant
cached information in the form of a transposition table
\cite{Greenblatt:transpose,Marsland:transpose}.  A transposition table
stores a single game position and the backed up value that has been
associated with it.  The name reflects the fact that many games
``transpose'' in that identical positions can be reached by swapping
the order in which moves are made.  The transposition table eliminates
the need to recompute values for positions that have already been
analyzed.

These collected observations lead naturally to the idea that
transposition tables should store not single positions and their
values, but {\em sets\/} of positions and their values.  Continuing
the dependency-maintenance analogy, a transposition table storing sets
of positions can prune the subsequent search far more efficiently than
a table that stores only singletons.

There are two reasons that this approach works.  The first, which we
have already mentioned, is that most game-playing programs already
maintain transposition tables, thereby incurring the bulk of the
computational expense involved in storing such tables in a more
general form.  The second and more fundamental reason is that when a
game ends with one player the winner, the reason for the victory is
generally a local one.  A chess game can be thought of as ending when
one side has its king captured (a completely local phenomenon); a
checkers game, when one side runs out of moves.  Even if an internal
search node is evaluated before the game ends, the reason for
assigning it any specific value is likely to be independent of some
global features (e.g., is the Black pawn on $a5$ or $a6$?).  Partition
search exploits both the existence of transposition tables and the
locality of evaluation for realistic games.

This section explains these ideas via an example and then describes
them formally.  Experimental results for bridge are also presented.

\subsection{An example}
\label{s.example}

\begin{figure}
\begin{center}
\setlength{\unitlength}{.8in}
\begin{picture}(3,2.25)
\thicklines
\multiput(0,.3)(1,0)4{\line(0,1){.4}}
\put(.2,1.3){\line(5,2){1}}
\put(1,1.3){\line(1,1){.4}}
\put(1.6,1.7){\line(1,-1){.4}}
\put(1.8,1.7){\line(5,-2){1}}
\put(0,0){\makebox(0,0){$\tictac XXXOO\ O\ X$}}
\put(1,0){\makebox(0,0){$\tictac XXXO\ \ OOX$}}
\put(2,0){\makebox(0,0){$\tictac XXXO\ OO\ X$}}
\put(3,0){\makebox(0,0){$\tictac XXOOX\ O\ X$}}
\put(0,1){\makebox(0,0){$\tictac XX\ OO\ O\ X$}}
\put(1,1){\makebox(0,0){$\tictac XX\ O\ \ OOX$}}
\put(2,1){\makebox(0,0){$\tictac XX\ O\ OO\ X$}}
\put(3,1){\makebox(0,0){$\tictac XXOO\ \ O\ X$}}
\put(1.5,2){\makebox(0,0){$\tictac XX\ O\ \ O\ X$}}
\put(2.5,2){\makebox(0,0){O moves}}
 \end{picture}
\end{center}
\caption{A portion of the game tree for tic-tac-toe}
\label{f.ex}
\end{figure}    

Our illustrative examples for partition search will be taken from the
game of tic-tac-toe.  A portion of the game tree for this game appears
in \fig{ex}, where we are analyzing a position that is a win for X.
We show O's four possible moves, and a winning response for X in each
case.  Although X frequently wins by making a row across the top of
the diagram, \ab\ cannot reduce the size of this tree because O's
losing options must all be analyzed separately.

Consider now the position at the lower left in the diagram, where X
has won:
 \begin{equation}
\tictac XXXOO\ O\ X
 \label{e.specific}
 \end{equation}
 The reason that X has won is local.  If we are retaining a list of
positions with known outcomes, the entry we can make because of this
position is:
 \begin{equation}
\tictac XXX??????
 \label{e.general}
 \end{equation}
 where the ?~means that it is irrelevant whether the associated square
is marked with an X, an O, or unmarked.  This table entry corresponds
not to a single position, but to approximately $3^6$ because the
unassigned squares can contain X's, O's, or be blank.  We can reduce
the game tree in \fig{ex} to:

\begin{center}
\setlength{\unitlength}{.8in}
\begin{picture}(3,2.25)
\thicklines
\multiput(1,.3)(2,0)2{\line(0,1){.4}}
\put(.3,.7){\line(1,-1){.4}}
\put(1.3,.3){\line(1,1){.4}}
\put(.2,1.3){\line(5,2){1}}
\put(1,1.3){\line(1,1){.4}}
\put(1.6,1.7){\line(1,-1){.4}}
\put(1.8,1.7){\line(5,-2){1}}
\put(1,0){\makebox(0,0){$\tictac XXX??????$}}
\put(3,0){\makebox(0,0){$\tictac XXOOX\ O\ X$}}
\put(0,1){\makebox(0,0){$\tictac XX\ OO\ O\ X$}}
\put(1,1){\makebox(0,0){$\tictac XX\ O\ \ OOX$}}
\put(2,1){\makebox(0,0){$\tictac XX\ O\ OO\ X$}}
\put(3,1){\makebox(0,0){$\tictac XXOO\ \ O\ X$}}
\put(1.5,2){\makebox(0,0){$\tictac XX\ O\ \ O\ X$}}
\put(2.5,2){\makebox(0,0){O moves}}
 \end{picture}
\end{center}

Continuing the analysis, it is clear that the position
 \begin{equation}
\tictac XX\ ??????
 \label{e.inverse}
 \end{equation}
 is a win for X if X is on play.\footnote{We assume that O has not
already won the game here, since X would not be ``on play'' if the
game were over.}  So is
 \[\tictac X???\ ???X\]
 and the tree can be reduced to:

\begin{center}
\setlength{\unitlength}{.8in}
\begin{picture}(3,2.5)(0,-.25)
\thicklines
\multiput(.6,.3)(1.8,0)2{\line(0,1){.4}}
\put(.6,1.3){\line(2,1){.8}}
\put(1.6,1.7){\line(2,-1){.8}}
\put(.6,0){\makebox(0,0){$\tictac XXX??????$}}
\put(2.4,0){\makebox(0,0){$\tictac X???X???X$}}
\put(.6,1){\makebox(0,0){$\tictac XX\ ??????$}}
\put(2.4,1){\makebox(0,0){$\tictac X???\ ???X$}}
\put(1.5,2){\makebox(0,0){$\tictac XX\ O\ \ O\ X$}}
\put(2.5,2){\makebox(0,0){O moves}}
 \end{picture}
\end{center}

Finally, consider the position
 \begin{equation}
\tictac XX\ ?\ \ ??X
 \label{e.reduce}
 \end{equation}
 where it is O's turn as opposed to X's.  If O moves in the second
row, we get an instance of 
 \[\tictac XX\ ??????\]
 while if O moves to the upper right, we get an instance of
 \[\tictac X???\ ???X\]
 Thus every one of O's moves leads to a position that is known to be a
 win for X, and we can conclude that the original position \eq{reduce}
 is a win for X as well.  The root node in the reduced tree can
 therefore be replaced with the position of \eq{reduce}.

These positions capture the essence of the algorithm we will propose:
If player $x$ can move to a position that is a member of a set known
to be a win for $x$, the given position is a win as well.  If every
move is to a position that is a loss, the original position is also.

\subsection{Formalizing partition search}
\label{s.existing}

In this section, we present a summary of existing methods for
evaluating positions in game trees.  There is nothing new here; our
aim is simply to develop a precise framework in which our new results
can be presented.

\begin{definition} An {\em interval-valued game\/} is a quadruple
  $(G,p_I,s,\ev$), where $G$ is a finite set of legal positions,
  $p_I\in G$ is the initial position, $s:G\rightarrow 2^G$ gives the
  immediate successors of a given position, and $\ev$ is an evaluation
  function
 \[\ev: G \rightarrow \set{\tmax,\tmin}\cup [0,1]\]
 Informally, $p'\in s(p)$ means that position $p'$ can be reached from
 $p$ in a single move, and the evaluation function $\ev$ labels internal
 nodes based upon whose turn it is to play ($\tmax$ or $\tmin$) and
 values terminal
 positions in terms of some element of the unit interval $[0,1]$.
 
 The structures $G$, $p_I$, $s$ and $\ev$ are
 required to satisfy the following conditions:

\begin{enumerate}

\item There is no sequence of positions $p_0,\dots,p_n$ with $n>0$,
$p_i \in s(p_{i-1})$ for each $i$ and $p_n = p_0$.  In other words,
there are no ``loops'' that return to an identical position.

\item $\ev(p)\in[0,1]$ if and only if $s(p) = \emptyset$.  In other
words, $\ev$ assigns a numerical value to $p$ if and only if the game
is over.  Informally, $\ev(p)=\tmax$ means that the maximizer is to
play and $\ev(p)=\tmin$ means that the minimizer is to play.
 \end{enumerate}
 \label{d.game}
 \end{definition}

We use $2^G$ to denote the power set of $G$, the set of subsets of
$G$.  There are two further things to note about this definition.

First, the requirement that the game have no ``loops'' is consistent
with all modern games.  In chess, for example, positions can repeat
but there is a concealed counter that draws the game if either a
single position repeats three times or a certain number of moves pass
without a capture or a pawn move.  In fact, dealing with the hidden
counter is more natural in a partition search setting than a
conventional one, since the evaluation function is in general
(although not always) independent of the value of the counter.

Second, the range of \ev\ includes the entire unit interval $[0,1]$.
The value 0 represents a win for the minimizer, and 1 a win for the
maximizer.  The intermediate values might correspond to intermediate
results (e.g., a draw) or, more importantly, allow us to deal with
internal search nodes that are being treated as terminal and assigned
approximate values because no time remains for additional search.

The evaluation function \ev\ can be used to assign numerical values to
the entire set $G$ of positions:

\begin{definition} Given an interval-valued game $(G,p_I,s,\ev$), we
introduce a function $\evc: G \rightarrow [0,1]$ defined recursively
by
 \[\evc(p) = \cases{\ev(p), & if $\ev(p)\in[0,1]$;\cr
                \max_{p'\in s(p)} \evc(p'), & if $\ev(p)=\tmax$; \cr
                \min_{p'\in s(p)} \evc(p'), & if $\ev(p)=\tmin$.}\]
 The {\em value\/} of $(G,p_I,s,\ev$) is defined to be $\evc(p_I)$.
 \end{definition}

To evaluate a position in a game, we can use the well-known {\em
minimax\/} procedure:

 \vbox{\begin{algorithm}{\bf(Minimax)} {\em For a game $(G,p_I,s,\ev$)
and a position $p\in G$, to compute $\evc(p)$:
 \begin{tabbing}
{\bf if} \=$\ev(p)\in[0,1]$ {\bf return} $\ev(p)$ \\
{\bf if} $\ev(p) = \tmax$
 {\bf return} $\max_{p'\in s(p)} \minimax(p')$ \\
{\bf if} $\ev(p) = \tmin$
 {\bf return} $\min_{p'\in s(p)} \minimax(p')$
 \end{tabbing}}
 \label{a.minimax}
 \end{algorithm}}

There are two ways in which the above algorithm is typically extended.
The first involves the introduction of transposition tables; we will
assume that a new entry is added to the transposition table $T$
whenever one is computed.  (A modification to cache only selected
results is straightforward.)  The second involves the introduction of
\ab.  Incorporating these ideas gives us the algorithm at the top of
the next page.

Each entry in the transposition table consists of a position $p$, the
current cutoffs $[x,y]$, and the computed value $v$.  Note the need to
include information about the cutoffs in the transposition table
itself, since the validity of any particular entry depends on the
cutoffs in question.

As an example, suppose that the value of some node is in fact 1 (a win
for the maximizer) but that when the node is evaluated with cutoffs of
$[0,0.5]$ a value of 0.5 is returned (indicating a draw) because the
maximizer has an obviously drawing line.  It is clear that this value
is only accurate for the given cutoffs; wider cutoffs will lead to a
different answer.

In general, the upper cutoff $y$ is the currently smallest value
assigned to a minimizing node; the minimizer can do at least this well
in that he can force a value of $y$ or lower.  Similarly, $x$ is the
currently greatest value assigned to a maximizing node.  These cutoff
values are updated as the algorithm is invoked recursively in the
lines responsible for setting $\new v$, the value assigned to a child
of the current position $p$.

\begin{proposition} Suppose that $v=\abc(p,[x,y])$ for each entry
$(p,[x,y],v)$ in $T$.  Then if $\evc(p)\in[x,y]$, the value returned
by \alg{abt} is $\evc(p)$.\proofend
 \end{proposition}
 \clearpage

\vbox{\begin{algorithm}{\bf(\ab\ with transposition tables)} {\em
Given an interval-valued game $(G,p_I,s,\ev)$, a position $p\in G$,
cutoffs $[x,y]\subseteq[0,1]$ and a transposition table $T$ consisting
of triples $(p,[a,b],v)$ with $p\in G$ and $a\leq b,v\in [0,1]$, to
compute $\abc(p,[x,y])$:
 \begin{tabbing}
{\bf if} there is an entry $(p,[x,y],z)$ in $T$ {\bf return} $z$\\
{\bf if} \=$\ev(p)\in[0,1]$ {\bf then} $\ans v = \ev(p)$\\
{\bf if} \=$\ev(p) = \tmax$ {\bf then} \\
\> $\ans v := 0$ \\
\> {\bf for} \=each $p'\in s(p)$ {\bf do} \\
\> \> $\new v = \abc(p',[\max(\ans v,x),y])$ \\
\> \> {\bf if} \=$\new v\geq y$ {\bf then} \\
\> \> \> $T := T \cup (p,[x,y],\new v)$ \\
\> \> \> {\bf return} $\new v$\\
 \> \> {\bf if} \=$\new v > \ans v$ {\bf then} 
 $\ans v = \new v$ \\
 {\bf if} \=$\ev(p) = \tmin$ {\bf then} \\
 \> $\ans v := 1$ \\
 \> {\bf for} \=each $p'\in s(p)$ {\bf do} \\
 \> \> $\new v = \abc(p',[x,\min(\ans v,y)])$ \\
 \> \> {\bf if} \=$\new v\leq x$ {\bf then} \\
\> \> \> $T := T \cup (p,[x,y],\new v)$ \\
\> \> \> {\bf return} $\new v$\\
 \> \> {\bf if} \=$\new v < \ans v$ {\bf then} 
 $\ans v = \new v$ \\
 $T := T \cup (p,[x,y],\ans v)$ \\
 {\bf return} $\ans v$ \\
 \end{tabbing}}
 \label{a.abt}
 \end{algorithm}}

\subsection{Partitions}
\label{s.formal}

We are now in a position to present our new ideas.  We begin by
formalizing the idea of a position that can reach a known winning
position or one that can reach only known losing ones.

\begin{definition} Given an interval-valued game $(G,p_I,s,\ev$) and a
set of positions $S\subseteq G$, we will say that the {\em set of
positions that can\/} {\bf reach} $S$ is the set of all $p$ for which
$s(p) \cap S\neq \emptyset$.  This set will be denoted $R_0(S)$.  The
{\em set of positions\/} {\bf constrained} {\em to reach $S$\/} is the
set of all $p$ for which $s(p)\subseteq S$, and is denoted $C_0(S)$.
\end{definition}
 
These definitions should match our intuition; the set of positions
that can reach a set $S$ is indeed the set of positions $p$ for which
some element of $S$ is an immediate successor of $p$, so that
$s(p)\cap S\neq\emptyset$.  Similarly, a position $p$ is constrained
to reach $S$ if {\em every\/} immediate successor of $p$ is in $S$, so
that $s(p)\subseteq S$.

Unfortunately, it may not be feasible to construct the $R_0$ and $C_0$
operators explicitly; there may be no concise representation of the
set of all positions that can reach $S$.  In practice, this will be
reflected in the fact that the data structures being used to describe
the set $S$ may not conveniently describe the set $R_0(S)$ of all
situations from which $S$ can be reached.  

Now suppose that we are expanding the search tree itself, and we find
ourselves analyzing a particular position $p$ that is determined to be
a win for the maximizer because the maximizer can move from $p$ to the
winning set $S$; in other words, $p$ is a win because it is in
$R_0(S)$.  We would like to record at this point that the set $R_0(S)$
is a win for the maximizer, but may not be able to construct or
represent this set conveniently.  We will therefore assume that we
have some computationally effective way to approximate the $R_0$ and
$C_0$ functions, in that we have (for example) a function $R$ that is
a conservative implementation of $R_0$ in that if $R$ says we can
reach $S$, then so we can:
 \[R(p,S) \subseteq R_0(S)\]
 
$R(p,S)$ is intended to represent a set of positions that are ``like
$p$ in that they can reach the (winning) set $S$.''  Note the inclusion
of $p$ as an argument to $R(p,S)$, since we certainly want $p\in R(p,S)$.
We are about to cache the fact that every element of $R(p,S)$ is a win
for the maximizer, and certainly want that information to include the
fact that $p$ itself has been shown to be a win.  Thus we require
$p\in R(p,S)$ as well.

Finally, we need some way to generalize the information returned by
the evaluation function; if the evaluation function itself identifies
a position $p$ as a win for the maximizer, we want to have some way to
generalize this to a wider set of positions that are also wins.  We
formalize this by assuming that we have some generalization function
$P$ that ``respects'' the evaluation function in the sense that the
value returned by $P$ is a set of positions that $\ev$ evaluates
identically.

\begin{definition} Let $(G,p_I,S,\ev)$ be an interval-valued game.
Let $f$ be any function with range $2^G$, so that $f$ selects a set of
positions based on its arguments.  We will say that $f$ {\em
respects\/} the evaluation function $\ev$ if whenever $p,p'\in F$ for
any $F$ in the range of $f$, $\ev(p) = \ev(p')$.

A {\em partition system\/} for the game is a triple $(P,R,C)$ of
functions that respect $\ev$ such that:

\begin{enumerate}

\item $P:G\rightarrow 2^G$ maps positions into sets of positions such
that for any position $p$, $p\in P(p)$.

\item $R:G \times 2^G \rightarrow 2^G$ accepts as arguments a position
$p$ and a set of positions $S$.  If $p\in R_0(S)$, so that $p$ can
reach $S$, then $p\in R(p,S) \subseteq R_0(S)$.

\item $C:G \times 2^G \rightarrow 2^G$ accepts as arguments a position
$p$ and a set of positions $S$.  If $p\in C_0(S)$, so that $p$ is
constrained to reach $S$, then $p\in C(p,S) \subseteq C_0(S)$.

\end{enumerate}

\label{d.approx}
\end{definition}

As mentioned above, the function $P$ tells us which positions are
sufficiently ``like'' $p$ that they evaluate to the same value.  In
tic-tac-toe, for example, the position \eq{specific} where X has won
with a row across the top might be generalized by $P$ to the set of
positions
 \begin{equation}
\tictac XXX??????
 \label{e.general2}
 \end{equation}
as in \eq{general}.

The functions $R$ and $C$ approximate $R_0$ and $C_0$.  Once again
turning to our tic-tac-toe example, suppose that we take $S$ to be the
set of positions appearing in \eq{general2} and that $p$ is given by
 \[\tictac XX\ OO\ O\ X\]
 so that $S$ can be reached from $p$.  $R(p,S)$ might be
 \begin{equation}
\tictac XX\ ??????
 \label{e.inverse1}
 \end{equation}
 as in \eq{inverse}, although we could also take $R(p,S) = \set p$ or
$R(p,S)$ to be
 \[{\tictac XX\ OO\ O\ X} \cup {\tictac \ XX??????} \cup {\tictac X\ X??????}\]
 although this last union might be awkward to represent.  Note again that
$R$ and $C$ are functions of $p$ as well as $S$; the set returned must
include the given position $p$ but can otherwise be expected to vary
as $p$ does.

\begin{figure}
\begin{algorithm}{\bf(Partition search)} {\em Given a game
$(G,p_I,s,\ev)$ and $(P,R,C)$ a partition system for it, a position
$p\in G$, cutoffs $[x,y]\subseteq[0,1]$ and a transposition table $T$
consisting of triples $(S,[a,b],v)$ with $S\subseteq G$ and
$a \leq b,v\in [0,1]$, to compute $\abc(p,[x,y])$:
 \begin{tabbing}
{\bf if} there is an entry $(S,[x,y],z)$ with $p\in S$ 
  {\bf return} $\pair{z,S}$\\
{\bf if} \=$\ev(p)\in[0,1]$ {\bf then}
 $\pair{\ans v,\ans S} = \pair{\ev(p),P(p)}$\\
{\bf if} \=$\ev(p) = \tmax$ {\bf then} \\
\> $\ans v := 0$ \\
\> $\all S := \emptyset$ \\
\> {\bf for} \=each $p'\in s(p)$ {\bf do} \\
\> \> $\pair{\new v,\new S} = \abc(p',[\max(\ans v,x),y])$ \\
\> \> {\bf if} \=$\new v\geq y$ {\bf then} \\
\> \> \> $T := T \cup (\new S,[x,y],\new v)$ \\
\> \> \> {\bf return} $\pair{\new v,\new S}$ \\
\> \> {\bf if} \=$\new v > \ans v$ {\bf then} 
 $\pair{\ans v,\ans S} = \pair{\new v, \new S}$ \\
\> \> $\all S := \all S \cup \new S$ \\
\> {\bf if} \=$\ans v = 0$ {\bf then}
 $\ans S = C(p,\all S)$ \hspace*{.82in} $\dag$ \\
\> {\bf else}
 $\ans S = R(p,\ans S) \cap C(p,\all S)$ \hspace*{.8in} $\dag\quad \ddag$\\
{\bf if} \=$\ev(p) = \tmin$ {\bf then} \\
\> $\ans v := 1$ \\
\> $\all S := \emptyset$ \\
\> {\bf for} \=each $p'\in s(p)$ {\bf do} \\
\> \> $\pair{\new v,\new S} = \abc(p',[x,\min(\ans v,y)])$ \\
\> \> {\bf if} \=$\new v\leq x$ {\bf then} \\
\> \> \> $T := T \cup (\new S,[x,y],\new v)$ \\
\> \> \> {\bf return} $\pair{\new v,\new S}$ \\
\> \> {\bf if} \=$\new v < \ans v$ {\bf then} 
 $\pair{\ans v,\ans S} = \pair{\new v, \new S}$ \\
\> \> $\all S := \all S \cup \new S$ \\
\> {\bf if} \=$\ans v = 1$ {\bf then}
 $\ans S = C(p,\all S)$ \\
\> {\bf else}
 $\ans S = R(p,\ans S) \cap C(p,\all S)$ \hspace*{.8in} $\ddag$\\
$T := T \cup (\ans S,[x,y],\ans v)$ \\
{\bf return} $\pair{\ans v,\ans S}$ \\
 \end{tabbing}}
\vspace*{-.3in}
 \label{a.ps}
 \end{algorithm}
 \label{f.alg}
 \caption{The partition search algorithm}
 \label{f.ps}
 \end{figure}

We will now modify \alg{abt} so that the transposition table, instead
of caching results for single positions, caches results for sets of
positions.  As discussed in the introduction to this section, this
is an analog to the introduction of truth maintenance techniques into
adversary search.  The modified algorithm \ref{a.ps} appears in
\fig{ps} and returns a pair of values -- the value for the given
position, and a set of positions that will take the same value.

\begin{proposition} Suppose that $v=\abc(p,[x,y])$ for every
$(S,[x,y],v)$ in $T$ and $p\in S$.  Then if $\evc(p)\in[x,y]$, the
value returned by \alg{ps} is $\evc(p)$.
 \end{proposition}

\proof  We need to show that when the algorithm returns, any position
in $\ans S$ will have the value $\ans v$.  This will ensure that the
transposition table remains correct.

To see this, suppose that the node being expanded is a maximizing
node; the minimizing case is dual.  Suppose first that this node is a
loss for the maximizer, having value 0.

In showing that the node is a loss, we will have examined successor
nodes that are in sets denoted $\new S$ in \alg{ps}; if the maximizer
subsequently finds himself in a position from which he has no moves
outside of the various $\new S$, he will still be in a losing
position.  Since $\all S = \cup \new S$, the maximizer will lose in
any position from which he is constrained to next move into an element
of $\all S$.  Since every position in $C(p,\all S)$ has this property,
it is safe to take $\ans S = C(p,\all S)$.  This is what is done in
the first line with a dagger in the algorithm.

The more interesting case is where the eventual value of the node is
nonzero; now in order for another node $n$ to demonstrably have the
same value, the maximizer must have no new options at $n$, and must
still have some move that achieves the value $\ans v$ at $n$.

The first condition is identical to the earlier case where $\ans v=0$.
For the second, note that any time the maximizer finds a new best
move, we set $\ans S$ to the set of positions that we know recursively
achieve the same value.  When we complete the maximizer's loop in the
algorithm, it follows that $\ans S$ will be a set of positions from
which the maximizer can indeed achieve the value $\ans v$.  Thus the
maximizer can also achieve that value from any position in $R(p,\ans
S)$.  It follows that the overall set of positions known to have the
value $\ans v$ is given by $R(p,\ans S) \cap C(p,\all S)$, intersecting
the two conditions of this paragraph.  This is what is done in the
second daggered step in the algorithm.  \proofend

\subsection{Zero-window variations}
\label{s.zero}

The effectiveness of partition search depends crucially on the size of
the sets maintained in the transposition table.  If the sets are
large, many positions will be evaluated by lookup.  If the sets are
small, partition search collapses to conventional \ab.

An examination of \alg{ps} suggests that the points in the algorithm
at which the sets are reduced the most are those marked with a {\em
  double\/} dagger in the description, where an intersection is
required because we need to ensure both that the player can make a
move equivalent to his best one {\em and\/} that there are no other
options.  The effectiveness of the method would be improved if this
possibility were removed.

To see how to do this, suppose for a moment that the evaluation
function always returned 0 or 1, as opposed to intermediate values.
Now if the maximizer is on play and the value $\new v =1$, a prune
will be generated because there can be no better value found for the
maximizer.  If all of the $\new v$ are 0, then $\ans v=0$ and we can
avoid the troublesome intersection.  The maximizer loses and there is
no ``best'' move that we have to worry about making.
 
In reality, the restriction to values of 0 or 1 is unrealistic.  Some
games, such as bridge, allow more than two outcomes, while others
cannot be analyzed to termination and need to rely on evaluation
functions that return approximate values for internal nodes.  We can
deal with these situations using a technique known as {\em zero-window
search} (originally called {\em scout\/} search \cite{Pearl:scout}).
To evaluate a specific position, one first estimates the value to be
$e$ and then determines whether the actual value is above or below $e$
by treating any value $v>e$ as a win for the maximizer and any value
$v\leq e$ as a win for the minimizer.  The results of this calculation
can then be used to refine the guess, and the process is repeated.  If
no initial estimate is available, a binary search can be used to find
the value to within any desired tolerance.

Zero-window search is effective because little time is wasted on
iterations where the estimate is wildly inaccurate; there will
typically be many lines showing that a new estimate is needed.  Most
of the time is spent on the last iteration or two, developing tight
bounds on the position being considered.  There is an analog in
conventional \ab, where the bounds typically get tight quickly and the
bulk of the analysis deals with a situation where the value of the
original position is known to lie in a fairly narrow range.

In zero-window search, a node always evaluates to 0 or 1, since either
$v>e$ or $v\leq e$.  This allows a straightforward modification to
\alg{ps} that avoids the troublesome cases mentioned earlier.

\subsection{Experimental results}
\label{s.experiment}

Partition search was tested by analyzing 1000 randomly generated
bridge deals and comparing the number of nodes expanded using
partition search and conventional methods.  

In addition to our general interest in bridge, there are two reasons
why it can be expected that partition search will be useful for this
game.  First, partition search requires that the functions $R_0$ and
$C_0$ support a partition-like analysis; it must be the case that an
analysis of one situation will apply equally well to a variety of
similar ones.  Second, it must be possible to build approximating
functions $R$ and $C$ that are reasonably accurate representatives of
$R_0$ and $C_0$.

Bridge satisfies both of these properties.  Expert discussion of a
particular deal often will refer to small cards as $x$'s, indicating
that it is indeed the case that the exact ranks of these cards are
irrelevant.  Second, it is possible to ``back up'' $x$'s from one
position to its predecessors.  If, for example, one player plays a
club with no chance of having it impact the rest of the game, and by
doing so reaches a position in which subsequent analysis shows him to
have two small clubs, then he clearly must have had {\em three\/}
small clubs originally.  Finally, the fact that cards are simply being
replaced by $x$'s means that it is possible to construct data
structures for which the time per node expanded is virtually unchanged
from that using conventional methods.

Perhaps an example will make this clearer.  Consider the following
partial bridge deal in which East is to lead and there are no trumps:

\begin{center}
\begin{tabular}{lll}
&\hspace*{.06in} \sd\ --- \hspace*{.06in}& \\
&\hspace*{.06in} \hs\ --- \hspace*{.06in}& \\
&\hspace*{.06in} \di\ AK \hspace*{.06in}& \\
&\hspace*{.06in} \cl\ --- \hspace*{.06in}& \\
\cline{2-2}
\multicolumn 1{l|}{\sd\ 10\quad} && \multicolumn 1{|l}{\hspace*{.2in}\sd\ AQ}  \\
\multicolumn 1{l|}{\hs\ A\hspace*{.2in}} && \multicolumn 1{|l}{\hspace*{.2in}\hs\ ---}  \\
\multicolumn 1{l|}{\di\ ---\quad} && \multicolumn 1{|l}{\hspace*{.2in}\di\ ---}  \\
\multicolumn 1{l|}{\cl\ ---\quad} && \multicolumn 1{|l}{\hspace*{.2in}\cl\ ---}  \\
\cline{2-2}
&\hspace*{.06in} \sd\ KJ \hspace*{.06in} & \\
&\hspace*{.06in} \hs\ --- \hspace*{.06in} &\\
&\hspace*{.06in} \di\ --- \hspace*{.06in} & \\
&\hspace*{.06in} \cl\ --- \hspace*{.06in}&
\end{tabular}
\end{center}

An analysis of this situation shows that in the main line, the only
cards that win tricks by virtue of their ranks are the spade Ace, King
and Queen.  This sanctions the replacement of the above figure by the
following more general one:

\begin{center}
\begin{tabular}{lll}
&\hspace*{.06in} \sd\ --- \hspace*{.06in}& \\
&\hspace*{.06in} \hs\ --- \hspace*{.06in}& \\
&\hspace*{.06in} \di\ xx \hspace*{.06in}& \\
&\hspace*{.06in} \cl\ --- \hspace*{.06in}& \\
\cline{2-2}
\multicolumn 1{l|}{\sd\ x\quad} && \multicolumn 1{|l}{\hspace*{.2in}\sd\ AQ}  \\
\multicolumn 1{l|}{\hs\ x\hspace*{.2in}} && \multicolumn 1{|l}{\hspace*{.2in}\hs\ ---}  \\
\multicolumn 1{l|}{\di\ ---\quad} && \multicolumn 1{|l}{\hspace*{.2in}\di\ ---}  \\
\multicolumn 1{l|}{\cl\ ---\quad} && \multicolumn 1{|l}{\hspace*{.2in}\cl\ ---}  \\
\cline{2-2}
&\hspace*{.06in} \sd\ Kx \hspace*{.06in} & \\
&\hspace*{.06in} \hs\ --- \hspace*{.06in} &\\
&\hspace*{.06in} \di\ --- \hspace*{.06in} & \\
&\hspace*{.06in} \cl\ --- \hspace*{.06in}&
\end{tabular}
\end{center}

Note first that this replacement is {\em sound\/} in the sense that
every position that is an instance of the second diagram is {\em
  guaranteed\/} to have the same value as the original.  We have not
resorted to an informal argument of the form ``Jacks and lower tend
not to matter,'' but instead to a precise argument of the form, ``In
the expansion of the search tree associated with the given deal, Jacks
and lower were proven {\em never\/} to matter.''

Bridge also appears to be extremely well-suited (no pun intended) to
the kind of analysis that we have been describing; a chess analog
might involve describing a mating combination and saying that ``the
position of Black's queen didn't matter.''  While this does happen,
casual chess conversation is much less likely to include this sort of
remark than bridge conversation is likely to refer to a host of small
cards as $x$'s, suggesting at least that the partition technique is
more easily applied to bridge than to chess (or to other games).

That said, however, the results for bridge are striking, leading to
performance improvements of an order of magnitude or more on fairly
small search spaces (perhaps $10^6$ nodes).  The deals we tested
involved between 12 and 48 cards and were analyzed to termination, so
that the depth of the search varied from 12 to 48.  (The solver
without partition search was unable to solve larger problems.)  The
branching factor for minimax without transposition tables appeared to
be approximately 4, and the results appear in \fig{exp}.

\begin{figure}
\begin{center}
\input{pgraph}
\end{center}
\caption{Nodes expanded as a function of method}
\label{f.exp}
\end{figure}

Each point in the graph corresponds to a single deal.  The position of
the point on the $x$-axis indicates the number of nodes expanded using
\ab\ and transposition tables, and the position on the $y$-axis the
number expanded using partition search as well.  Both axes are plotted
logarithmically.

In both the partition and conventional cases, a binary zero-window
search was used to determine the exact value to be assigned to the
hand, which the rules of bridge constrain to range from 0 to the
number of tricks left (one quarter of the number of cards in play).
As mentioned previously, hands generated using a full deck of 52 cards
were not considered because the conventional method was in general
incapable of solving them.  The program was run on a Sparc 5 and
PowerMac 6100, where it expanded approximately 15K nodes/second.  The
transposition table shares common structure among different sets and
as a result, uses approximately 6 bytes/node.

The dotted line in the figure is $y=x$ and corresponds to the
breakeven point relative to \ab\ in isolation.  The solid line is the
least-squares best fit to the logarithmic data, and is given by $y =
1.57 x^{0.76}$.  This suggests that partition search is leading to an
effective reduction in branching factor of $b \rightarrow b^{0.76}$.
This improvement, above and beyond that provided by \ab, can be
contrasted with \ab\ itself, which gives a reduction when compared to
pure minimax of $b \rightarrow b^{0.75}$ if the moves are ordered
randomly~\cite{Pearl:ab} and $b \rightarrow b^{0.5}$ if the ordering
is optimal.

The method was also applied to full deals of 52 cards, which can be
solved while expanding an average of 18,000 nodes per
deal.\footnote{The version of \gib\ that was released in October of
  2000 replaced the transposition table with a data structure that
  uses a fixed amount of memory, and also sorts the moves based on
  narrowness (suggested by Plaat et~al.~\cite{Plaat:narrowness} to be
  rooted in the idea of conspiracy search
  \cite{McAllester:conspiracy}) and the killer heuristic.  While the
  memory requirements are reduced, the overall performance is little
  changed.}  This works out to about a second of {\sc cpu} time.

\section{Monte Carlo cardplay algorithms}
\label{s.monte}

One way in which we might use our perfect-information cardplay engine
to proceed in a realistic situation would be to deal the unseen cards
at random, biasing the deal so that it was consistent both with the
bidding and with the cards played thus far.  We could then analyze the
resulting deal double dummy and decide which of our possible plays was
the strongest.  Averaging over a large number of such Monte Carlo
samples would allow us to deal with the imperfect nature of bridge
information.  This idea was initially suggested by Levy
\cite{Levy:MonteCarlo}, although he does not appear to have realized
(see below) that there are problems with it in practice.

\begin{algorithm}[Monte Carlo card selection] To select a move from a
candidate set $M$ of such moves:
 \begin{enumerate}\setlength{\itemsep}{0pt}
 \item Construct a set $D$ of deals consistent with both the bidding and
play of the deal thus far.
 \item For each move $m\in M$ and each deal $d\in D$, evaluate the
double dummy result of making the move $m$ in the deal $d$.  Denote
the score obtained by making this move $s(m,d)$.
 \item Return that $m$ for which $\sum_d s(m,d)$ is maximal.
 \end{enumerate}
 \label{a.mc}
\end{algorithm}

The Monte Carlo approach has drawbacks that have been pointed out by a
variety of authors, including Koller$^\dag$ and others
\cite{Frank:bridge}.  Most obvious among these is that the approach
never suggests making an ``information gathering play.''  After all,
the perfect-information variant on which the decision is based
invariably assumes that the information will be available by the time
the next decision must be made!  Instead, the tendency is for the
approach to simply defer important decisions; in many situations this
may lead to information gathering inadvertently, but the amount of
information acquired will generally be far less than other approaches
might provide.

As an example, suppose that on a particular deal, \gib\ has four
possible lines of play to make its contract:
 \begin{enumerate}
 \item Line $A$ works if West has the \sd Q.
 \item Line $B$ works if East has the \sd Q.
 \item Line $C$ defers the guess until later.
 \item Line $D$ (the clever line) works independent of who has the \sd Q.
\end{enumerate}
 
Assuming that either player is equally likely to hold the \sd Q, a
Monte Carlo analyzer will correctly conclude that line $A$ works half
the time, and line $B$ works half the time.  Line $C$, however, will
be presumed to work {\em all\/} of the time, since the contract can
  still be made (double dummy) if the guess is deferred.  Line $D$
  will also be concluded to work all of the time (correctly, in this
case).
  
As a result, \gib\ will choose randomly between the last two
possibilities above, believing as it does that if it can only defer
the guess until later (even the next card), it will make that guess
correctly.  The correct play, of course, is $D$.

We will discuss a solution to these difficulties in Sections
\ref{s.achieve}--\ref{s.swo}; although \gib's defensive cardplay
continues to be based on the above ideas, its declarer play now uses
stronger techniques.  Nevertheless, basing the card play on the
algorithm presented leads to extremely strong results, approximately
at the level of a human expert.  Since \gib's introduction, all other
competitive bridge-playing programs have switched their cardplay to
similar methods, although \gib's double dummy analysis is
substantially faster than most of the other programs and its play is
correspondingly stronger.

We will describe three tests of GIB's cardplay algorithms: Performance
on a commercially available set of benchmarks, performance in a human
championship designed to highlight cardplay in isolation, and
statistical performance measured over a large set of deals.

For the first test, we evaluated the strength of \gib's cardplay using
{\em Bridge Master\/} (BM), a commercial program developed by Canadian
internationalist Fred Gitelman.  BM contains 180 deals at 5 levels of
difficulty.  Each of the 36 deals on each level is a problem in
declarer play.  If you misplay the hand, BM moves the defenders' cards
around if necessary to ensure your defeat.

BM was used for the test instead of randomly dealt deals because the
signal to noise ratio is far higher; good plays are generally rewarded
and bad ones punished.  Every deal also contains a lesson of some
kind; there are no completely uninteresting deals where the line of
play is irrelevant or obvious.  There are drawbacks to testing \gib's
performance on nonrandomly dealt deals, of course, since the BM deals
may in some way not be representative of the problems a bridge player
would actually encounter at the table.

The test was run under Microsoft Windows on a 200 MHz Pentium Pro.  As
a benchmark, Bridge Baron (BB) version 6 was also tested on the same
deals using the same hardware.\footnote{The current version is Bridge
  Baron 10 and could be expected to perform guardedly better in a test
  such as this.  Bridge Baron 6 does not include the Smith
  enhancements \cite{Nau:bridge}.}  BB was given 10 seconds to select
each play, and \gib\ was given 90 seconds to play the entire deal with
a maximum Monte Carlo sample size of 50.\footnote{GIB's Monte Carlo
  sample size is fixed at 50 in most cases, which provides a good
  compromise between speed of play and accuracy of result.}  New deals
were generated each time a play decision needed to be made.

These numbers approximately equalized the computational resources used
by the two programs; BB could in theory take 260 seconds per deal (ten
seconds on each of 26 plays), but in practice took substantially less.
\Gib\ was given the auctions as well; there was no facility for doing
this in BB.  This information was critical on a small number of deals.

Here is how the two systems performed:
 \begin{center}
\begin{tabular}{c|rr}
\bf{Level} & \bf BB & \bf GIB \\
\hline
1&16&31 \\
2&8&23 \\
3 & 2 & 12 \\
4 & 1 & 21 \\
5 & 4 & 13 \\
\hline
Total & 33 & 100 \\
& 18.3\% & 55.6\%
\end{tabular}
\end{center}
 Each entry is the number of deals that were played successfully by
the program in question.

\Gib's mistakes are illuminating.  While some of them involve failing
to gather information, most are problems in combining multiple chances
(as in case $D$ above).  As BM's deals get more difficult, they more
often involve combining a variety of possibly winning options and that
is why GIB's performance falls off at levels 2 and~3.

At still higher levels, however, BM typically involves the successful
development of complex end positions, and \gib's performance rebounds.
This appeared to happen to BB as well, although to a much lesser
extent.  It was gratifying to see \gib\ discover for itself the
complex end positions around which the BM deals are designed, and more
gratifying still to witness \gib's discovery of a maneuver that had
hitherto not been identified in the bridge literature, as described in
Appendix \ref{a.new}.

Experiments such as this one are tedious, because there is no text
interface to a commercial program such as Bridge Master or Bridge
Baron.  As a result, information regarding the sensitivity of \gib's
performance to various parameters tends to be only anecdotal.

\Gib\ solves an additional 16 problems (bringing its total to 64.4\%)
given additional resources in the form of extra time (up to 100
seconds per play, although that time was very rarely taken), a larger
Monte Carlo sample (100 deals instead of 50) and hand-generated
explanations of the opponents' bids and opening leads.  Each of the
three factors appeared to contribute equally to the improved
performance.

Other authors are reporting comparable levels of performance for \gib.
Forrester, working with a different but similar benchmark
\cite{Blackwood:play}, reports\footnote{Posting to rec.games.bridge on
  14 July 1997.} that \gib\ solves 68\% of the problems given 20
seconds/play, and 74\% of them given 30 seconds/play.  Deals where
\gib\ has outplayed human experts are the topic of a series of
articles in the Dutch bridge magazine {\em IMP} \cite[and
sequels]{IMP:GIB}.\footnote{\tt http://www.imp-bridge.nl} Based on
these results, \gib\ was invited to participate in an invitational
event at the 1998 world bridge championships in France; the event
involved deals similar to Bridge Master's but substantially more
difficult.  \Gib\ joined a field of 34 of the best card players in the
world, each player facing twelve such problems over the course of two
days.  \Gib\ was leading at the halfway mark, but played poorly on the
second day (perhaps the pressure was too much for it), and finished
twelfth.

The human participants were given 90 minutes to play each deal,
although they were penalized slightly for playing slowly.  GIB played
each deal in about ten minutes, using a Monte Carlo sample size of
500; tests before the event indicated little or no improvement if
\gib\ were allotted more time.  Michael Rosenberg, the eventual winner
of the contest and the pre-tournament favorite, in fact made one more
mistake than did Bart Bramley, the second place finisher.  Rosenberg
played just quickly enough that Bramley's accumulated time penalties
gave Rosenberg the victory.  The scoring method thus favors GIB
slightly.

\begin{figure}
\begin{center}
\input{dec-comp}
\end{center}
\caption{\Gib's performance as declarer}
\label{f.declare}
\end{figure}

Finally, \gib's performance was evaluated directly using records from
actual play.  These records are available from high levels of human
competition (world and national championships, typically), so that it
is possible to determine exactly how frequently humans make mistakes
at the bridge table.  In \fig{declare}, we show the frequency with
which this data indicates that a human declarer, leading to the $n$th
trick of a deal, makes a mistake that causes his contract to become
unmakeable on a double-dummy basis.  The $y$ axis gives the frequency
of the mistakes and is plotted logarithmically; as one would expect,
play becomes more accurate later in the deal.

We also give similar data for \gib, based on large sample of deals
that \gib\ played against itself.  The error profiles of the two are
quite similar.

Before turning to defensive play, let me point out that this method of
analysis favors \gib\ slightly.  Failing to make an information
gathering play gets reflected in the above figure, since the lack of
information will cause \gib\ to make a double-dummy mistake
subsequently.  But human declarers often work to give the defenders
problems that exploit their relative lack of information, and that
tactic is not rewarded in the above analysis.  Similar results for
defensive play appear in \fig{defend}.

\begin{figure}
\begin{center}
\input{def-comp}
\end{center}
\caption{\Gib's performance as defender}
\label{f.defend}
\end{figure}

There are two important technical remarks that must be made about the
Monte Carlo algorithm before proceeding.  First, note that we were
cavalier in simply saying, ``Construct a set $D$ of deals consistent
with both the bidding and play of the deal thus far.''

To construct deals consistent with the bidding, we first simplify the
auction as observed, building constraints describing each of the hands
around the table.  We then deal hands consistent with the constraints
using a deal generator that deals unbiased hands given restrictions on
the number of cards held by each player in each suit.  This set of
deals is then tested to remove elements that do not satisfy the
remaining constraints, and each of the remaining deals is passed to
the bidding module to identify those for which the observed bids would
have been made by the players in question.  (This assumes that \gib\ 
has a reasonable understanding of the bidding methods used by the
opponents.)  The overall dealing process typically takes one or two
seconds to generate the full set of deals needed by the algorithm.

Now the card play must be analyzed.  Ideally, \gib\ would do something
similar to what it does for the bidding, determining whether each
player would have played as indicated on any particular deal.
Unfortunately, it is simply impractical to test each hypothetical
decision recursively against the cardplay module itself.  Instead,
\gib\ tries to evaluate the probability that West (for example) has
the \sd K (for example), and to then use these probabilities to weight
the sample itself.

To understand the source of the weighting probabilities, let us
consider a specific example.  Suppose that in some particular
situation, \gib\ plays the $\spadesuit 5$.  The analysis indicates
that 80\% of the time that the next player (say West) holds the
$\spadesuit$K, it is a mistake for West not to play it.  In other
words, West's failure to play the \sd K leads to odds of 4:1 that he
hasn't got it.

These odds are now used via Bayes' rule to adjust the probability that
West holds the $\spadesuit$K at all.  The probabilities are then
modified further to include information revealed by defensive
signalling (if any), and the adjusted probabilities are finally used
to bias the Monte Carlo sample.  The evaluation $\sum_d s(m,d)$ in
\alg{mc} is replaced with $\sum_d w_d s(m,d)$ where $w_d$ is the weight
assigned to deal $d$.  More heavily weighted deals thus have a larger
impact on \gib's eventual decision.

The second technical point regarding the algorithm itself involves the
fact that it needs to run quickly and that it may need to be
terminated before the analysis is complete.  For the former, there are
a variety of greedy techniques that can be used to ensure that a move
$m$ is not considered if we can show $\sum_d s(d,m) \leq \sum_d
s(d,m')$ for some $m'$.  The algorithm also uses iterative broadening
\cite{Ginsberg:broaden} to ensure that a low-width answer is available
if a high-width search fails to terminate in time.  Results from the
low- and high-width searches are combined when time expires.

Also regarding speed, the algorithm requires that for each deal in the
Monte Carlo sample and each possible move, we evaluate the resulting
position exactly.  Knowing simply that move $m_1$ is not as good as
move $m_2$ for deal $d$ is not enough; $m_1$ may be better than $m_2$
elsewhere and we need to compare them quantitatively.  This approach
is aided substantially by the partition search idea, where entries in
the transposition table correspond not to single positions and their
evaluated values, but to sets of positions and values.  In many cases,
$m_1$ and $m_2$ may fall into the same entry of the partition table
long before they actually transpose into one another exactly.

\section{Monte Carlo bidding}
\label{s.bidding}

The purpose of bidding in bridge is twofold.  The primary purpose is
to share information about your cards with your partner so that you
can cooperatively select an optimal final contract.  A secondary
purpose is to disrupt the opponents' attempt to do the same.

In order to achieve this purpose, a wide variety of bidding
``languages'' have been developed.  In some, when you suggest clubs as
trumps, it means you have a lot of them.  In others, the suggestion is
only temporary and the information conveyed is quite different.  In
all of these languages, {\em some\/} meaning is assigned to a wide
variety of bids in particular situations; there are also default rules
that assign meanings to bids that have no specifically assigned
meanings.  Any computer bridge player will need similar
understandings.

Bidding is interesting because the meanings frequently overlap; there
may be one or more bids that are suitable (or nearly so) on any
particular set of cards.  Existing computer programs have simply
matched possible bids against large databases giving their meanings,
searching for that bid that best matches the cards that the machines
hold.  World champion Chip Martel reports$^\dag$ that human experts
take a different approach.\footnote{The 1994 Rosenblum Cup World Team
  Championship was won by a team that included Martel and
  Rosenberg.}$^,$\footnote{Frank suggests \cite{Frank:bridgebook} that
  the existing machine approach is capable of reaching expert levels
  of performance.  While this appears to have been true in the early
  1980's \cite{Lindelof:Cobra}, modern expert bidding practice has
  begun to highlight the disruptive aspect of bidding, and machine
  performance is no longer likely to be competitive.}

Although expert bidding is based on a database such as that used by
existing programs, close decisions are made by simulating the results
of each candidate action.  This involves projecting how the bidding is
likely to proceed and evaluating the play in one of a variety of
possible final contracts.  An expert gets his ``judgment'' from a
Monte Carlo-like simulation of the results of possible bids, often
referred to in the bridge-playing community as a {\em Borel\/}
simulation (so named after the first player to describe the method).
\Gib\ takes a similar tack.

\begin{algorithm}[Borel simulation] To select a bid from a candidate
set $B$, given a database $Z$ that suggests bids in various
situations:
 \begin{enumerate}\setlength{\itemsep}{0pt}
 \item Construct a set $D$ of deals consistent with the bidding thus
far.
 \item For each bid $b\in B$ and each deal $d\in D$, use the database
$Z$ to project how the auction will continue if the bid $b$ is made.
(If no bid is suggested by the database, the player in question is
assumed to pass.)  Compute the double dummy result of the eventual
contract, denoting it $s(b,d)$.\label{project}
 \item Return that $b$ for which $\sum_d s(b,d)$ is maximal.
 \end{enumerate}
 \label{a.bs}
\end{algorithm}

As with the Monte Carlo approach to card play, this approach does not
take into account the fact that bridge is not played double dummy.
Human experts often choose not to make bids that will convey too much
information to the opponents in order to make the defenders' task as
difficult as possible.  This consideration is missing from the above
algorithm.\footnote{In theory at least, this issue could be addressed
using the single-dummy ideas that we will present in subsequent
sections.  Computational considerations currently make this
impractical, however.}

There are more serious problems also, generally centering around the
development of the bidding database $Z$.

First, the database itself needs to be built and debugged.  A large
number of rules need to be written, typically in a specialized
language and dependent upon the bridge expertise of the author.  The
rules need to be debugged as actual play reveals oversights or other
difficulties.

The nature and sizes of these databases vary enormously, although all
of them represent very substantial investments on the part of the
authors.  The database distributed with {\sc meadowlark bridge}
includes some 7300 rules; that with {\sc q-plus bridge} 2500 rules
comprising 40,000 lines of specialized code.  \Gib's database is built
using a derivative of the Meadowlark language, and includes about 3000
rules.

All of these databases doubtless contain errors of one sort or
another; one of the nice things about most bidding methods is that
they tend to be fairly robust against such problems.  Unfortunately,
the Borel algorithm described above introduces substantial instability
in \gib's overall bidding.

To understand this, suppose that the database $Z$ is somewhat
conservative in its actions.  The projection in step \ref{project} of
\alg{bs} now leads each player to assume its partner bids
conservatively, and therefore to bid somewhat aggressively to
compensate.  The partnership as a whole ends up {\em
  over\/}compensating.

Worse still, suppose that there is an omission of some kind in $Z$;
perhaps every time someone bids $7\diamondsuit$, the database suggests
a foolish action.  Since $7\diamondsuit$ is a rare bid, a bidding
system that matches its bids directly to the database will encounter
this problem infrequently.

\Gib, however, will be much more aggressive, bidding $7\diamondsuit$
often on the grounds that doing so will cause the opponents to make a
mistake.  In practice, of course, the bug in the database is unlikely
to be replicated in the opponents' minds, and \gib's attempts to
exploit the gap will be unrewarded or worse.

This is a serious problem, and appears to apply to any attempt to
heuristically model an adversary's behavior: It is difficult to
distinguish a good choice that is successful because the opponent has
no winning options from a bad choice that {\em appears\/} successful
because the heuristic fails to identify such options.

There are a variety of ways in which this problem might be addressed,
none of them perfect.  The most obvious is simply to use \gib's
aggressive tendencies to identify the bugs or gaps in the bidding
database, and to fix them.  Because of the size of the database, this
is a slow process.

Another approach is to try to identify the bugs in the database
automatically, and to be wary in such situations.  If the bidding
simulation indicates that the opponents are about to achieve a result
much worse than what they might achieve if they saw each other's
cards, that is evidence that there may be a gap in the database.
Unfortunately, it is also evidence that \gib\ is simply effectively
disrupting its opponents' efforts to bid accurately.

Finally, restrictions could be placed on \gib\ that require it to make
bids that are ``close'' to the bids suggested by the database, on the
grounds that such bids are more likely to reflect improvements in
judgment than to highlight gaps in the database.

All of these techniques are used, and all of them are useful.  \Gib's
bidding is substantially better than that of earlier programs, but 
not yet of expert caliber.

The bidding was tested as part of the 1998 Baron Barclay/OKBridge
World Computer Bridge Championships, and the 2000 Orbis World Computer
Bridge Championship.  Each program bid deals that had previously been
bid and played by experts; a result of~0 on any particular deal meant
that the program bid to a contract as good as the average expert
result.  A positive result was better, and a negative result was
worse.

There were 20 deals in each contest; although card play was not an
issue, the deals were selected to pose challenges in bidding and a
standard deviation of 5.5 \imps/deal is still a reasonable estimate.
One standard deviation over the 20 deal set could thus be expected to
be about 25 \imps.

\Gib's final score in the 1998 bidding contest was +2 \imps; in the
2000 contest it was +9 \imps.  In both cases, it narrowly edged out
the expert field against which it was compared.\footnote{This is in
  spite of the earlier remark that GIB's bidding is not of expert
  caliber.  GIB was fortunate in the bidding contests in that most of
  the problems involved situations handled by the database.  When
  faced with a situation that it does not understand, GIB's bidding
  deteriorates drastically.} The next best program in 1998, Blue Chip
Bridge, finished with a score of -35 \imps, not dissimilar from the
-37 \imps\ that had been sufficient to win the bidding contest in
1997.  The second place program in 2000 (once again Blue Chip Bridge)
had a score of -2 \imps.

\section{The value of information}
\label{s.achieve}

In previous sections of this paper, we have described Monte Carlo
methods for dealing with the fact that bridge is a game of imperfect
information, and have also described possible problems with this
approach.  We now turn to ways to overcomes some of these
difficulties.

For the moment, let me assume that we replace bridge with a
$\set{0,1}$ game, so that we are interested only in the question of
whether declarer makes his contract.  Overtricks or extra undertricks
are irrelevant.  At least as a first approximation, bridge experts
often look at hands this way, only subsequently refining the analysis.

If you ask such an expert why he took a particular line on a deal, he
will often say something like, ``I was playing for each opponent to
have three hearts,'' or ``I was playing for West to hold the spade
queen.''  What he is reporting is that set of distributions of the
unseen cards for which he was expecting to make the hand.

At some level, the expert is treating the value of the game not as
zero or one (which it would be if he could see the unseen cards), but
as a {\em function} from the set of possible distributions of unseen
cards into $\set{0,1}$.  If we denote this set of distributions by $S$,
the value of the game is thus a function
 \[f:S\rightarrow \set{0,1}\]
 We will follow standard mathematical notation and denote the set
$\set{0,1}$ by $2$ and denote the set of functions $f:S\rightarrow 2$
by $2^S$.

It is possible to extend $\max$ and $\min$ from the set $\set{0,1}$
to $2^S$ in a pointwise fashion, so that, for example
 \begin{equation}
\min(f,g)(s) = \min(f(s),g(s))
 \label{e.pointwise}
 \end{equation}
 for functions $f,g\in 2^S$ and a specific situation $s\in S$.  The
maximizing function is defined similarly.

As an example, suppose that in a particular situation, there is one
line of play $f$ that wins if West has the \sd Q.  There is another
line of play $g$ that wins if East has exactly three hearts.  Now
$\min(f,g)$ is the line of play that wins just in case {\em both\/}
West has the \sd Q and East has three hearts, while $\max(f,g)$ is
the line of play that wins if either condition obtains.

It is important to realize that the set $2^S$ is not totally ordered
by these max and min functions, like the unit interval is.  Instead,
$2^S$ is an instance of a mathematical structure known as a {\em
lattice\/} \cite[and \secn{alpha}]{Grat78}.  At this point, we note
only that we can extend \defn{game} to any set with maximization and
minimization operators:

\begin{definition} A {\em game\/} is an octuple
$(G,V,p_I,s,\ev,f_+,f_-)$ such that:

\begin{enumerate}

 \item $G$ is a finite set of possible positions in the game.
 \item $V$ is the set of values for the game.
 \item $p_I\in G$ is the initial position of the game.
 \item $s:G\rightarrow 2^G$ gives the successors of a given position.
 \item $\ev:G\rightarrow \set{\tmax,\tmin}\cup V$ gives the value for
terminal positions or indicates which player is to move for nonterminal
positions.
 \item $f_+:\powset(V)\rightarrow V$ and $f_-:\powset(V)\rightarrow V$
are the combination functions for the maximizer and minimizer
respectively.
 \end{enumerate}
 The structures $G$, $V$, $p_I$, $s$ and $\ev$ are required to satisfy
the following conditions (unchanged from \defn{game}):

\begin{enumerate}

\item There is no sequence of positions $p_0,\dots,p_n$ with $n>0$,
$p_i \in s(p_{i-1})$ for each $i$ and $p_n = p_0$.  In other words,
there are no ``loops'' that return to an identical position.

\item $\ev(p)\in V$ if and only if $s(p) = \emptyset$.
 \end{enumerate}
 \label{d.game2}
\end{definition}
 
This definition extends \defn{game} only in that the value set and
combination functions have been generalized.  A such, \defn{game2}
includes both ``conventional'' games in which the values are numeric
and the combination functions are max/min, and our more general
setting where the values are functional and the combination functions
combine them as described above.

As usual, we can use the maximization and minimization functions to
assign a value to the root of the tree:

\begin{definition} Given a game $(G,V,p_I,s,\ev,f_+,f_-)$, we
introduce a function $\evc: G \rightarrow V$ defined recursively by
 \[\evc(p) = \cases{\ev(p), & if $\ev(p)\in V$;\cr
                f_+\set{\evc(p')|p'\in s(p)}, & if $\ev(p)=\tmax$; \cr
                f_-\set{\evc(p')|p'\in s(p)}, & if $\ev(p)=\tmin$.}\]
 The {\em value\/} of $(G,V,p_I,s,\ev,f_+,f_-)$ is defined to be
$\evc(p_I)$.
 \end{definition}

The definition is well founded because the game has no loops, and it
is straightforward to extend the minimax algorithm \ref{a.minimax} to
this more general formalism.  We will discuss extensions of \ab\ in
the next section.

To flesh out our previous informal description, we need to instantiate
\defn{game2}.  We do this by having the value of any particular node
correspond to the set of positions where the maximizer can win:
 \begin{enumerate}
 \item The set $G$ of positions is a set of pairs $(p,Z)$ where $p$ is
a position with only two of the four bridge hands visible (i.e., a
position in the ``single dummy'' game), and $Z$ is that subset of $S$
(the set of situations) that is consistent both with $p$ and with the
cards that were played to reach $p$ from the initial position.
\item The value set $V$ is $2^S$.
\item The initial position $p_I$ is $(p_0,S)$, where $p_0$ is the
  initial single-dummy position.
\item The successor function is described as follows:
 \begin{enumerate}
 \item If the declarer/maximizer is on play in the given position, the
   successors are obtained by enumerating the maximizer's legal plays
   and leaving the set $Z$ of situations unchanged.
 \item If the minimizer is on play in the given position, the
   successors are obtained by playing any card $c$ that is legal in
   any element of $Z$ and then restricting $Z$ to that subset for
   which $c$ is in fact a legal play.
 \end{enumerate}
\item Terminal nodes are nodes where all cards have been played, and
  therefore correspond to single situations $s$, since the locations
  of all cards have been revealed.  For such a terminal position, if
  the declarer has made his contract, the value is $S$ (the entire set
  of positions possible at the root).  If the declarer has failed to
  make his contract, the value is $S-\set{s}$.
\item The maximization and minimization functions are computed
  pointwise, so that
 \[f_+(U,V) = U\cup V\]
 and
 \[f_-(U,V) = U\cap V\]
 \end{enumerate}
 Given an initial single-dummy situation $p$ corresponding to a set
$S$ of situations, we will call the above game the {\em $(p,S)$ game}.

\begin{proposition}  Suppose that the set of situations for which the
maximizer can make his contract is $T\subseteq S$.  Then the value of
the $(p,S)$ game is $T$.
 \label{p.perfect}
 \end{proposition}

It is natural to view $T$ as an element of $2^S$; it is the function
mapping points in $T$ to 1 and points outside of $T$ to 0.

\proof The proof proceeds by induction on the depth of the game tree.
If the root node $p$ is also terminal, then $S=\set s$ and the value
is clearly set correctly (to $s$ or $\emptyset$) by the definition of
the $(p,S)$ game.

If $p$ is nonterminal, suppose first that it is a maximizing node.
Now let $s\in S$ be some particular situation.  If the maximizer can
win in $s$, then there is some successor $(p',S')$ to $(p,S)$ where
the maximizer wins, and hence by the inductive hypothesis, the value
of $(p',S')$ is a set $U$ with $s\in U$.  But since the maximizer
moves in $p$, the value assigned to $(p,S)$ is a superset of the value
assigned to any subnode, so that $s\in \evc(p,S)=T$.

If, on the other hand, the maximizer cannot win in $s$, then he cannot
win in any child of $s$.  If $(p_i,S_i)$ are the successors of $(p,S)$
in the game tree, then again by the inductive hypothesis, we must have
$s\not\in \evc(p_i,S_i)$ for each $i$.  But
 \[\evc(p,S) = \cup_i \evc(p_i,S_i)\]
so that $s\not\in \evc(p,S)=T$.
 
For the minimizing case, suppose that the maximizer wins in $s$.  Then
the maximizer must win in every successor of $s$, so that $s\in
\evc(p_i,S_i)$ for each such successor and therefore $s\in \evc(p,S)$.
Alternatively, if the minimizer wins in $s$, he must have a legal
winning option so that $s\not\in \evc(p_i,S_i)$ for some $i$ and
therefore $s\not\in \evc(p,S)$.  \proofend

Unfortunately, \prop{perfect} is in some sense exactly what we wanted
{\em not\/} to prove: it says that our modified game computes the set
of situations in which it is possible for the maximizer to make his
contract if he has perfect information about the opponents' cards, not
the set of situations in which it is possible for him to make his
contract given his actual state of incomplete information.

Before we go on to deal with this, however, let me look at an example
in some detail.  The example we will use is similar to that of
\secn{monte} and involves a situation where the maximizer can make his
contract if either West has the \sd Q or East has three hearts.  I
will denote by $S$ the set of situations where West has the \sd Q, and
by $T$ the set where East has three hearts.  It's possible to tie in
the ``defer the guess'' example from \secn{monte} as well, so I will
do that also.  Here is the game tree for the game in question:

\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(.4,2.1){\makebox(0,0)[r]{min}}
\put(2.4,2.1){\makebox(0,0)[r]{min}}
\put(6.6,2.1){\makebox(0,0)[l]{min}}
\put(3.9,1.1){\makebox(0,0)[r]{min}}
\put(5.1,1.1){\makebox(0,0)[l]{min}}
\put(0,.9){\makebox(0,0)[t]{1}}
\put(1,.9){\makebox(0,0)[t]{0}}
\put(2,.9){\makebox(0,0)[t]{0}}
\put(3,.9){\makebox(0,0)[t]{1}}
\put(6,.9){\makebox(0,0)[t]{1}}
\put(7,.9){\makebox(0,0)[t]{1}}
\put(3.75,-.1){\makebox(0,0)[t]{1}}
\put(4.25,-.1){\makebox(0,0)[t]{0}}
\put(4.75,-.1){\makebox(0,0)[t]{0}}
\put(5.25,-.1){\makebox(0,0)[t]{1}}
\put(.15,1.5){\makebox(0,0)[r]{$S$}}
\put(2.15,1.5){\makebox(0,0)[r]{$S$}}
\put(6.15,1.5){\makebox(0,0)[r]{$S$}}
\put(3.775,.5){\makebox(0,0)[r]{$S$}}
\put(4.775,.5){\makebox(0,0)[r]{$S$}}
\put(.85,1.5){\makebox(0,0)[l]{$T$}}
\put(2.85,1.5){\makebox(0,0)[l]{$T$}}
\put(6.85,1.5){\makebox(0,0)[l]{$T$}}
\put(4.225,.5){\makebox(0,0)[l]{$T$}}
\put(5.225,.5){\makebox(0,0)[l]{$T$}}
\end{picture}
\end{center}

At the root node, the maximizer has four choices.  If he makes the
move on the left (playing for $S$, as it turns out), the minimizer then
moves in a situation where the maximizer wins if $S$ holds and loses
if $T$ holds.  For the second move, where the maximizer is essentially
playing for $T$, the reverse is true.

In the third case, the maximizer defers the guess.  We suppose that he
is on play again immediately, forced to commit between playing for
$S$ and playing for $T$.  In the last case, he wins independent of
whether $T$ or $S$ obtains.

In the Monte Carlo setting, the above tree will actually be split
based on the element of the sample in question.  In some cases, $S$
will be true and we will examine only this subtree:

\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(2,0){4}{\dot}
\put(5,1){\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(1,0){2}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(4.5,2)(2,0){1}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(.4,2.1){\makebox(0,0)[r]{min}}
\put(2.4,2.1){\makebox(0,0)[r]{min}}
\put(6.6,2.1){\makebox(0,0)[l]{min}}
\put(3.9,1.1){\makebox(0,0)[r]{min}}
\put(5.1,1.1){\makebox(0,0)[l]{min}}
\put(0,.9){\makebox(0,0)[t]{1}}
\put(2,.9){\makebox(0,0)[t]{0}}
\put(6,.9){\makebox(0,0)[t]{1}}
\put(3.75,-.1){\makebox(0,0)[t]{1}}
\put(4.75,-.1){\makebox(0,0)[t]{0}}
\put(.15,1.5){\makebox(0,0)[r]{$S$}}
\put(2.15,1.5){\makebox(0,0)[r]{$S$}}
\put(6.15,1.5){\makebox(0,0)[r]{$S$}}
\put(3.775,.5){\makebox(0,0)[r]{$S$}}
\put(4.775,.5){\makebox(0,0)[r]{$S$}}
\end{picture}
\end{center}
 The maximizer can win by making any move other than the second.  In
the cases where $T$ obtains, we examine:

\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(1,1)(2,0){4}{\dot}
\put(4,1){\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(4.25,0)(1,0){2}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(4,1)(2,0){1}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(.4,2.1){\makebox(0,0)[r]{min}}
\put(2.4,2.1){\makebox(0,0)[r]{min}}
\put(6.6,2.1){\makebox(0,0)[l]{min}}
\put(3.9,1.1){\makebox(0,0)[r]{min}}
\put(5.1,1.1){\makebox(0,0)[l]{min}}
\put(1,.9){\makebox(0,0)[t]{0}}
\put(3,.9){\makebox(0,0)[t]{1}}
\put(7,.9){\makebox(0,0)[t]{1}}
\put(4.25,-.1){\makebox(0,0)[t]{0}}
\put(5.25,-.1){\makebox(0,0)[t]{1}}
\put(.85,1.5){\makebox(0,0)[l]{$T$}}
\put(2.85,1.5){\makebox(0,0)[l]{$T$}}
\put(6.85,1.5){\makebox(0,0)[l]{$T$}}
\put(4.225,.5){\makebox(0,0)[l]{$T$}}
\put(5.225,.5){\makebox(0,0)[l]{$T$}}
\end{picture}
\end{center}
Here, the maximizer can win by making any move other than the first.
In all cases, both of the last two moves win for the maximizer, since
this approach cannot recognize the fact that the third move simply
defers the guess while the fourth wins outright.

Now let us return to the situation where we include information about
the sets that it is possible to play for.  Here is the tree again:
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(.4,2.1){\makebox(0,0)[r]{min}}
\put(2.4,2.1){\makebox(0,0)[r]{min}}
\put(6.6,2.1){\makebox(0,0)[l]{min}}
\put(3.9,1.1){\makebox(0,0)[r]{min}}
\put(5.1,1.1){\makebox(0,0)[l]{min}}
\put(0,.9){\makebox(0,0)[t]{1}}
\put(1,.9){\makebox(0,0)[t]{0}}
\put(2,.9){\makebox(0,0)[t]{0}}
\put(3,.9){\makebox(0,0)[t]{1}}
\put(6,.9){\makebox(0,0)[t]{1}}
\put(7,.9){\makebox(0,0)[t]{1}}
\put(3.75,-.1){\makebox(0,0)[t]{1}}
\put(4.25,-.1){\makebox(0,0)[t]{0}}
\put(4.75,-.1){\makebox(0,0)[t]{0}}
\put(5.25,-.1){\makebox(0,0)[t]{1}}
\put(.15,1.5){\makebox(0,0)[r]{$S$}}
\put(2.15,1.5){\makebox(0,0)[r]{$S$}}
\put(6.15,1.5){\makebox(0,0)[r]{$S$}}
\put(3.775,.5){\makebox(0,0)[r]{$S$}}
\put(4.775,.5){\makebox(0,0)[r]{$S$}}
\put(.85,1.5){\makebox(0,0)[l]{$T$}}
\put(2.85,1.5){\makebox(0,0)[l]{$T$}}
\put(6.85,1.5){\makebox(0,0)[l]{$T$}}
\put(4.225,.5){\makebox(0,0)[l]{$T$}}
\put(5.225,.5){\makebox(0,0)[l]{$T$}}
\end{picture}
\end{center}

The first thing that we need to do is to realize that the terminal
nodes should not be labelled with 1's and 0's but instead with sets
where the maximizer can win.  This produces:

\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(.4,2.1){\makebox(0,0)[r]{min}}
\put(2.4,2.1){\makebox(0,0)[r]{min}}
\put(6.6,2.1){\makebox(0,0)[l]{min}}
\put(3.9,1.1){\makebox(0,0)[r]{min}}
\put(5.1,1.1){\makebox(0,0)[l]{min}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize $S$}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize $T$}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(3.5,-.1){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize $S$}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize $T$}}
\put(5.5,-.1){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(.15,1.5){\makebox(0,0)[r]{$S$}}
\put(2.15,1.5){\makebox(0,0)[r]{$S$}}
\put(6.15,1.5){\makebox(0,0)[r]{$S$}}
\put(3.775,.5){\makebox(0,0)[r]{$S$}}
\put(4.775,.5){\makebox(0,0)[r]{$S$}}
\put(.85,1.5){\makebox(0,0)[l]{$T$}}
\put(2.85,1.5){\makebox(0,0)[l]{$T$}}
\put(6.85,1.5){\makebox(0,0)[l]{$T$}}
\put(4.225,.5){\makebox(0,0)[l]{$T$}}
\put(5.225,.5){\makebox(0,0)[l]{$T$}}
\end{picture}
\end{center}
To understand the labels, consider the two leftmost fringe nodes.  The
leftmost node gets labelled with $T$ ``for free'' because $T$ is
eliminated by the fact that the minimizer chose $S$.  Since the
maximizer wins in $S$, the maximizer wins in all cases.

For the second fringe node, $S$ is included by virtue of the
minimizer's moving to $T$; $T$ is not included because the minimizer
actually wins on this line.  Hence the label of $T$ for the node in
question.  This analysis assumes that $S$ and $T$ are disjoint; if
they overlap, the labels become slightly more complex but the overall
analysis is little changed.

Backing up the values one step gives us:

\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)
\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize $S$}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize $T$}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(3.5,-.1){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize $S$}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize $T$}}
\put(5.5,-.1){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(.4,2.1){\makebox(0,0)[r]{\scriptsize $S$}}
\put(2.4,2.1){\makebox(0,0)[r]{\scriptsize $T$}}
\put(6.6,2.1){\makebox(0,0)[l]{\scriptsize $S\cup T$}}
\put(3.9,1.1){\makebox(0,0)[r]{\scriptsize $S$}}
\put(5.1,1.1){\makebox(0,0)[l]{\scriptsize $T$}}
\end{picture}
\end{center}
The minimizer, playing with perfect information, always does as best
he can.  The first interior node's label of $S$, for example, means
that the maximizer wins only if $S$ actually is the case.

Of course, our definitions thus far imply that the maximizer is
playing with perfect information as well, and we can back up the rest
of the tree to get:

\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)
\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{\scriptsize $S\cup T$}}
\put(4.6,2){\makebox(0,0)[l]{\scriptsize $S\cup T$}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize $S$}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize $T$}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(3.5,-.1){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize $S$}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize $T$}}
\put(5.5,-.1){\makebox(0,0)[t]{\scriptsize $S\cup T$}}
\put(.4,2.1){\makebox(0,0)[r]{\scriptsize $S$}}
\put(2.4,2.1){\makebox(0,0)[r]{\scriptsize $T$}}
\put(6.6,2.1){\makebox(0,0)[l]{\scriptsize $S\cup T$}}
\put(3.9,1.1){\makebox(0,0)[r]{\scriptsize $S$}}
\put(5.1,1.1){\makebox(0,0)[l]{\scriptsize $T$}}
\end{picture}
\end{center}
As before, the maximizer ``wins'' with either of the last two options.

Before we address the fact that the players do not in fact have
perfect information, let me point out that in most bridge analyses,
imperfect information is assumed to be an issue for the maximizer
only.  The defenders are assumed to be operating with complete
information for at least the following reasons:

\begin{figure}
\begin{center}
\input{dec-def}
\end{center}
\caption{Defense vs.~declarer play for humans}
\label{f.human}
\end{figure}

 \begin{enumerate}
 \item In general, there is a premium for declaring as opposed to
   defending, so that both sides want to declare.  Typically, the pair
   with greater assets in terms of high cards wins the ``bidding
   battle'' and succeeds in becoming the declaring side, so that the
   overall assets available to the defenders in terms of high cards
   are generally less than those available to the declarer.  This
   means that the defenders will generally be able to predict each
   other's hands with more accuracy than the declarer can.
 \item The defenders can signal, conveying to one another information
   about the cards they hold.  (As an example, play of an
   unnecessarily high card often indicates an even number of cards in
   the suit being played.)  They are generally assumed to signal only
   information that is useful to them but not to declarer, once again
   improving their collective ability to play as if they had perfect
   information. 
 \item After the first two or three tricks, defenders' play is
   typically closer to double dummy than is the declarer's.  This is
   shown in \fig{human}, which contrasts the quality of human play as
   defender with the quality of human play as declarer; we make more
   mistakes declaring than defending as of trick four.  (This figure
   is analogous to Figures \ref{f.declare} and \ref{f.defend}.)
 \end{enumerate}
 There are some deals where it is important for declarer to exploit
uncertainty on the part of the defenders, but these are definitely the
exception as opposed to the rule.

This suggests that \prop{perfect} is doing a reasonable job of
modeling the defenders' cardplay, but the combination function for the
maximizer needs to be modified to reflect the imperfect-information
nature of his task.

To understand this, let us return to our putative expert, who
suggested at the beginning of this section that he might be playing
for West to hold the spade queen.  What he might say in a bit more
detail is, ``I could play for each opponent to hold exactly three
hearts, or I could play for West to hold the spade queen.  The latter
was the better chance.''

This suggests that the value assigned to the position by the maximizer
is not a single set of situations (those in which he can make the
contract), but a {\em set\/} ${\cal S}$ of sets of situations.  Each
set $S\in {\cal S}$ corresponds to one set of situations that the
maximizer could play for, given his incomplete knowledge of the
positions of the opposing cards.

Extending the notation used earlier in this section, we will denote
the set of sets of situations by $2^{2^S}$.  The maximizer's
combination function on $2^{2^S}$ is given by
 \begin{equation}
 \max({\cal F},{\cal G}) = {\cal F}\cup {\cal G}
\label{e.maximize}
\end{equation}
where each of $\cal F$ and $\cal G$ are sets of sets of situations.
This says that if the maximizer is on play in a situation $p$, and he
has one move that will allow him to select from a set ${\cal F}$ of
things to ``play for'' and another move that will allow him to select
from a set ${\cal G}$, then his choice at $p$ is to select from any
element of ${\cal F}\cup {\cal G}$. 

The minimizer's function is a bit more subtle.  Suppose that at a node
$p$, the minimizer can move to a successor with value ${\cal F} =
\set{F_i}$, or to a successor with value ${\cal G}=\set{G_i}$.  What
value should we assign to $p$?

Since the minimizer has perfect information, he will always guarantee
that the maximizer achieves the minimum value for the actual
situation.  Whatever element of $F_i\in{\cal F}$ or $G_j\in{\cal G}$
is eventually selected by the maximizer, the eventual value of $p$ will
be the minimum of $F_i$ and $G_j$.  In other words
 \begin{equation}
\min(\set{F_i},\set{G_j}) = \set{\min(F_i,G_j)}
 \label{e.minimize}
\end{equation}
where the individual minima are computed using the perfect information
rule \eq{pointwise}.
 
 \begin{definition} Let $G$ be the set of positions in an imperfect
   information game, a set of pairs $(p,Z)$ where $p$ is a position
   from the point of view of the maximizing player and $Z$ is the set of
   perfect information positions
   consistent with $p$.  The {\em imperfect information game for $G$}
   is the game $(G,V,p_I,s,\ev,f_+,f_-)$ where:
 \begin{enumerate}
 \item The value set $V$ is $2^{2^S}$.
 \item The initial position $p_I$ is $(p_0,S)$, where $p_0$ is the
   initial imperfect information position and $S$ is the set of all
   perfect information positions consistent with it.
 \item The successor function is described as follows:
 \begin{enumerate}
 \item If the maximizer is on play in the given position, the
   successors are obtained by enumerating the maximizer's legal plays
   and leaving the elements of the set $Z$ of situations unchanged.
 \item If the minimizer is on play in the given position, the
   successors are obtained by making playing any card $c$ that is
   legal in any element of $X$ and then restricting 
   $Z$ to those situations for which $c$ is in fact a legal
   play.
 \end{enumerate}
\item Terminal nodes are nodes where all cards have been played, and
  therefore correspond to single situations $s$.  For such a terminal
  position, if the declarer has made his contract, the value is 
  $(\set{s},\set{S})$.  If the declarer has failed to make his
  contract, the value is $(\set{s},\set{S-\set s})$.
 \item The maximization and minimization functions are given by
\eq{maximize} and \eq{minimize} respectively.
 \end{enumerate}
\label{d.game3}
\end{definition}

\begin{theorem} Suppose that the value of the imperfect information
  game for $G$ is $\cal T$.  Then a set of positions $T$ is a subset
  of an element of $\cal T$ if and only if the maximizer has a
  strategy that wins in every element of $T$, assuming that the
  minimizer plays with perfect information.
 \label{t.imperfect}
\end{theorem}
 
\proof Once again, the proof proceeds by induction on the depth of the
game tree.  And once again, the case where $p$ is a terminal position
is handled easily by the definition.  For the inductive case, we
consider the maximizer and minimizer separately.
 
For the maximizer, suppose that there is some set $T$ of situations
that satisfies the conditions of the theorem, so that the maximizer
has a strategy that caters to all of the elements of $T$.  Then the
first move of that strategy will be some single move to a position
$p_i$ that is a successor of $p$ and that caters to the elements of
$T$.  Thus if the value of the successful child is ${\cal F}$, $T$ is
a subset of some $F\in {\cal F}$ by the inductive hypothesis.  Thus if
the value of the original game is ${\cal G}$, $T$ is a subset of an
element of ${\cal G}$ by virtue of \eq{maximize}.

Alternatively, if $T$ is a set for which the maximizer has no such
strategy, then clearly the maximizer cannot have a strategy after
making any of the moves to the successor positions $p_i$.  This means
that no superset $U\supseteq T$ in any $\evc(p_i)$, and thus no
superset of $T$ in $\evc(p)$ either.

The minimizing case is not really any harder.  Suppose first that the
maximizer has no strategy for succeeding in every situation in $T$.
Then the minimizer (playing with perfect information) must have some
move to a position $p_i$ with value ${\cal F}_i$ such that $T$ is not
a subset of any element of ${\cal F}_i$.  Now if ${\cal
  F}_i=\set{T_i}$, recall that
 \[\min(\set{T_i},\set{U_i}) = \set{T_i\cap U_j},\]
 and $T\not\subseteq T_i$ for each $i$.  Thus $T\not\subseteq T_i\cap U_j$
for each $i$ and $j$, and there is no $V\supseteq T$ with
\[V\in \min(\set{T_i},\set{U_i})\]

For the last case, suppose that the maximizer does have a strategy for
succeeding in every situation in $T$.  That means that after any move
for the minimizer, the maximizer will still have a strategy that
succeeds in $T$, so that if $p_i$ are the successors of $p$ and
$\evc(p_i) = {\cal T}_i$, then there is a $T_i\in {\cal T}_i$ with
$T\subseteq T_i$.  Now $T\subseteq \cap_i T_i \in \min({\cal T}_i) =
\evc(p)$.  Thus $\evc(p)$ contains an element that is a superset of
$T$.  \proofend

Using this result, we can in theory compute exactly the set of things
we might play for given a single-dummy bridge problem.  Before we turn
to the issues involved in doing so in practice, however, let me repeat
the example of this section using the imperfect information technique.
Here is the game tree again with values assigned to the terminal
nodes:

\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(.4,2.1){\makebox(0,0)[r]{min}}
\put(2.4,2.1){\makebox(0,0)[r]{min}}
\put(6.6,2.1){\makebox(0,0)[l]{min}}
\put(3.9,1.1){\makebox(0,0)[r]{min}}
\put(5.1,1.1){\makebox(0,0)[l]{min}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize $\set S$}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize $\set T$}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(3.4,-.1){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize $\set S$}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize $\set T$}}
\put(5.6,-.1){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(.15,1.5){\makebox(0,0)[r]{$S$}}
\put(2.15,1.5){\makebox(0,0)[r]{$S$}}
\put(6.15,1.5){\makebox(0,0)[r]{$S$}}
\put(3.775,.5){\makebox(0,0)[r]{$S$}}
\put(4.775,.5){\makebox(0,0)[r]{$S$}}
\put(.85,1.5){\makebox(0,0)[l]{$T$}}
\put(2.85,1.5){\makebox(0,0)[l]{$T$}}
\put(6.85,1.5){\makebox(0,0)[l]{$T$}}
\put(4.225,.5){\makebox(0,0)[l]{$T$}}
\put(5.225,.5){\makebox(0,0)[l]{$T$}}
\end{picture}
\end{center}

Backing up past the minimizer's final move gives us:

\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(.4,2.1){\makebox(0,0)[r]{\scriptsize $\set S$}}
\put(2.4,2.1){\makebox(0,0)[r]{\scriptsize $\set T$}}
\put(6.6,2.1){\makebox(0,0)[l]{\scriptsize $\set{S\cup T}$}}
\put(3.9,1.1){\makebox(0,0)[r]{\scriptsize $\set S$}}
\put(5.1,1.1){\makebox(0,0)[l]{\scriptsize $\set T$}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize $\set S$}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize $\set T$}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(3.4,-.1){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize $\set S$}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize $\set T$}}
\put(5.6,-.1){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\end{picture}
\end{center}
 And we can now complete the analysis to finally get:
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{\scriptsize $\set{S,T,S\cup T}$}}
\put(4.6,2.0){\makebox(0,0)[l]{\scriptsize $\set{S,T}$}}
\put(.4,2.1){\makebox(0,0)[r]{\scriptsize $\set S$}}
\put(2.4,2.1){\makebox(0,0)[r]{\scriptsize $\set T$}}
\put(6.6,2.1){\makebox(0,0)[l]{\scriptsize $\set{S\cup T}$}}
\put(3.9,1.1){\makebox(0,0)[r]{\scriptsize $\set S$}}
\put(5.1,1.1){\makebox(0,0)[l]{\scriptsize $\set T$}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize $\set S$}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize $\set T$}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(3.4,-.1){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize $\set S$}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize $\set T$}}
\put(5.6,-.1){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\end{picture}
\end{center}
Note the difference in the values assigned to the maximizer's third
and fourth choices at the first ply.  The third choice has value
$\set{S,T}$, indicating clearly that the maximizer will need to
subsequently decide whether to play for $S$ or for $T$.  But the
fourth choice has value $\set{S\cup T}$ indicating that both
possibilities are catered to.  

The value assigned to the root contains some redundancy (which we will
deal with in \secn{swo}), in that one of the maximizer's choices
($S\cup T$) dominates the others.  Nevertheless, this value clearly
indicates that the maximizer has an option available at the root that
caters to both situations.

\section{Extending alpha-beta pruning to lattices}
\label{s.alpha}

The results of the previous section allow us to deal with imperfect
information in theory.  Unfortunately, computing the value in theory
is hardly the same as computing it in practice.  Some ideas, such as
transposition tables and partition search, can fairly obviously be
applied to games with values taken from sets more general than total
orders.  But what about \ab, the linchpin of high-performance
adversary search algorithms?  The answer here is far more subtle.

\subsection{Some necessary definitions}
\label{s.basic}

\begin{figure}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{center}
\begin{picture}(3,3.2)(0,-.7)

\multiput(0,0)(1,0){4}{\dot}
\put(1.5,1){\dot}
\put(0,0){\line(3,2){1.5}}
\put(1,0){\line(1,2){.5}}
\put(1.5,1){\line(1,-2){.5}}
\put(1.5,1){\line(3,-2){1.5}}
\put(1.25,2){\line(1,-4){.25}}
\put(1.6,1.1){\makebox(0,0)[l]{min}}
\put(0,-.1){\makebox(0,0)[t]{$m_1$}}
\put(1,-.1){\makebox(0,0)[t]{$m_2$}}
\put(2,-.1){\makebox(0,0)[t]{$m_3$}}
\put(3,-.1){\makebox(0,0)[t]{$m_4$}}
\end{picture}
\hspace{.5in}
\begin{picture}(2.5,3.2)(0,-.2)

\multiput(1.5,0)(.5,0){3}{\dot}
\multiput(.5,1)(1.5,0)2{\dot}
\put(1.25,2){\dot}
\put(1.5,0){\line(1,2){.5}}
\put(2,0){\line(0,1){1}}
\put(2,1){\line(1,-2){.5}}
\put(.5,1){\line(3,4){.75}}
\put(1.25,2){\line(3,-4){.75}}
\put(1,3){\line(1,-4){.25}}
\put(2.1,1.1){\makebox(0,0)[l]{min}}
\put(1.35,2.1){\makebox(0,0)[l]{min}}
\put(.5,.9){\makebox(0,0)[t]{$m_2$}}
\put(1.5,-.1){\makebox(0,0)[tr]{$m_1$}}
\put(2,-.1){\makebox(0,0)[t]{$m_3$}}
\put(2.5,-.1){\makebox(0,0)[tl]{$m_4$}}
\end{picture}
\end{center}
\caption{Equivalent games?}
\label{f.binary}
\end{figure}

Let us begin by considering the two small game trees in \fig{binary},
where the minimizer is on play at the nonfringe nodes and none of the
$m_i$ is intended to be necessarily terminal.  Are these two games
always equivalent?

We would argue that they are.  In the game on the left, the minimizer
needs to select among the four options $m_1,m_2,m_3,m_4$.  In the game
on the right, he needs to first select whether or not to play $m_2$;
if he decides not to, he must select among the remaining options.  Since
the minimizer has the same possibilities in both cases, we assume that
the values assigned to the games are the same.

From a more formal point of view, the value of the game on the left is
$f_-(m_1,m_2,m_3,m_4)$, while that of the game on the right is
$f_-(m_2,f_-(m_1,m_3,m_4))$ where we have abused notation somewhat,
writing $m_i$ for the value of the node $m_i$ as well.

\begin{definition}
 A game will be called {\em simple} if for any $x\in v\subseteq V$,
 \[f_+\set{x} = f_-\set{x} = x\]
and also
 \[f_+(v) = f_+\set{x,f_+(v-x)}\]
and
 \[f_-(v) = f_-\set{x,f_-(v-x)}\]
\label{d.binary}
 \end{definition}

We have augmented the condition developed in the discussion of
\fig{binary} with the assumption that if a player's move in a position
$p$ is forced (so that $p$ has a unique successor), then the value
before and after the forced move is the same.

\begin{proposition} For any simple game, there are binary functions
$\wedge$ and $\vee$ from $V$ to itself that are commutative,
associative and idempotent\/\footnote{A binary function $f$ is called
{\em idempotent\/} if $f(a,a)=a$ for all a.} and such that
 \[f_+\set{v_0,\dots,v_m} = v_0 \vee \cdots \vee v_m\]
and
 \[f_-\set{v_0,\dots,v_m} = v_0 \wedge \cdots \wedge v_m\]
 \end{proposition}

\proof Induction on $m$.\proofend

When referring to a simple game, we will typically replace the
functions $f_+$ and $f_-$ by the equivalent binary functions $\vee$
and $\wedge$.  We assume throughout the rest of this section that all
games are simple.\footnote{We also assume that the games are
sufficiently complex that we can find in the game tree a node with any
desired functional value, e.g., $a\wedge(b\vee c)$ for specific $a$,
$b$ and $c$.  Were this not the case, none of our results would
follow.  As an example, a game in which the initial position is also
terminal surely admits pruning of all kinds (since the game tree is
empty) but need not satisfy the conclusions of the results in this
section.}

The binary functions $\vee$ and $\wedge$ now induce a partial order
$\leq$, where we will say that $x\leq y$ if and only if $x\vee y = y$.
It is not hard to see that this partial order is reflexive ($x\leq
x$), antisymmetric ($x\leq y$ and $y\leq x$ if and only if $x=y$) and
transitive.  The operators $\vee$ and $\wedge$ behave like greatest
lower bound and least upper bound operators with regard to the partial
order.

We also have the following:

\begin{proposition} Whenever $S\subseteq T$, $f_+(S)\leq f_+(T)$ and
$f_-(S)\geq f_-(T)$.~~\proofend
 \end{proposition}

In other words, assuming that the minimizer is trying to reach a low
value in the partial order and the maximizer is trying to reach a high
one, having more options is always good.

\subsection{Shallow pruning}
\label{s.shallow}

We are now able to investigate \ab\ in our general framework.  Let us
begin with shallow pruning, shown in \fig{shallow}.

\begin{figure}
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(2.5,3.2)(0,-.2)
\multiput(1.5,0)(1,0){2}{\dot}
\multiput(.5,1)(1.5,0)2{\dot}
\put(1.25,2){\dot}
\put(1.5,0){\line(1,2){.5}}
\put(2,1){\line(1,-2){.5}}
\put(.5,1){\line(3,4){.75}}
\put(1.25,2){\line(3,-4){.75}}
\put(1,3){\line(1,-4){.25}}
\put(2.1,1.1){\makebox(0,0)[l]{max}}
\put(1.35,2.1){\makebox(0,0)[l]{min}}
\put(.5,.9){\makebox(0,0)[t]{$x$}}
\put(1.5,-.1){\makebox(0,0)[tr]{$y$}}
\put(2.5,-.1){\makebox(0,0)[tl]{$T$}}
\end{picture}
\end{center}
\caption{$T$ can be pruned (shallowly) if $x\leq y$}
\label{f.shallow}
\end{figure}

The idea here is that if the minimizer prefers $x$ to $y$, he will
never allow the maximizer even the possibility of selecting between
$y$ and the value of the subtree rooted at $T$.  After all, the value
of the maximizing node in the figure is $y\vee \evc(T) \geq y \geq
x$, and the minimizer will therefore always prefer $x$.

In order for the usual correctness proof for (shallow) \ab\ to hold, 
we need the following condition to be satisfied:

\begin{definition}(Shallow \ab) A game $G$ will be said to {\em allow
shallow \ab\ for the minimizer} if
 \begin{equation}
x \wedge (y \vee T) = x
 \label{e.min0}
 \end{equation}
 for all $x,y,T\in V$ with $x\leq y$.  The game will be said to {\em
allow shallow \ab\ for the maximizer} if
 \begin{equation}
x \vee (y \wedge T) = x
 \label{e.max0}
 \end{equation}
 for all $x,y,T\in V$ with $x\geq y$.  We will say that $G$ {\em
allows shallow pruning} if it allows shallow \ab\ for both players.
 \end{definition}
 The definition basically says that the backed up value at the root of
the game tree is unchanged by pruning the maximizing subtree in the
figure.

As we will see shortly, the expressions \eq{min0} and \eq{max0}
describing shallow pruning are identical to what are more typically
known as {\em absorption identities}.

\begin{definition} Suppose $V$ is a set and $\wedge$ and $\vee$ are
two binary operators on $V$.  The triple $(V,\wedge,\vee)$ is called a
{\em lattice} if $\wedge$ and $\vee$ are idempotent, commutative and
associative, and satisfy the {\em absorption identities} in that for
any $x,y\in V$,
 \begin{eqnarray}
 x\vee (x\wedge y) & = & x \label{e.abs1} \\
 x\wedge (x\vee y) & = & x \label{e.abs2}
 \end{eqnarray}
 \end{definition}

We also have the following:

\begin{definition} A lattice $(V,\wedge,\vee)$ is called {\em
distributive} if $\wedge$ and $\vee$ distribute with respect to one
another, so that 
 \begin{eqnarray}
 x\vee(y \wedge z) & = & (x\vee y) \wedge (x\vee z) \label{e.dist1} \\
 x\wedge(y \vee z) & = & (x\wedge y) \vee (x\wedge z) \label{e.dist2}
 \end{eqnarray}
 \end{definition}

\begin{lemma}  Each of \eq{abs1} and \eq{abs2} implies the other.
Each of \eq{dist1} and \eq{dist2} implies the other.
\end{lemma}

\proof These are well known results from lattice theory
\cite{Grat78}.\proofend

\begin{proposition}{\bf\cite{Jaffray:alpha}} For a game
  $G$, the following conditions are equivalent:
 \begin{enumerate}
 \item $G$ allows shallow \ab\ for the minimizer.
 \item $G$ allows shallow \ab\ for the maximizer.
 \item $G$ allows shallow pruning.
 \item $(V,\wedge,\vee)$ is a lattice. 
 \end{enumerate}
 \end{proposition}

\noindent{\bf Proof.}\footnote{The proofs of this and \prop{deep} are
due to Alan Jaffray.}  We show that the first and fourth conditions
are equivalent; everything else follows easily.

If $G$ allows shallow \ab\ for the minimizer, we take $x = a$
and $y = T = a\vee b$ in \eq{min0}.  Clearly $x\leq y$ so we get
 \[a \wedge (y \vee y) = a \wedge y = a \wedge (a \vee b) = a\]
 as in \eq{abs2}.

For the converse, if $x\leq y$, then $x\wedge y = x$ and
 \begin{eqnarray*}
 x \wedge (y \vee T) & = & (x \wedge y) \wedge (y \vee T) \\
                & = & x \wedge (y \wedge (y \vee T)) \\
                & = & x \wedge y \\
                & = & x.\proofend
 \end{eqnarray*}

\subsection{Deep pruning}
\label{s.deep}

Deep pruning is a bit more subtle.  An example appears in \fig{deep}.

\begin{figure}
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.07}}}
\begin{picture}(2.5,3.2)(0,-.2)
\multiput(1.5,0)(1,0){2}{\dot}
\multiput(.5,1)(1.5,0)2{\dot}
\put(1.25,2){\dot}
\put(1.5,0){\line(1,2){.5}}
\put(2,1){\line(1,-2){.5}}
\put(.5,1){\line(3,4){.75}}
\put(1.25,2){\line(3,-4){.75}}
\put(1,3){\line(1,-4){.25}}
\put(1.5,1.67){\dot}
\put(1.6,1.77){\makebox(0,0)[l]{max}}
\put(1.75,1.33){\dot}
\put(1.87,1.43){\makebox(0,0)[l]{min}}
\put(1.05,1.07){\line(3,4){.45}}
\put(1.45,.93){\line(3,4){.3}}
\put(2.1,1.1){\makebox(0,0)[l]{max}}
\put(1.35,2.1){\makebox(0,0)[l]{min}}
\put(.5,.9){\makebox(0,0)[t]{$x$}}
\put(1.5,-.1){\makebox(0,0)[tr]{$y$}}
\put(2.5,-.1){\makebox(0,0)[tl]{$T$}}
\end{picture}
\end{center}
\caption{$T$ can be pruned (deeply) if $x\leq y$}
\label{f.deep}
\end{figure}

As before, assume $x\leq y$.  The argument is as described previously:
Given that the minimizer has a guaranteed value of $x$ at the upper
minimizing node, there is no way that a choice allowing the maximizer
to reach $y$ can be on the main line; if it were, then the maximizer
could get a value of at least $y$.

\begin{definition}(Deep \ab) A game $G$ will be said to {\em allow
\ab\ for the minimizer} if for any $x,y,T,z_1,\dots,z_{2i}\in V$ with
$x\leq y$,
 \begin{eqnarray*}
x\wedge(z_1 \vee (z_2 \wedge \cdots \vee (z_{2i} \wedge (y \vee T)))\cdots)
        = \qquad \\
 x\wedge(z_1 \vee (z_2 \wedge \cdots \vee z_{2i})\cdots).
 \end{eqnarray*}
 The game will be said to {\em allow \ab\ for the maximizer} if
 \begin{eqnarray*}
x\vee(z_1 \wedge (z_2 \vee \cdots \wedge (z_{2i} \vee (y \wedge T)))\cdots)
        = \qquad \\
 x\vee(z_1 \wedge (z_2 \vee \cdots \wedge z_{2i})\cdots).
 \end{eqnarray*}
 We will say that $G$ {\em allows pruning} if it allows \ab\ for both
players.
 \end{definition}
 As before, the prune allows us to remove the dominated node ($y$ in
\fig{deep}) and all of its siblings.

\begin{figure}
\begin{center}
\thicklines\setlength{\unitlength}{.3in}\renewcommand{\dot}{{\circle*{.15}}}
\begin{picture}(5,4)
\multiput(1,4)(1,-1)5{\dot}
\put(1,4){\line(1,-1)4}
\multiput(0,3)(1,-1)4{\line(1,1)1}
\put(5.2,-.1){\makebox(0,0)[l]0}
\put(-.1,2.9){\makebox(0,0)[r]{$\clubsuit$}}
\put(.9,1.9){\makebox(0,0)[r]{$\diamondsuit$}}
\put(1.9,.9){\makebox(0,0)[r]{$\heartsuit$}}
\put(2.9,-.1){\makebox(0,0)[r]{$\clubsuit$}}
\put(3.2,2.1){\makebox(0,0)[l]{max}}
\put(4.2,1.1){\makebox(0,0)[l]{min}}
\put(1.2,4.1){\makebox(0,0)[l]{max}}
\put(2.2,3.1){\makebox(0,0)[l]{min}}
\end{picture}
\end{center}
\caption{The deep pruning counterexample}
\label{f.nodeep}
\end{figure}

The fact that a game allows shallow \ab\ does not mean that it allows
pruning in general, as is shown by the following counterexample.  The
example involves a game with one card that is known to both players;
only the suit of the card matters.  The game tree appears in
\fig{nodeep}.

In this tree, a node labelled with a suit symbol is terminal and means
that the maximizer wins if and only if the suit of the card matches
the given symbol.  So at the root of the given tree, the maximizer
(whose turn it is to play) can choose to ``turn over'' the card,
winning if and only if it's a club, or can defer to the minimizer.
The minimizer can choose to turn the card ({\em losing\/} just in case
it's a diamond -- the suit symbols refer to the maximizer's result),
or hand the situation back to the maximizer.  If the maximizer defers
yet again, the minimizer can either turn over the card, losing if it's
a club, or simply declare victory (presumably his choice).

There is one other wrinkle in this game.  At any point in the game,
the maximizer can change the card from either a diamond or a spade to
a club.

Now let's consider the game itself.  At ply 4, the minimizer will
obviously choose to win the game.  Thus at ply 3, the maximizer will
need to choose \hs, winning just in case the card is a heart.  But
this means that at ply 2, the minimizer will win the game, since if
the card is not a diamond he will move to the left (and win at once)
while if the card is not a heart he can win by moving to the right.
(Remember that the minimizer knows the suit of the card.)  The upshot
of this is that the maximizer wins the overall game if and only if the
card in question is a club.  A formal analysis proceeds similarly,
labelling the nodes as follows:
\begin{center}
\thicklines\setlength{\unitlength}{.3in}\renewcommand{\dot}{{\circle*{.15}}}
\begin{picture}(5,4)
\multiput(1,4)(1,-1)5{\dot}
\put(1,4){\line(1,-1)4}
\multiput(0,3)(1,-1)4{\line(1,1)1}
\put(5.2,-.1){\makebox(0,0)[l]0}
\put(-.1,2.9){\makebox(0,0)[r]{$\clubsuit$}}
\put(.9,1.9){\makebox(0,0)[r]{$\diamondsuit$}}
\put(1.9,.9){\makebox(0,0)[r]{$\heartsuit$}}
\put(2.9,-.1){\makebox(0,0)[r]{$\clubsuit$}}
\put(3.2,2.1){\makebox(0,0)[l]{$\heartsuit = \heartsuit \vee 0$}}
\put(4.2,1.1){\makebox(0,0)[l]{$0=\clubsuit \wedge 0$}}
\put(1.2,4.1){\makebox(0,0)[l]{$\clubsuit = \clubsuit \vee 0$}}
\put(2.2,3.1){\makebox(0,0)[l]{$0 = \diamondsuit \wedge \heartsuit$}}
\end{picture}
\end{center}
Note, incidentally, that the maximizer's ability to change the card
does not help him win the game.

Now suppose that we apply deep pruning to this game.  The ply four
node is one where the minimizer can force a value of at most \cl,
suggesting that the siblings of the bottom \cl\ node can be pruned.
But doing so produces the following tree:
\begin{center}
\thicklines\setlength{\unitlength}{.3in}\renewcommand{\dot}{{\circle*{.15}}}
\begin{picture}(5,4)
\multiput(1,4)(1,-1)5{\dot}
\put(1,4){\line(1,-1)4}
\multiput(0,3)(1,-1)4{\line(1,1)1}
\put(5.2,-.1){\makebox(0,0)[l]{pruned?}}
\put(-.1,2.9){\makebox(0,0)[r]{$\clubsuit$}}
\put(.9,1.9){\makebox(0,0)[r]{$\diamondsuit$}}
\put(1.9,.9){\makebox(0,0)[r]{$\heartsuit$}}
\put(2.9,-.1){\makebox(0,0)[r]{$\clubsuit$}}
\put(3.2,2.1){\makebox(0,0)[l]{$1 = \heartsuit \vee \clubsuit$}}
\put(4.2,1.1){\makebox(0,0)[l]{\cl}}
\put(1.2,4.1){\makebox(0,0)[l]{$\clubsuit \vee \diamondsuit$}}
\put(2.2,3.1){\makebox(0,0)[l]{$\diamondsuit = \diamondsuit \wedge 1$}}
\end{picture}
\end{center}
If the maximizer reaches ply 3, he can win by changing the card to a
club if need be.

Of course, the minimizer won't let the maximizer reach ply 3; at ply
2, he'll move left so that the maximizer wins only if the card is a
diamond.  That means that the maximizer wins at the root just in case
the card is either a club or a diamond.

A partial graph of the values for this game is as follows:
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.07}}}
\begin{picture}(3,2)
\multiput(1.5,0)(0,2)2{\dot}
\multiput(0,1)(1,0)4{\dot}
\put(0,1){\line(3,2){1.5}}
\put(0,1){\line(3,-2){1.5}}
\put(1,1){\line(1,2){.5}}
\put(1,1){\line(1,-2){.5}}
\put(1.5,0){\line(3,2){1.5}}
\put(1.5,0){\line(1,2){.5}}
\put(1.6,-0.1){\makebox(0,0)[l]0}
\put(1.6,2){\makebox(0,0)[l]1}
\put(-.1,1){\makebox(0,0)[r]{$\clubsuit$}}
\put(2.1,1){\makebox(0,0)[l]{$\diamondsuit$}}
\put(.9,1){\makebox(0,0)[r]{$\heartsuit$}}
\put(3.1,1){\makebox(0,0)[l]{$\spadesuit$}}
\end{picture}
\end{center}
where we have included the crucial fact that $x\wedge y=0$ if $x\neq
y$ (since the minimizer knows the card) and $\heartsuit \vee \clubsuit
= 1$ because the maximizer can invoke his special rule.  Other least
upper bounds are not shown in the diagram.  The maximizing function
$\vee$ moves up the figure; the minimizing function $\wedge$ moves
down.

The deep prune fails because we can't ``push'' the value $\clubsuit
\wedge 0$ past the $\heartsuit$ to get to the $\clubsuit$ near the
root.  Somewhat more precisely, the problem is that
 \[\heartsuit = \heartsuit \vee (\clubsuit \wedge 0) \neq
         (\heartsuit \wedge \clubsuit) \vee (\heartsuit \wedge 0) = 0\]
 This suggests the following:

\begin{proposition}{\bf \cite{Jaffray:alpha}} For a game
  $G$, the following conditions are equivalent:
 \begin{enumerate}
 \item $G$ allows \ab\ for the minimizer.
 \item $G$ allows \ab\ for the maximizer.
 \item $G$ allows pruning.
 \item $(V,\wedge,\vee)$ is a distributive lattice.
 \end{enumerate}
 \label{p.deep}
 \end{proposition}

\proof As before, we show only that the first and fourth conditions
are equivalent.  Since pruning implies shallow pruning (take $i=0$ in
the definition), it follows that the first condition implies that
$(V,\wedge,\vee)$ is a lattice.

From deep pruning for the minimizer with $i=1$, we have that if $x\leq y$,
then for any $z_1,z_2,T$, 
 \[x\wedge (z_1\vee(z_2\wedge(y\vee T))) = x\wedge(z_1\vee z_2)\]
 Now take $y = T = x$ to get
 \begin{equation}
x \wedge (z_1 \vee(z_2 \wedge x)) = x\wedge(z_1\vee z_2)
 \label{e.e0}
 \end{equation}
 It follows that each top level term in the left hand side of \eq{e0}
is greater than or equal to the right hand side; specifically
 \begin{equation}
z_1 \vee (z_2\wedge x) \geq x \wedge (z_1 \vee z_2).
 \label{e.e1}
 \end{equation}
 We claim that this implies that the lattice in question is
distributive.

To see this, let $u,v,w\in V$.  Now take $z_1=u\wedge w$, $z_2=v$ and
$x=w$ in \eq{e1} to get
 \begin{equation}
(u\wedge w) \vee (v\wedge w) \geq w \wedge ((u \wedge w) \vee v)
 \label{e.e2}
 \end{equation}
 But $v\vee (u\wedge w) \geq w \wedge (v\vee u)$ is an instance of
\eq{e1}, and combining this with \eq{e2} gives us
 \begin{eqnarray*}
(u\wedge w) \vee (v\wedge w) & \geq & w \wedge ((u \wedge w) \vee v) \\
& \geq & w \wedge w \wedge (v\vee u) \\
& = &  w \wedge (v\vee u)
 \end{eqnarray*}

This is the hard direction; $w\wedge(v\vee u) \geq (u\wedge w)
\vee(v\wedge w)$ for any lattice because $w\wedge(v\vee u) \geq
u\wedge w$ and $w\wedge(v\vee u) \geq v\wedge w$ individually.  Thus
$w\wedge(v\vee u) = (u\wedge w) \vee(v\wedge w)$, and deep pruning
implies that the lattice is distributive.

For the converse, if the lattice is distributive and $x\leq y$, then
 \begin{eqnarray*}
 x\wedge (z_1\vee(z_2\wedge(y\vee T))) & \!\!\!=\!\!\! &
        (x \wedge z_1) \vee (x \wedge z_2 \wedge (y\vee T)) \\
 & \!\!\!=\!\!\! & (x \wedge z_1) \vee (x \wedge z_2) \\ 
 & \!\!\!=\!\!\! & x \wedge (z_1 \vee z_2)
 \end{eqnarray*}
 where the second equality is a consequence of the fact that $x\leq
(y\vee T)$, so that $x = x\wedge (y\vee T)$.  This validates pruning
for $i=1$; deeper cases are similar.\proofend

Finally, note that in games where this result applies, we can continue
to use Algorithms \ref{a.abt} or \ref{a.ps} without modification,
since the prunes that they endorse continue to be sound as the game
tree is expanded.

\subsection{Application to imperfect information}

In order to apply these ideas to games of imperfect information
treated as in \secn{achieve}, we need to show that the value set
introduced there is a (hopefully distributive) lattice.

To do this, recall that there is redundant information in an arbitrary
element ${\cal F}$ of $2^{2^S}$, since if ${\cal F}$ contains both $T$
and $U$ with $T\subseteq U$ (in other words, the maximizer can play
for either $T$ or for $U$ but $U$ is properly better), the set $T$ can
be removed from ${\cal F}$ without affecting the maximizer's options
in any interesting way.  This suggests the following:

\begin{definition} Let ${\cal F}\in 2^{2^S}$ for an arbitrary set $S$.
  We will say that ${\cal F}$ is {\em reduced\/} if there are no
  $T,U\in {\cal F}$ with $T\subseteq U$.  We will say that ${\cal
    F}_1$ is a {\em reduction\/} of ${\cal F}_2$ if ${\cal F}_1$ is
  reduced and ${\cal F}_1\subseteq {\cal F}_2$.
 \end{definition}

\begin{lemma} Every ${\cal F}\in 2^{2^S}$ has a unique reduction.
\end{lemma}
 
\proof This is immediate; just remove the subsumed elements from $\cal
F$.  \proofend.
 
We will denote the reduction of $\cal F$ by $r(\cal F)$.

Armed with this definition, we can now modify \defn{game3} in the
obvious way, replacing the value set $V$ with the set of reduced
elements of $V$ and the maximizing and minimizing functions
\eq{maximize} and \eq{minimize} with the reduced versions thereof,
so that
 \begin{equation}
 \max({\cal F},{\cal G}) = r({\cal F}\cup {\cal G})
 \label{e.max2}
 \end{equation}
and
 \begin{equation}
 \min(\set{F_i},\set{G_j}) = r(\set{F_i\cap G_j})
 \label{e.min2}
 \end{equation}
 Remember that we typically write $\vee$ for $\max$ and $\wedge$ for
$\min$.

\begin{proposition} Given the above definitions, $(V,\vee,\wedge)$
is a distributive lattice.
\end{proposition}
 
\proof We need to show that $\max$ and $\min$ as defined above are
commutative, associative, and idempotent, that they distribute with
respect to one another, and that the absorption identity \eq{abs1} is
satisfied.  Since the reduction operator clearly commutes with the
initial definitions of $\max$ and $\min$, commutativity, associativity
and distributivity are obvious, as is the fact that $\vee$ is
idempotent.  To see that $\wedge$ is idempotent, we have
 \[{\cal F} \wedge {\cal F} = r(\set{\min(F_i,F_j)}) = r(\set{F_i \cap F_j})\]
but each element of the set on the righthand side is a subset of
$F_i\cap F_i$ so
 \[{\cal F} \wedge {\cal F} = r(\set{F_i}) = r({\cal F}) = {\cal F}.\]

For the absorption identity, we need to show that 
 \[{\cal F}\vee ({\cal F}\wedge {\cal G}) = {\cal F}\]
But
 \[{\cal F} \wedge {\cal G} = r\set{F_i \cap G_j} \]
 so
\begin{eqnarray*}
 {\cal F}\vee ({\cal F}\wedge {\cal G}) & = & 
        r({\cal F} \vee r\set{F_i \cap G_j}) \\
& = & r(\set{F_i} \cup \set{F_i \cap G_j}) \\
& = & r(\set{F_i}) \\
& = & r({\cal F}) \\
& = & {\cal F}
 \end{eqnarray*}
 since, once again, each element of ${\cal F} \wedge {\cal G}$ is
 subsumed by the corresponding $F_i$.  \proofend

It follows that an implementation designed to compute the value of an
imperfect information game as described by \thm{imperfect} can indeed
use \ab\ to speed the computation.

\subsection{Bridge implementation}

Given this body of theory, we implemented a single-dummy version of
\gib's double-dummy search engine.  Not surprisingly, the most
difficult element of the implementation was building efficient data
structures for the manipulation of elements of $2^{2^S}$.

To handle this, we represented each element of $S$ as a conjunction.
We first identified one of the two hidden hands $H$, and then for each
card $c$, would write $c$ if $c$ were held by $H$ and $\neg c$ if $c$
were not held by $H$.  An element of $2^S$ was then taken to be a
disjunctive combination of these conjunctions, and an element of
$2^{2^S}$ was taken to be a list of such disjunctions.  The advantage
of this representation was that logical inference could be used to
construct the reduction of any such list.

In order to make this inference as efficient as possible, the
disjunctions themselves were represented as {\em binary decision
  diagrams}, or \bdd's \cite{buddy}.  There are a variety of public
domain implementations of \bdd's available, and we used one provided
by Lind-Nielsen \cite{buddy}.\footnote{We tried a variety of non-\bdd\ 
  based implementations as well.  The \bdd-based implementation was
  far faster than any of the others.}

The resulting implementation solves small endings (perhaps 16 cards
left in total) quickly but for larger endings, the running times come
to be dominated by the \bdd\ computations; this is hardly surprising,
since the size of individual \bdd s can be exponential in the size of
$S$ (the number of possible distributions of the unseen cards).  We
found that we were generally able to solve 32-card endings in about a
minute, but that the running times were increasing by two orders of
magnitude as each additional card was added.

This is both good news and bad news.  Viewed positively, the
performance of the system as constructed is far superior to the
performance of preceding attempts to deal with the imperfect
information arising in bridge.  Frank et.al, for example, are only
capable of solving single suit combinations (13 cards left, give or
take) using an algorithm that appears to take several minutes to run
\cite{Frank:bridgeprog}.  They subsequently improve the performance to
an average time of 0.6 seconds \cite{Frank:bridge2}, but are still
restricted to problems that are too small to be of much use to a
program intended to play the complete game.

That's the good news.  The bad news is that a program capable only of
solving an 8-card ending in a minute is inappropriate for production
use.  \Gib\ is a production program, expected to play bridge at human
speeds.  Another approach was therefore needed.

\section{Solving single-dummy problems in practice}
\label{s.swo}

\subsection{Achievable sets}

The key to practical application of the ideas in the previous section
is the realization that when it comes time to make a play, a single
element of $\cal F$ must be selected: if you can play for West to have
the \sd Q or for each player to have three hearts but cannot cater to
both possibilities simultaneously, you eventually have to actually
make the choice.

\begin{definition} Suppose that the value of the imperfect information
game for $G$ is $\cal F$.  Given a specific $A\subseteq S$, we will
say that $A$ is {\em achievable\/} if there is some $F\in \cal F$ for
which $A\subseteq F$.
 \end{definition}
 In other words, the set $A$ of situations is achievable if the
maximizer has a plan that wins for all elements of $A$.

\begin{definition} Given a set $S$ of situations, a {\em payoff
function\/} for $S$ is any function $f:2^S\rightarrow\R$ such that
$f(U)\leq f(T)$ whenever $U\subseteq T$.
 \label{d.payoff}
 \end{definition}
 The payoff function evaluates potential achievable sets.

\begin{definition} Let $G$ be a game and $S$ the associated set of
situations.  If $f$ is a payoff function for $S$, a {\em solution to
$G$ under $f$} is any achievable set $A$ for which $f(A)$ is maximal.
 \end{definition}
 In practice, we need not find the actual value of the game; finding a
solution to $G$ under an appropriate payoff function suffices.  In
bridge, the payoff function is presumably the probability that the
cards are dealt as in the set $A$; this function clearly increases
with increasing set size as required by \defn{payoff} and can be
evaluated in practice using the Monte Carlo sample of \secn{monte}.

Instead of finding the solution to an imperfect information game,
suppose instead that we have a Monte Carlo sample for the game
consisting of a set of situations $S=\set{s_i}$ that is ordered
as $i=0,\dots,n$.  We can now produce an achievable set $A$ as 
follows:

\begin{algorithm} To construct a maximal achievable set $A$ from a sequence
  $\langle s_0,\dots,s_n\rangle$ of situations:
 \begin{enumerate}\setlength{\itemsep}{0pt}
 \item Set $A = \emptyset$.
 \item For $i=0,\dots,n$, if $A\cup\set{s_i}$ is achievable, set
$A = A\cup\set{s_i}$.\label{unionstep}
 \end{enumerate}
\label{a.greedy}
\end{algorithm}
 The algorithm constructs the achievable set in a greedy fashion,
gradually adding elements of $S$ to $A$ until no more can be added.

\begin{definition} Given a game $G$ and a sequence $S$ of situations,
the {\em achievable set induced by $S$ for $G$} is the set constructed
by \alg{greedy}.
\end{definition}

From a computational point of view, the expensive step in the
algorithm is determining whether or not the set $A\cup\set{s_i}$ is
achievable.  This is relatively straightforward, however, since the
focus on a specific set effectively replaces the game $G$ with a new
game with values in $\set{0,1}$.  At any particular node $n$, if
expanding $n$ demonstrates that $A\cup\set{s_i}$ is not achievable,
the value of the game is zero.  If expanding $n$ indicates that
$A\cup\set{s_i}$ is achievable once $n$ is reached, then the value of
the node $n$ is one.  Although the search space is unchanged from that
of the original imperfect information game as in \defn{game3}, there
is no longer any need to manipulate complex values, and the check for
achievability is therefore tractable in practice.

Let me illustrate this by returning to our usual example of
\secn{achieve}.  Here is the fully evaluated tree once again:
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{\scriptsize $\set{S\cup T}$}}
\put(4.6,2.0){\makebox(0,0)[l]{\scriptsize $\set{S,T}$}}
\put(.4,2.1){\makebox(0,0)[r]{\scriptsize $\set S$}}
\put(2.4,2.1){\makebox(0,0)[r]{\scriptsize $\set T$}}
\put(6.6,2.1){\makebox(0,0)[l]{\scriptsize $\set{S\cup T}$}}
\put(3.9,1.1){\makebox(0,0)[r]{\scriptsize $\set S$}}
\put(5.1,1.1){\makebox(0,0)[l]{\scriptsize $\set T$}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize $\set S$}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize $\set T$}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(3.4,-.1){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize $\set S$}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize $\set T$}}
\put(5.6,-.1){\makebox(0,0)[t]{\scriptsize $\set{S\cup T}$}}
\end{picture}
\end{center}
Note that we have replaced the value at the root with its reduction.

Now suppose that we view the set of positions as containing only two
elements, $s\in S$ and $t\in T$.  Presumably West holds the \sd Q in
$s$, and East holds three hearts in $t$.  If the ordering chosen is
$\langle s,t \rangle$, then we first try to achieve $\set s$.  In this
context, a node $n$ is a win for the maximizer if either the maximizer
can indeed win at $n$ or $s$ is no longer possible (in which case the
maximizer's ability to achieve $\set s$ is undiminished).  The game
tree becomes:
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(.4,2.1){\makebox(0,0)[r]{min}}
\put(2.4,2.1){\makebox(0,0)[r]{min}}
\put(6.6,2.1){\makebox(0,0)[l]{min}}
\put(3.9,1.1){\makebox(0,0)[r]{min}}
\put(5.1,1.1){\makebox(0,0)[l]{min}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize 0}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(3.75,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize 0}}
\put(5.25,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(.15,1.5){\makebox(0,0)[r]{$S$}}
\put(2.15,1.5){\makebox(0,0)[r]{$S$}}
\put(6.15,1.5){\makebox(0,0)[r]{$S$}}
\put(3.775,.5){\makebox(0,0)[r]{$S$}}
\put(4.775,.5){\makebox(0,0)[r]{$S$}}
\put(.85,1.5){\makebox(0,0)[l]{$T$}}
\put(2.85,1.5){\makebox(0,0)[l]{$T$}}
\put(6.85,1.5){\makebox(0,0)[l]{$T$}}
\put(4.225,.5){\makebox(0,0)[l]{$T$}}
\put(5.225,.5){\makebox(0,0)[l]{$T$}}
\end{picture}
\end{center}
All of the $T$ branches are wins for the maximizer (who is concerned
with $s$ only), and the $S$ branches are wins just in case the
maximizer does indeed win (as he does if he guesses right at either of
the first two plies).  Backing up the values gives us:
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.15){\makebox(0,0)[l]{1}}
\put(4.6,2.1){\makebox(0,0)[l]{1}}
\put(.4,2.1){\makebox(0,0)[r]{1}}
\put(2.4,2.1){\makebox(0,0)[r]{0}}
\put(6.6,2.1){\makebox(0,0)[l]{1}}
\put(3.9,1.1){\makebox(0,0)[r]{0}}
\put(5.1,1.1){\makebox(0,0)[l]{1}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize 0}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(3.75,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize 0}}
\put(5.25,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(.15,1.5){\makebox(0,0)[r]{$S$}}
\put(2.15,1.5){\makebox(0,0)[r]{$S$}}
\put(6.15,1.5){\makebox(0,0)[r]{$S$}}
\put(3.775,.5){\makebox(0,0)[r]{$S$}}
\put(4.775,.5){\makebox(0,0)[r]{$S$}}
\put(.85,1.5){\makebox(0,0)[l]{$T$}}
\put(2.85,1.5){\makebox(0,0)[l]{$T$}}
\put(6.85,1.5){\makebox(0,0)[l]{$T$}}
\put(4.225,.5){\makebox(0,0)[l]{$T$}}
\put(5.225,.5){\makebox(0,0)[l]{$T$}}
\end{picture}
\end{center}
This indicates (correctly) that the maximizer can achieve $s$ provided
that he doesn't decide to play for $T$ at the root of the tree.  Note
that this analysis is a straight minimax, allowing fast algorithms to
be applied while avoiding the manipulation of elements of $2^{2^S}$
described in the previous section.

Now we add $t$ to our achievable set, which thus becomes $\set{s,t}$.
The maximizer wins only if he really does win (and not just because 
he isn't interested in $T$ any more), and the basic tree becomes:
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.1){\makebox(0,0)[l]{max}}
\put(4.6,2.1){\makebox(0,0)[l]{max}}
\put(.4,2.1){\makebox(0,0)[r]{min}}
\put(2.4,2.1){\makebox(0,0)[r]{min}}
\put(6.6,2.1){\makebox(0,0)[l]{min}}
\put(3.9,1.1){\makebox(0,0)[r]{min}}
\put(5.1,1.1){\makebox(0,0)[l]{min}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize 0}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize 0}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(3.75,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize 0}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize 0}}
\put(5.25,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(.15,1.5){\makebox(0,0)[r]{$S$}}
\put(2.15,1.5){\makebox(0,0)[r]{$S$}}
\put(6.15,1.5){\makebox(0,0)[r]{$S$}}
\put(3.775,.5){\makebox(0,0)[r]{$S$}}
\put(4.775,.5){\makebox(0,0)[r]{$S$}}
\put(.85,1.5){\makebox(0,0)[l]{$T$}}
\put(2.85,1.5){\makebox(0,0)[l]{$T$}}
\put(6.85,1.5){\makebox(0,0)[l]{$T$}}
\put(4.225,.5){\makebox(0,0)[l]{$T$}}
\put(5.225,.5){\makebox(0,0)[l]{$T$}}
\end{picture}
\end{center}

Backing up the values gives:
\begin{center}
\thicklines\setlength{\unitlength}{.5in}\renewcommand{\dot}{{\circle*{.05}}}
\begin{picture}(7,3.5)(0,-.2)

\multiput(0,1)(1,0){8}{\dot}
\multiput(.5,2)(2,0){4}{\dot}
\multiput(3.75,0)(.5,0){4}{\dot}
\put(3.5,3){\dot}
\put(.5,2){\line(3,1){3}}
\put(3.5,3){\line(3,-1){3}}
\put(2.5,2){\line(1,1){1}}
\put(3.5,3){\line(1,-1){1}}
\multiput(0,1)(2,0){4}{\line(1,2){0.5}}
\multiput(.5,2)(2,0){4}{\line(1,-2){0.5}}
\multiput(3.75,0)(1,0){2}{\line(1,4){0.25}}
\multiput(4,1)(1,0){2}{\line(1,-4){0.25}}
\put(3.6,3.15){\makebox(0,0)[l]{1}}
\put(4.6,2.1){\makebox(0,0)[l]{0}}
\put(.4,2.1){\makebox(0,0)[r]{0}}
\put(2.4,2.1){\makebox(0,0)[r]{0}}
\put(6.6,2.1){\makebox(0,0)[l]{1}}
\put(3.9,1.1){\makebox(0,0)[r]{0}}
\put(5.1,1.1){\makebox(0,0)[l]{0}}
\put(0,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(1,.9){\makebox(0,0)[t]{\scriptsize 0}}
\put(2,.9){\makebox(0,0)[t]{\scriptsize 0}}
\put(3,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(6,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(7,.9){\makebox(0,0)[t]{\scriptsize 1}}
\put(3.75,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(4.25,-.1){\makebox(0,0)[t]{\scriptsize 0}}
\put(4.75,-.1){\makebox(0,0)[t]{\scriptsize 0}}
\put(5.25,-.1){\makebox(0,0)[t]{\scriptsize 1}}
\put(.15,1.5){\makebox(0,0)[r]{$S$}}
\put(2.15,1.5){\makebox(0,0)[r]{$S$}}
\put(6.15,1.5){\makebox(0,0)[r]{$S$}}
\put(3.775,.5){\makebox(0,0)[r]{$S$}}
\put(4.775,.5){\makebox(0,0)[r]{$S$}}
\put(.85,1.5){\makebox(0,0)[l]{$T$}}
\put(2.85,1.5){\makebox(0,0)[l]{$T$}}
\put(6.85,1.5){\makebox(0,0)[l]{$T$}}
\put(4.225,.5){\makebox(0,0)[l]{$T$}}
\put(5.225,.5){\makebox(0,0)[l]{$T$}}
\end{picture}
\end{center}
The maximizer can achieve the extended result only by making the
rightmost move, as desired.

What if the rightmost branch did not exist, so that the maximizer were
unable to combine his chances?  Now the value of the root node in the
above tree is $0$, so that $\set{s,t}$ is not achievable.  The maximal
achievable set returned by the algorithm would be $S$; had the
ordering been $\langle t,s \rangle$ instead, an alternative maximal
achievable set of $T$ would have been returned instead.

In any event, we have:

\begin{proposition} Given a game $G$ and a sequence $S$ of situations,
let $A$ be the achievable set induced by $S$ for $G$.  Then no proper
superset of $A$ in $S$ is achievable.
 \end{proposition}

\proof This is straightforward.  For any element $s\in S-A$, we know
that $U \cup \set s$ is not achievable for some $U\subseteq A$.  Thus
$A \cup \set s$ is not achievable as well.\proofend

\alg{greedy} allows us to construct maximal achievable sets relative
to our Monte Carlo sample; recall that we are taking our sequence $S$
of situations to be any ordering of the sample itself.  In practice,
however, it is important not to focus too sharply on the sample
itself, lest the eventual achievable set constructed overfit
irrelevant probabilistic characteristics of that sample.  This can be
accomplished by replacing the simple union in step \ref{unionstep} of
the algorithm with some more complicated operation that captures the
idea of ``situations that are either like $s_i$ or like those already
in $A$.''  In bridge, for example, $A$ might be all situations where
West has two or three hearts, and $s_i$ might be some new situation
where West has four hearts.  The generalized union would be situations
where West has two, three or four hearts.  If this more general set is
not achievable, another attempt could be made with the simple union.
If we denote the ``general union'' by $\oplus$, \alg{greedy} becomes:

\begin{algorithm} To construct an achievable set $A$ from a sequence
$\langle s_0,\dots,s_n\rangle$ of situations:
 \begin{enumerate}\setlength{\itemsep}{0pt}
 \item Set $A = \emptyset$.
 \item For $i=0,\dots,n$:
 \begin{enumerate}
 \item If $A\oplus\set{s_i}$ is achievable, set $A=A\oplus\set{s_i}$.
 \item Otherwise, if $A\cup\set{s_i}$ is achievable, set $A=A\cup\set{s_i}$.
 \end{enumerate}
 \end{enumerate}
\label{a.verygreedy}
\end{algorithm}

This algorithm can be used in practice to find achievable sets that
are either maximal or effectively so over the set of all possible
instances, not just those appearing in the Monte Carlo sample.

\subsection{Maximizing the payoff}

It remains to find not just maximal achievable sets, but ones that
approximate the solution to the game in question given a particular
payoff function.

To understand how we do this, let me draw an analogy between the
problem we are trying to solve and resource-constrained project
scheduling (\rcps).  In \rcps, one has a list of tasks to be
performed, together with ordering constraints saying that certain
tasks need to be performed before others.  In addition, each task uses
a certain quantity of various resources; there are limitations on the
availability of any particular resource at any particular time.  As an
example, building an aircraft wing may involve fabricating the top and
bottom flight surfaces, building the aileron, and attaching the two.
It should be clear that the aileron cannot be attached until both it
and the wing have been constructed.  Building each section may involve
the use of three sheetmetal workers, but only five may be available in
general.

The goal in an \rcps\ problem is typically to minimize the length of
the schedule (often called the {\em makespan}) without exceeding the
resource limits.  In building a wing, it is more efficient (and more
cost effective) to build it quickly than slowly.

Many production scheduling systems try to minimize makespan by
building the schedule from the initial time forward.  At each point,
they select a task all of whose predecessors have been scheduled, and
then schedule that task as early as possible given the previously
scheduled tasks and the resource constraints.  Scheduling the tasks in
this way produces a locally optimal schedule that may be improved by
modifying the order in which the tasks are selected for scheduling.

One method for finding an appropriate modification to the selection
order is known as {\em squeaky wheel optimization}, or \swo\ 
\cite{Joslin:squeak}.  In \swo, a locally optimal schedule is examined
to determine which tasks are scheduled most suboptimally relative to
some overall metric; those tasks are deemed to ``squeak'' and are then
advanced in the task list so that they are scheduled earlier when the
schedule is reconstructed.  This process is repeated, producing a
variety of candidate solutions to the scheduling problem at hand; one
of these schedules is typically optimal or nearly so.

Applying \swo\ to our game-playing problem is relatively
straightforward.\footnote{Squeaky wheel optimization was developed at
  the University of Oregon; the patent application for the technique
  has been allowed by the U.S.~Patent and Trademark Office.  The
  University's interests in \swo\ are licensed exclusively to On Time
  Systems, Inc.~for use in scheduling and related applications, and to
  Just Write, Inc.~for use in bridge-playing systems.}  When we use
\alg{verygreedy} to construct an achievable set, we also construct as
a byproduct a list of sample elements to which that achievable set
cannot be extended; moving elements of this list forward in the
sequence of $\langle s_0,\dots,s_n\rangle$ will cause them to be more
likely to be included in the achievable set $A$ if the algorithm is
reinvoked.  The weights assigned to the failing sequence elements can
be constructed by determining how representative each particular
element is of the remainder of the sample.

Returning to our example, suppose that the set $S$ (where West has the
\sd Q) has a single representative $s_1$ in the Monte Carlo sample
(presumably this means it is unlikely for West to hold the card in
question), while $T$ has five such representatives $t_1$, $t_2$,
$t_3$, $t_4$ and $t_5$.  Suppose also that the initial ordering of the
six elements is $\langle s_1,t_4,t_2,t_1,t_5,t_3 \rangle$.

Assuming that the maximizer loses his rightmost option (so that he
cannot cater to $S$ and $T$ simultaneously), the maximal achievable
set corresponding to this ordering is $S$.  An examination now reveals
that all of the $t_i$'s could have been achieved but weren't; in 
\swo\ terms, these elements of the sample ``squeak.''

At the next iteration, the priorities of the $t_i$'s are increased by
moving them forward in the sequence, while the priority of $s_1$
falls.  Perhaps the new ordering is $\langle t_4,t_2,s_1,t_1,t_5,t_3
\rangle$.

This ordering can be easily seen to lead to the maximal achievable set
$T$; $S\cup T$ is still unachievable.  But the payoff assigned to $T$
is likely to be much better than that assigned to $S$ (a probability
of 0.8 instead of 0.2, if the Monte Carlo sample itself is
unweighted).  It is in this way that \swo\ allows us to find a
globally optimal (or nearly so) achievable set.

\subsection{Results}

Our implementation of \gib's cardplay when declarer is based on the
ideas described above.  (As a defender, a direct Monte Carlo approach
appears preferable because enough information is typically available
about declarer's hand to make the double-dummy assumption reasonably
valid.)  The implementation is fast enough to conform to the time
requirements placed on a production program (roughly one {\sc cpu}
minute to play each deal).

Evaluating the impact of these ideas on \gib's cardplay is difficult,
since declarer play is already the strongest aspect of its game.  In
extended matches between the two versions of \gib, the approach based
on the ideas described here beats the Monte-Carlo based version by
approximately 0.1 \imp s/deal, but there is a great deal of noise in
the data because most of the swings correspond to differences in
bidding or defensive play.  It is possible to remove some of these
differences artificially (requiring the bidding to be identical both
times the deal is played, for example), but defensive differences
remain.  Nevertheless, \gib\ is currently a strong enough player that
the 0.1 \imp s/deal difference is significant.

The situation on problem deals, such as those from the par contests or
from the Gitelman sets, is much clearer.  In addition, many of the
deals that \gib\ gets ``wrong'' are in fact deals that \gib\ plays
correctly but that the problem composers play incorrectly (Gitelman
or, in the case of the par contests, Swiss bridge expert Pietro
Bernasconi).  In the following table, we have been generous with all
parties, deeming a line to be correct if it is not clearly inferior to
another.  Let me point out that the designers of the problems are {\em
  attempting\/} to construct deals where there is a unique solution
(the ``answer'' to the test they are posing the solver), so that a
deal with multiple solutions is in fact one that the composer has
already misanalyzed.

\begin{center}
\begin{tabular}{r|c|cccc|c}
\multicolumn 1{c|}{\bf Source} & {\bf size} & {\bf BB} & ${\Gib}_{\bf MC}$ & 
  ${\Gib}_{\bf SWO}$ & {\bf composer} & {\bf ambiguous} \\ \hline
BM level 1 & 36 & 16 & 31 & 36 & 35 & 0 \\
level 2 & 36 & 8 & 23 & 34 & 34 & 1 \\
level 3 & 36 & 2 & 12 & 34& 34 & 2 \\
level 4 & 36 & 1 & 21 & 31 & 34 & 4 \\
level 5 & 36 & 4 & 13 & 28 & 34 & 5 \\ \hline
1998 par contest & 12 &0 & 5 & 11 & 12 & 2 \\
1990 par contest & 18 & 0 & 8 & 14 & 17 & 3 \\
\end{tabular}
\end{center}
The rows are in order of increasing difficulty; it was universally
felt among the human competitors that the deals in the 1990 par
contest were far more difficult than those in 1998.  The columns are
as follows:
 \begin{center}
 \begin{tabular}{ll}
{\bf Source} & is the source from which the problems were obtained. \\
{\bf Size} & is the number of problems available from this particular source. \\
{\bf BB} & gives the number of problems solved correctly by Bridge Baron 6. \\
${\Gib}_{\bf MC}$ & gives the number solved correctly by \gib\ using a Monte
 Carlo approach. \\
${\Gib}_{\bf SWO}$ & gives the number solved correctly by \gib\ using \swo\
and achievable sets.\\
{\bf composer} & gives the number solved correctly by the composer (in that
the intended \\ & solution was the best one available).\\
{\bf ambiguous} & gives the number misanalyzed by the composer (in that 
multiple solutions \\ & exist).
 \end{tabular}
\end{center}
 
Note, incidentally, that \gib's performance is still less than perfect
on these problems.  The reason is that \gib's sample may be skewed in
some way, or that \swo\ may fail to find a global optimum among the
set of possible achievable sets.

\section{Conclusion}
\label{s.conclude}

\subsection{GIB compared}

\paragraph{Other programs}

\Gib\ participated in both the 1998 and the 2000 World Computer Bridge
Championships.  (There was no 1999 event.)  Play was organized with
each machine playing two hands and the competitors being trusted not
to cheat by ``peeking'' at partner's cards or those of the
opponents.\footnote{Starting with the 2001 event, each computer will
  handle only one of the four players, although there is still no
  attempt to prevent the (networked) computers from transmitting
  illegal information between partners.}

Each tournament began with a complete round robin among the programs,
with the top four programs continuing to a knockout phase.  The
matches in the round robin were quite short, and it was expected that
bridge's stochastic element would keep any program from being
completely dominant.

While this may have been true in theory, in practice \gib\ dominated
both round robins, winning all of its matches in 1998 and all but one
in 2000.  The round robin results from the 2000 event were as
follows:\footnote{There were eight competitors in the event: \gib\ 
  ({\sf www.gibware.com}), Hans Leber's {\sc q-plus} ({\sf
    www.q-plus.com}), Tomio and Yumiko Uchida's {\sc micro bridge}
  ({\sf www.threeweb.ad.jp/\~\ $\!\!\!\!\!$mcbridge}), Mike Whittaker
  and Ian Trackman's {\sc blue chip} bridge ({\sf
    www.bluechipbridge.co.uk}), Rod Ludwig's {\sc meadowlark} bridge
  ({\sf rrnet.com/meadowlark}), bridge {\sc baron} ({\sf
    www.bridgebaron.com}), and two newcomers: Doug Bannion's bridge
  {\sc buff} ({\sf www.bridgebuff.com}) and Yves Costel's {\sc
    wbridge} ({\sf ourworld.compuserve.com/homepages/yvescostel}).}
\begin{center}
\begin{tabular}{l|rrrrrrrr|c} &\Gib & {\sc WB} & {\sc Micro} & {\sc
Buff} & {\sc Q-Plus} &
 {\sc Chip} & {\sc Baron} & {\sc M'lark} & Total \\
\hline
\Gib             & -- & 14 & 11 & 16 &  7 & 19 & 16 & 17 & 100 \\
\sc WBridge      &  6 & -- & 19 & 13 & 16 &  7 & 18 & 20 & 99 \\
\sc Micro        &  9 &  1 & -- & 18 & 15 & 15 & 13 & 20 & 91 \\
\sc Buff         &  4 &  7 &  2 & -- & 12 & 20 &  5 & 20 & 70 \\
\sc Q-Plus       & 13 &  4 &  5 &  8 & -- & 11 & 14 & 11 & 66 \\
\sc Blue Chip    &  1 & 13 &  5 &  0 &  9 & -- & 11 & 20 & 59 \\
\sc Baron        &  4 &  2 &  7 & 15 &  6 &  9 & -- & 14 & 57 \\
\sc Meadowlark   &  3 &  0 &  0 &  0 &  9 &  0 &  6 & -- & 18 \\
\end{tabular}
\end{center}
 Each match was converted first to \imp s and then to {\em victory
points}, or VPs, with the two competing programs sharing the 20 VPs
available in each match.  The first entry in the above table indicates
that \gib\ beat {\sc wbridge} by 14 VPs to 6; the fourth that \gib\
lost to {\sc q-plus bridge} by 7 VPs to 13.  (This is \gib's only loss
ever to another program in tournament play.)

In the 1998 knockout phase, \gib\ beat Bridge Baron in the semifinals
by 84 \imps\ over 48 deals.  Had the programs been evenly matched, the
\imp\ difference could be expected to be normally distributed, and the
observed 84 \imp\ difference would be a 2.2 standard deviation event.
\Gib\ then beat Q-Plus Bridge in the finals by 63 \imps\ over 64 deals
(a 1.4 standard deviation event).  In 2000, it beat Bridge Buff by 39
\imps\ over 48 deals in the semifinals (a 1.0 standard deviation
event) and then beat {\sc wbridge} by 101 \imps\ over 58 deals (a 2.6
standard deviation event).  The finals had been scheduled to run 64
deals, but {\sc wbridge} conceded after 58 had been played.

The most publicized deal from the final was this one, an extremely
difficult deal that both programs played moderately well.  \Gib\ 
reached a better contract and was aided somewhat by {\sc wbridge}'s
misdefence in a moderately complex situation.

\vbox{
\begin{center}
\begin{tabular}{lll}
&\sd\ K Q 9 & \\
&\hs\ A Q J &\\
&\di\ 9 6 4 3 2 & \\
&\cl\ 8 6 \\
\cline{2-2}
\multicolumn 1{l|}{\sd\ 10 6} && \multicolumn 1{|l}{\hspace*{.2in}\sd\ 8 7 3 2}  \\
\multicolumn 1{l|}{\hs\ 10 9 2} && \multicolumn 1{|l}{\hspace*{.2in}\hs\ 7 5 3}  \\
\multicolumn 1{l|}{\di\ 10} && \multicolumn 1{|l}{\hspace*{.2in}\di\ A K Q J 8 5}  \\
\multicolumn 1{l|}{\cl\ A J 10 9 5 3 2} && \multicolumn 1{|l}{\hspace*{.2in}\cl\ ---}  \\
\cline{2-2}
&\sd\ A J 5 4 & \\
&\hs\ K 8 6 4 & \\
&\di\ 7 & \\
&\cl\ K Q 7 4 & \\
\end{tabular}
\end{center}
}

When {\sc wbridge} played the North-South cards and \gib\ was
East-West, North opened 1\di\ and eventually played in three notrump,
committing to taking nine tricks.  The \gib\ East started with four
rounds of diamonds as South discarded two clubs and \dots?

Looking at all four hands, the contract is cold; South can discard
another club and East has none to play.  There are thus nine tricks:
four in each of hearts and spades, and the diamond nine.

Give East a club, however, and the contract rates to be down no less
than four since the defense will be able to take at least four club
tricks.  {\sc WBridge} decided to play safe, keeping the \cl KQ and
discarding a heart.  There are now only eight tricks and the contract
was down one.

The bidding and play were more interesting when \gib\ was N-S.  North
opened 1NT, showing 11--14 HCP without four hearts or spades unless
exactly three cards were held in every other suit.  East overcalled a
natural 2\di\ and South cue bid 3\di, showing weakness in diamonds and
asking North to bid a 4-card heart or spade suit if he had one.

North has no good bid at this point.  Bidding 3NT with five small
diamonds rates to be wrong and 4\cl\ is clearly out of the question.
\Gib's simulation suggested that 3\sd\ (ostensibly showing four of
them) was the least of evils.  South raised to 4\sd, and East doubled,
ending the auction.

East led a top diamond, and shifted to the \hs 3, won by North's
\hs Q.  \Gib\ now cashed the \hs J and led the \cl 6, which East chose
(wrongly) to ruff.  {\sc WBridge} now led the \di K as East, which was
ruffed with the \sd J.  \Gib\ was now able to cash the \sd AK to
produce:

\vbox{
\begin{center}
\begin{tabular}{lll}
&\sd\ Q & \\
&\hs\ A &\\
&\di\ 9 6 2 & \\
&\cl\ 8 \\
\cline{2-2}
\multicolumn 1{l|}{\sd\ ---} && \multicolumn 1{|l}{\hspace*{.2in}\sd\ 8}  \\
\multicolumn 1{l|}{\hs\ ---} && \multicolumn 1{|l}{\hspace*{.2in}\hs\ 7}  \\
\multicolumn 1{l|}{\di\ ---} && \multicolumn 1{|l}{\hspace*{.2in}\di\ Q J 8 5}  \\
\multicolumn 1{l|}{\cl\ A J 10 9 5 3} && \multicolumn 1{|l}{\hspace*{.2in}\cl\ ---}  \\
\cline{2-2}
&\sd\ 5 & \\
&\hs\ K 8 & \\
&\di\ --- & \\
&\cl\ K Q 4 & \\
\end{tabular}
\end{center}
}

Knowing the position exactly, \gib\ needed five more tricks with North
to lead.  It ruffed a diamond, returned to the \hs A and drew East's
trump with the \sd Q.  Now a club forced an entry to the South hand,
where the \hs K provided the tenth trick.

\paragraph{Humans}

\Gib\ played a 14-deal demonstration match against human world
champions Zia Mahmood and Michael Rosenberg\footnote{Mahmood and
  Rosenberg have won, among other titles, the 1995 Cap Volmac World
  Top Invitational Tournament.  As remarked earlier, Rosenberg would
  also go on after the GIB match to win the Par Competition in which
  GIB finished 12th.} in the AAAI Hall of Champions in 1998, losing by
a total of 6.4 \imps\ (a 0.3 standard deviation event).  Early
versions of \gib\ also played on OKBridge, an internet bridge club
with some 15,000 members.\footnote{\tt http://www.okbridge.com} After
playing thousands of deals against human opponents of various levels,
\gib's ranking was comparable to the OKBridge average.

It is probable that neither of these results is an accurate reflection
of \gib's current strength.  The Mahmood-Rosenberg match was extremely
short and \gib\ appeared to have the best of the luck.  The OKBridge
interface has changed and the \gib\ `OKbots' no longer function.  The
performance figures there are thus somewhat outdated, predating
various recent improvements including all of the ideas in Sections
\ref{s.achieve}--\ref{s.swo}.  More interesting information will
become available starting in late July of 2001, when \gib, paired with
Gitelman and his regular partner Brad Moss, will begin a series of
64-deal matches against human opponents of varying skill levels.

\subsection{Current and future work} Recent work on \gib\ has focused
on its weakest areas: defensive cardplay and bidding.  The bidding
work has been and continues to be primarily a matter of extending the
existing bidding database, although \gib's bidding language is also
being changed from Standard American (a fairly natural system) to a
variant of an artificial system called Moscito developed in
Australia.\footnote{\Gib's version of Moscito is called {\em Moscito
    Byte}.}  Moscito has very sharply defined meanings, making it
ideal for use by a computer program, and is an ``action'' system,
working hard to make the opponents' bidding as difficult as possible.

With regard to defensive cardplay, the key elements of high level
defense are to make it hard for partner to make a mistake while making
it easy for declarer to do so.  Providing \gib\ with these abilities
will involve an extra level of recursion in the cardplay, as each
element of the Monte Carlo sample must now be considered from other
players' points of view, as they generate and then analyze their own
samples.  These ideas have been implemented but currently lead to
small performance degradations (approximately 0.05 \imp s/deal)
because the computational cost of the recursive analyses require
reducing the size of the Monte Carlo sample substantially.  As
processor speeds increase, it is reasonable to expect these ideas to
bear significant fruit.

In 1997, Martel, a computer scientist himself, suggested that he
expected \gib\ to be the best bridge player in the world in
approximately 2003.$^\dag$ The work appears to be roughly on schedule.

\subsection{Other games}

I have left essentially untouched the question of to what extent the
basic techniques we have discussed could be applied to games of
imperfect information other than bridge. 

The ideas that we have presented are likely to be the most applicable
in games where the perfect information variant is tractable but
computationally challenging, and the assumption that one's opponents
are playing with perfect information is a reasonable one.  This
suggests that games like hearts and other trick-taking games will be
amenable to our techniques, while games like poker (where it is
essential to realize and exploit the fact that the opponents also have
imperfect information) are likely to need other approaches.

\acks{ A great many people have contributed to the \gib\ project over
  the years.  In the technical community, I would like to thank
  Jonathan Schaeffer, Rich Korf, David Etherington, Bart Massey and
  the other members of \cirl.  In the bridge community, I have
  received invaluable assistance from Chip Martel, Rod Ludwig, Zia
  Mahmood, Andrew Robson, Alan Jaffray, Hans Kuijf, Fred Gitelman, Bob
  Hamman, Eric Rodwell, Jeff Goldsmith, Thomas Andrews and the members
  of the rec.games.bridge community.  The work itself has been
  supported by Just Write, Inc., by DARPA/Rome Labs under contracts
  F30602-95-1-0023 and F30602-97-1-0294, and by the Boeing Company
  under contract AHQ569.  To everyone who has contributed, whether
  named above or not, I owe my deepest appreciation.}

\appendix
\section{A summary of the rules of bridge}
\label{a.rules}

We give here a very brief summary of the rules of bridge.  Readers
wanting a more complete description are referred to any of the many
excellent texts available \cite{Sheinwold}.

Bridge is a card game for four players, who are split into two pairs.
Members of a single pair sit opposite one another, so that North-South
form one pair and East-West the other.  The deck is distributed evenly
among the players, so that each deal involves giving each player a
{\em hand\/} of 13 cards.  The game then proceeds through a bidding
and a playing phase.

The playing phase consists of 13 {\em tricks}, with each player
contributing one card to each trick in a clockwise fashion.  The
player who plays first to any trick is said to {\em lead\/} to that
trick.  The highest card of the suit led wins the trick (Ace is high
and deuce low), unless a trump is played, in which case the highest
trump wins the trick.  The person who leads to a trick is free to lead
any card he wishes; subsequent players must play a card of the suit
led if they have one, and can play any card they choose if they don't.
The winner of one trick leads to the next; the person who leads to the
first trick (the {\em opening leader}) is determined during the
bidding phase of the game.

The object of the card play phase is always for your partnership to
take as many tricks as possible; there is no advantage to one
partner's taking a trick over another, and the order in which the
tricks are taken is irrelevant.  After the opening leader plays the
first card to the first trick, the player to his left places his cards
face up on the table so that all of the other players can see them.
This player is called the {\em dummy}, and when it is dummy's turn to
play, dummy's partner (who can see the partnership's combined assets)
selects the card to be played.  Dummy's partner is called the {\em
declarer\/} and the members of the other pair are called the {\em
defenders}.

The purpose of the bidding phase is to identify trumps and the
declarer, and also the {\em contract}, which will be described
shortly.  The opening leader is identified as well, and is the player
to the declarer's left.

During the bidding phase, various contracts are proposed.  The dealer
has the first opportunity to propose a contract and subsequent
opportunities are given to each player in a clockwise direction.  Each
player has many opportunities to suggest a contract during this phase
of the game, which is called the {\em auction}.  Each partnership is
required to explain the meanings of their actions during the auction
to the other side, if requested.

Each contract suggests a particular trump suit (or perhaps that there
not be a trump suit at all).  Each player suggesting a contract is
committing his side to winning some particular number of the 13
available tricks.  The minimum commitment is 7 tricks, so there are 35
possible contracts (each of 4 possible trumps, or no trumps, and seven
possible commitments, from seven to thirteen tricks).  These 35
contracts are ordered, which guarantees that the bidding phase will
eventually terminate.

After the bidding phase is complete, the side that suggested the
final contract is the {\em declaring side}.  Of the two members
of the declaring side, the one who first suggested the eventual
trump suit (or no trumps) is the declarer.  Play begins with the
player to the declarer's left leading to the first trick.

After the hand is complete, there are two possible outcomes.  If the
declaring side took at least as many tricks as it committed to taking,
the declaring side receives a positive score and the defending side an
equal but negative score.  There are substantial bonuses awarded for
committing to taking particular numbers of tricks; in general, the
larger the commitment, the larger the bonus.  There are small bonuses
awarded for winning tricks above and beyond the commitment.

If the declaring side failed to honor its commitment, it receives a
negative score and the defenders receive an equal but positive score.
The overall score in this case (where the declarer ``goes down'') is
generally smaller than the overall score in the case where declarer
``makes it'' (i.e., honors his commitment).

\section{A new ending discovered by GIB}
\label{a.new}

This deal occurred during a short \imp\ match between \gib\ and Bridge
Baron.

\vbox{
\begin{center}
\begin{tabular}{lll}
&\sd\ 9 6 & \\
&\hs\ Q J 8 5 &\\
&\di\ A Q 3 & \\
&\cl\ K J 10 8 \\
\cline{2-2}
\multicolumn 1{l|}{\sd\ K Q J 8 7 5} && \multicolumn 1{|l}{\hspace*{.2in}\sd\ 4 3}  \\
\multicolumn 1{l|}{\hs\ 9 4 3} && \multicolumn 1{|l}{\hspace*{.2in}\hs\ A 7 2}  \\
\multicolumn 1{l|}{\di\ 7} && \multicolumn 1{|l}{\hspace*{.2in}\di\ J 10 6 2}  \\
\multicolumn 1{l|}{\cl\ 6 4 2} && \multicolumn 1{|l}{\hspace*{.2in}\cl\ A Q 7 3}  \\
\cline{2-2}
&\sd\ A 10 2 & \\
&\hs\ K 10 6 & \\
&\di\ K 9 8 5 4 & \\
&\cl\ 9 5 & \\
\end{tabular}
\end{center}
}
 \noindent With South (\gib) dealing at unfavorable vulnerability, the
 auction went P--2\sd--X--P--3NT--all pass.  (P is pass and X is
 double.)  The opening lead was the \sd K, ducked by \gib, and Bridge
 Baron now switched to a small heart.  East won the ace and returned
 to spades, \gib\ winning.
 
 \Gib\ cashed all the hearts, pitching a small club from its hand.  It
 then tested the diamonds, learning of the bad break and winning the
 third diamond in hand.  It then led the \di 9 in the following
 position:

\vbox{
\begin{center}
\begin{tabular}{lll}
&\sd\ --- & \\
&\hs\ --- & \\
&\di\ --- & \\
&\cl\ K J 10 8 & \\
\cline{2-2}
\multicolumn 1{l|}{\sd\ Q} && \multicolumn 1{|l}{\hspace*{.2in}\sd\ ---}  \\
\multicolumn 1{l|}{\hs\ ---} && \multicolumn 1{|l}{\hspace*{.2in}\hs\ ---}  \\
\multicolumn 1{l|}{\di\ ---} && \multicolumn 1{|l}{\hspace*{.2in}\di\ J}  \\
\multicolumn 1{l|}{\cl\ ? ? ?} && \multicolumn 1{|l}{\hspace*{.2in}\cl\ A ? ?}  \\
\cline{2-2}
&\sd\ 10 & \\
&\hs\ --- & \\
&\di\ 9 8 & \\
&\cl\ 9 & \\
\end{tabular}
\end{center}
}
 \noindent When \gib\ pitched the {\em ten\/} of clubs from dummy (it
had been aiming for this ending all along), the defenders were
helpless to take more than two tricks independent of the location of
the club queen.  At the other table, Bridge Baron let \gib\ play in
2\sd\ making exactly, and \gib\ picked up 12 \imp s.

\vskip 0.2in
\bibliography{bib}
\bibliographystyle{theapa}

\end{document}
