  Fictitious play is an algorithm for computing Nash equilibria of matrix
games. Recently, machine learning variants of fictitious play have been
successfully applied to complicated real-world games. This paper presents a
simple modification of fictitious play which is a strict improvement over the
original: it has the same theoretical worst-case convergence rate, is equally
applicable in a machine learning context, and enjoys superior empirical
performance. We conduct an extensive comparison of our algorithm with
fictitious play, proving an optimal convergence rate for certain classes of
games, demonstrating superior performance numerically across a variety of
games, and concluding with experiments that extend these algorithms to the
setting of deep multiagent reinforcement learning.
