Estimates for the Branching Factors of Atari Games
  The branching factor of a game is the average number of new states reachable
from a given state. It is a widely used metric in AI research on board games,
but less often computed or discussed for videogames. This paper provides
estimates for the branching factors of 103 Atari 2600 games, as implemented in
the Arcade Learning Environment (ALE). Depending on the game, ALE exposes
between 3 and 18 available actions per frame of gameplay, which is an upper
bound on branching factor. This paper shows, based on an enumeration of the
first 1 million distinct states reachable in each game, that the average
branching factor is usually much lower, in many games barely above 1. In
addition to reporting the branching factors, this paper aims to clarify what
constitutes a distinct state in ALE.
