Estimates for the Branching Factors of Atari Games

Autor:	Nelson, Mark J.
Rok vydání:	2021
Předmět:	Computer Science - Artificial Intelligence
Druh dokumentu:	Working Paper
Popis:	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. Comment: Accepted at IEEE Conference on Games (CoG) 2021
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2107.02385 Zobrazit plný text záznamu View this record from Arxiv