Board game AI research quotes branching factors quite a bit. For example, go's branching factor of ~250 versus ~35 for chess is an old argument for it being a harder game – at least for AI. Videogame AI research doesn't use the concept much though.
— Mark Nelson (@mm_jj_nn) July 6, 2021
Two reasons branching factors are lower than the available actions: 1) multiple action sequences can lead to the same state (think of equivalent rotation/translation sequences in Tetris) and 2) sometimes input is ignored (e.g. while a jump animation is playing out in Q*bert).
— Mark Nelson (@mm_jj_nn) July 6, 2021
The first wrinkle: what constitutes a "state" in ALE, in the sense of a tree-search or MDP state? As far as I can tell, it isn't possible to compute proper states from the public API of ALE, so I had to patch it.
— Mark Nelson (@mm_jj_nn) July 6, 2021
The paddle controller is this weird thing, a potentiometer that you rotate, used first (I think) for Pong. When the paddle is in use, left/right actions in ALE move the controller PADDLE_DELTA to the left/right, compared to its current position. pic.twitter.com/QNzljrlurv
— Mark Nelson (@mm_jj_nn) July 6, 2021
To be fair, only a handful of games use it: of the 104 games supported by ALE, 98 use the joystick, and 6 use the paddle. But still, I'd like a definition of state that works for Pong and Breakout too, not only the 98 joystick games.
— Mark Nelson (@mm_jj_nn) July 6, 2021
To be fair, only a handful of games use it: of the 104 games supported by ALE, 98 use the joystick, and 6 use the paddle. But still, I'd like a definition of state that works for Pong and Breakout too, not only the 98 joystick games.
— Mark Nelson (@mm_jj_nn) July 6, 2021
Once state is defined, the next wrinkle: the Atari is deterministic in principle, but ALE has bugs making it not! Which is bad for counting states in a game tree. Fortunately, @JesseFarebro has a patch that (mostly?) fixes it, not yet in official ALE. https://t.co/cMv29wMSxM
— Mark Nelson (@mm_jj_nn) July 6, 2021
Nonetheless, I now had a correct definition of state and a patched ALE that seems to pass a sanity check on at least most of the games. So the next step is to count states.
— Mark Nelson (@mm_jj_nn) July 6, 2021
The thread continues on Twitter. Check it out, and the paper too! Here's the abstract:
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.
No comments:
Post a Comment