Skip to content

ENH: Implement pure strategy node reachability check #629

Description

@d-kad

Description.

The goal is to introduce a new method, GameNode::IsStrategyReachable(), to determine if a given node in an extensive tree form can be reached by any pure strategy profile. A node is reachable if there exists at least one pure strategy profile where the resulting path of play passes through that node. A pure strategy requires the player to choose the same action at every member node of that information set. In games with absent-mindedness, a path of play may visit the same information set multiple times, making some of the ancestors of its member nodes unreachable.

The existing GameTreeRep::BuildInfosetParents() method already handles the logic for absent-minded revisiting information sets. This traversal will be leveraged to collect the set of reachable decision nodes.

Implementation Plan.

  1. In GameTreeRep, add member:
    mutable std::set<GameNodeRep *> m_reachableNodes;
  2. Define the public API on the node, consistent with existing properties, e.g., IsTerminal() and IsSubgameRoot():
    In GameNodeRep, add the method bool IsStrategyReachable() const;
  3. Modify GameTreeRep::BuildInfosetParents() to populate the m_reachableNodes set.
  4. Implement GameNodeRep::IsStrategyReachable() to trigger computation if needed and perform the check.
  5. Python API: Add a read-only property Node.is_strategy_reachable.

Metadata

Metadata

Assignees

Labels

c++Items which involve writing in C++cythonItems which involve coding in Cythonenhancement

Projects

Status
Done

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions