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
| CREATOR | Hugo Gimbert, Soumyajit Paul, B. Srivathsan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-13933