This paper investigates the evolutionary foundation for our capacity to attribute preferences to others. This ability is intrinsic to game theory, and is a key component of "Theory of Mind'' (ToM), perhaps the capstone of social cognition. We argue here that this component of theory of mind allows organisms to efficiently modify their behavior in strategic environments with a persistent element of novelty. In particular, we consider an evolutionary environment in which players interact with one another while the set of games that they might face becomes larger and larger with time. We then compare two types of agents --- a naive type that adapts to each particular game through repeated exposure to it --- as in reinforcement learning --- and a ToM type that knows his opponents have preferences and can infer these from observed behavior. We show that ToM yields a sharp and unambiguous advantage over naivete when novel games are introduced at an intermediate rate. The edge to ToM arises because a ToM type can acquire opponent preferences by observing behavior in previous games and can then use this knowledge to make the correct choice in novel circumstances, while the naive type requires direct exposure to each new game. In related experiments, we demonstrate that there is a highly significant tendency for subjects to learn preferences of opponents, rather than to learn the game. That is, we provide strong evidence for the presence of ToM in the sense of our model. Moreover, scores on standard measures of autism-spectrum behaviors are significant determinants of individual speed of learning, indicating that our notion of ToM is correlated with ToM as it is understood in psychology.