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