MAINT: Refactor implementation of generation of reduced normal form strategies

[tturocy]

Overview

The TreeGameRep class for extensive forms has built-in generation of the set of reduced normal form strategies. The implementation of this is some of the oldest code in Gambit - variable names can be traced to the implementation circa 1990.

There is a better way to approach this problem using the concept of the "power" of an action. To realise this we will need to add some new concepts to games, which concepts are interesting in their own right in addition to being useful for computing the reduced normal form.

Plan

• Extend GameTreeRep to keep track of the total number of nodes in the game. #491
• FEAT: Compute the plays consistent with nodes, infosets, actions #517
• FEAT: Implement the concept of the power of an action #522

[emiliomarquez]

Is this still open or has this been implemented already? If its still open and not been implemented, I am going to try refactoring it

[tturocy]

At the moment it's not being actively worked on, so feel free to have a go!

[tturocy]

To make this more concrete, we will write a function like this (type names provisional/indicative at this point)

using StrategyMap = std::map<GameInfoset, GameAction>;

std::map<GamePlayer, std::list<StrategyMap>> MakeReducedStrategies(const Game &);

This is a global-scope function (in the Gambit namespace). It shouldn't need to access the internals of games at all - it should be able to do the calculation entirely using public members of Game.

[tturocy]

We've settled on a concrete plan for accomplishing this:

• Add a function in C++ which returns the action at an information set for a given strategy
• Expose that function via Cython in pygambit
• Write a pure-Python implementation of the algorithm to compute reduced strategy sets
• Write tests which confirm the new implementation produces the same results (and therefore we have a test suite)
• Re-implement the pure-Python algorithm in C++ and replace the old implementation, using the test suite to confirm there are no regressions

[tturocy]

The first commit on issue_440 deals with the first two items above with a temporary interface to the action mapping. This is enough to enable progress on the broader issue, but will need to be polished before we merge this work into master.