  Direct reciprocity is a mechanism for the evolution of cooperation based on
repeated interactions. When individuals meet repeatedly, they can use
conditional strategies to enforce cooperative outcomes that would not be
feasible in one-shot social dilemmas. Direct reciprocity requires that
individuals keep track of their past interactions and find the right response.
However, there are natural bounds on strategic complexity: Humans find it
difficult to remember past interactions accurately, especially over long
timespans. Given these limitations, it is natural to ask how complex strategies
need to be for cooperation to evolve. Here, we study stochastic evolutionary
game dynamics in finite populations to systematically compare the evolutionary
performance of reactive strategies, which only respond to the co-player's
previous move, and memory-one strategies, which take into account the own and
the co-player's previous move. In both cases, we compare deterministic strategy
and stochastic strategy spaces. For reactive strategies and small costs, we
find that stochasticity benefits cooperation, because it allows for
generous-tit-for-tat. For memory one strategies and small costs, we find that
stochasticity does not increase the propensity for cooperation, because the
deterministic rule of win-stay, lose-shift works best. For memory one
strategies and large costs, however, stochasticity can augment cooperation.
