ENH: Collections of nodes

[tturocy]

There is not yet a built-in way to get (sub)sets of the nodes of an extensive game. Some ideas:

• Game.nodes returns a collection of nodes. Presumably this should be implemented implicitly - it should return an e.g. NodeSet object rather than an explicit list of nodes.
• This NodeSet should define the ability to filter on a boolean function. Possibly getitem should be used for this (which would be similar to pandas indexing), although perhaps a .filter() member could be defined instead.

This might then combine well with #188 (nodes as histories) in building games - as it would be easy e.g. to filter on "all terminal nodes with histories matching a particular pattern".

[tturocy]

In the intervening time we have done some further thinking on this. This is motivated a bit by thoughts following on from #587, which changed how the Node.children collection was indexed, and #188.

First, it would be useful to think of nodes in a tree as being synonymous with their paths, and therefore to have path-like operations on them. #188 and #587 suggested implementing add, which would take a Node as the left argument and an action or action label as the right argument, and produce the child of the node following that action.

However, why stop at nodes? Thinking about how selectors work in various methods for working with hierarchical documents like XML or JSON, it would be useful to have that information set plus an action (at that information set of course) would produce the set of nodes which follow the information set's members by following that action.

But it can also be useful to have similar operations that work on more arbitrary sets of nodes. For example, in the tutorial showing how to build the one-card poker example from Myerson's (1991) textbook. it would be very useful to be able to select two sets of nodes:

• The nodes which follow the "Raise" action of the first player;
• The nodes which follow the "Fold" action of the first player.

For this, you might want something like g.root.children + "Raise" and g.root.children + "Fold". Note that in this case "Raise" and "Fold" are action labels which appear at both information sets of the first player, so the intent of this syntax is clear - that is, for each node in the set of nodes, attempt to find its child following an action labeled "Raise".

But then, having to write .children is verbose. You might want something like g.root + "*" + "Raise".

Also, thinking about this syntax being applied to sets, perhaps + is not the right operator. Python doesn't define + for sets, but it does define it for lists, and someone might rightly be confused in thinking that .children is a list (because they do have a deterministic order in the way Gambit defines games). Also, g.root + "*" + "Raise" wouldn't mean the same thing as. g.root + ("*" + "Raise"), which would break the associativity rules we naturally associate with +. Observe that Python's pathlib uses the forward-slash / operator, and so perhaps g.root / "*" / "Raise" would be less ambiguous, especially as g.root / ("*" / "Raise") would not be meaningful. This would potentially then allow us to define operators like | and - on sets of nodes in the intuitive way.

Finally, there is the question of what happens in an arbitrary nodeset when the next action matches only some of the nodes. Would this fail with an exception, or would it drop any nodes that don't match? One possibility is to define / to return only matching child nodes (and silently drop those that don't), and // to require matches at all nodes (and raise an exception if not).

This all works well also only if actions are required to have unique (non-empty) labels. This has not historically been enforced. However, also given the work that is being done on game generation and equivalence checking, perhaps it is time to consider doing this.