  We present efficient algorithms for computing optimal or approximately
optimal strategies in a zero-sum game for which Player I has n pure strategies
and Player II has an arbitrary number of pure strategies. We assume that for
any given mixed strategy of Player I, a best response or "approximate" best
response of Player II can be found by an oracle in time polynomial in n. We
then show how our algorithms may be applied to several search games with
applications to security and counter-terrorism. We evaluate our main algorithm
experimentally on a prototypical search game. Our results show it performs well
compared to an existing, well-known algorithm for solving zero-sum games that
can also be used to solve search games, given a best response oracle.
