[GameAlgebra]: Setting information sets and extending the game with new moves

[tturocy]

This discussion relates to these operations currently provided on Game (PyGambit names for operations used):

• set_player
• set_infoset
• leave_infoset
• set_chance_probs
• add_action
• delete_action
• append_move
• append_infoset

We have often organised these as two different types of operation, but the suggestion here is we need to think about them jointly. The reason is that we can think of a game tree as being defined by:

1. For every history, which player (if any) has the move, and what the set of actions are available to the player at that history;
2. Which sets of histories are information sets, that is, are equivalence classes from the perspective of the player with the move.

Let's start by assuming we have a full tree structure already built and we are thinking about transforming information sets.

Defining information sets

We propose that the existing operations set_player, set_infoset, and leave_infoset could be replaced by a single operation: make_infoset(nodes, player):

• nodes would be a set of nodes which have conformant sets of action labels.
• player would be the label of the player to have the move. (For the moment let's put to one side chance moves versus player moves).

It would be an error if all of the nodes did not have the same set of action labels. If all of nodes are already in the same information set, this could accomplish re-assigning the move to a different player. If nodes are currently in different information sets, then any information sets emptied by this operation would be "deleted" (although this is not the best way to think about this). leave_infoset could be accomplished by calling make_infoset with a singleton node.

Changing the move at information sets

(Note: add_action and delete_action are actually missing from the documentation index!). We propose that changing the sets of actions at an information set could be implemented by a single operation set_actions(infoset, actions). This would eliminate the need for separate add and delete operations - and further the awkwardness of "inserting" an action in add_action.

For a personal player, actions would be a list of labels. For a chance move, this would be a dictionary from labels to probabilities, where the probabilities must some to one. This would solve the current awkwardness noted in #378.

Question: Would it be desirable to require the addition or deletion of actions to have an explicit flag attached? That is, something like set_actions(infoset, actions, drop: bool = False, add: bool = False)?

A separate operation would allow relabelling of actions via relabel_actions(infoset, action_map), where the action_map would specify current and new labels.

Adding new nodes

Here is where there is some interaction with setting information structures. When we are building out a tree by adding new moves, we currently have append_move and append_infoset. append_move is probably just about correct for what we have in mind now: it takes a set of terminal nodes and creates a move at all of them, and places them all in the same information set. This is very consistent with our "game algebra" idea already.

However, this operation isn't sufficient, as examples of "games without public clocks" show; it is not possible to build all possible games using just append_move.

append_infoset is not strictly needed, especially if we define make_infoset as proposed above. However, append_infoset could be retained as a convenience, and have it be defined simply by the appropriate composition of append_move and make_infoset.

Semantics of infosets

An important change will be that information sets will no longer be exposed as objects in their own right. This is a current problem with the game operations. An information set object resolves not to a set of nodes but to an actual C++ object. The nodes associated with that object can change.

Instead, an information set should point to a node. So when we talk about an "information set" we would be talking about "the set of histories which are equivalent to this one from the perspective of the player who has the move"