Fetching the paper…

Reading the bibliography…

2021

Estimates for the Branching Factors of Atari Games

Nelson, Mark J.

Original
PDF
Post on X

Understand

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.

Estimates for the Branching Factors of Atari Games · Around

Built on

“Depth-First Iterative-Deepening: An Optimal Admissible Tree Search”
Richard Korf · 1985
Earlier work this paper cites.
“Checkers: A preview of what will happen in chess?”
Jonathan Schaeffer · 1991
Earlier work this paper cites.
“Natural Developments in Game Research: From Chess to Shogi to Go”
Hitoshi Matsubara, Hiroyuki Iida and Reijer Grimbergen · 1996
Earlier work this paper cites.

Similar

“The Arcade Learning Environment: An Evaluation Platform for General Agents”
Marc Bellemare, Yavar Naddaf, Joel Veness and Michael Bowling · 2013
Cited alongside, same era.
“The Impact of Determinism on Learning Atari 2600 Games”
Matthew Hausknecht and Peter Stone · 2015
Cited alongside, same era.
“Frame Skip is a Powerful Parameter for Learning to Play Atari”
Original
Alex Braylan, Mark Hollenbeck, Elliot Meyerson and Risto Miikkulainen · 2015
Cited alongside, same era.

Then

“Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents”
Marlos Machado et al · 2018
Later among the works it cites.
“Ludii User Guide”, 2021
Dennis… Soemers, Eric Piette, Matthew Stephenson and Cameron Browne · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…