  In this paper we study how to play (stochastic) games optimally using little
space. We focus on repeated games with absorbing states, a type of two-player,
zero-sum concurrent mean-payoff games. The prototypical example of these games
is the well known Big Match of Gillete (1957). These games may not allow
optimal strategies but they always have {\epsilon}-optimal strategies. In this
paper we design {\epsilon}-optimal strategies for Player 1 in these games that
use only O(log log T ) space. Furthermore, we construct strategies for Player 1
that use space s(T), for an arbitrary small unbounded non-decreasing function
s, and which guarantee an {\epsilon}-optimal value for Player 1 in the limit
superior sense. The previously known strategies use space {\Omega}(logT) and it
was known that no strategy can use constant space if it is {\epsilon}-optimal
even in the limit superior sense. We also give a complementary lower bound.
Furthermore, we also show that no Markov strategy, even extended with finite
memory, can ensure value greater than 0 in the Big Match, answering a question
posed by Abraham Neyman.
