Simplifying imperfect recall games

Hugo Gimbert, Soumyajit Paul, B. Srivathsan · 2025

Read Simplifying imperfect recall games by Hugo Gimbert, Soumyajit Paul, B. Srivathsan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-13933.txt.

Description

In some games, a player can forget moves they made earlier, and solving such games is known to be very hard in general. Hugo Gimbert, Soumyajit Paul, and Srivathsan look for kinds of forgetful games that computers can still solve fast. One friendly kind, called A-loss recall, already has efficient methods. The authors show how to reshape other games into that kind without changing what the game means.

Their first trick shuffles the order of actions. It defines a new, larger class of games that can still be solved in polynomial time. The second trick builds new action sequences that can be combined to stand in for the old ones. The reshaped game has a simpler memory structure, though it can grow much bigger. An algorithm produces the smallest such reshaped game, giving solvers a practical path into forgetful-game problems.

Catalog record

CREATORHugo Gimbert, Soumyajit Paul, B. Srivathsan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-13933

Browse the full library · About the Tower of Babel