Skip to content

ENH: Improve implementation of IsPerfectRecall #484

@tturocy

Description

@tturocy

Our implementation of GameTreeRep::IsPerfectRecall is quite inelegant and unnecessarily inefficient. Roughly, it looks at each pair of information sets and checks whether one always precedes the other.

We have developed a new method, which first computes for each information set the set of own-player actions that can (immediately) precede it in a play of the game. This requires only one pass through the game tree (all players' information sets can be so labeled in one pass). Then, whether a game is perfect recall can be determined by examining this graph.

We want to replace the existing implementation of IsPerfectRecall with a method based on this data structure, and add appropriate test cases to the pygambit test suite to exercise this, for both general imperfect recall examples and absent-mindedness.

Metadata

Metadata

Assignees

Labels

c++Items which involve writing in C++cythonItems which involve coding in CythonpythonItems which involve coding in Python

Type

Projects

No projects

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions