gambitproject
MAINT: Refactor implementation of generation of reduced normal form strategies
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
- [x] #491
- [x] #517
- [x] #522
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
At the moment it's not being actively worked on, so feel free to have a go!
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.
We've settled on a concrete plan for accomplishing this:
- [x] Add a function in C++ which returns the action at an information set for a given strategy
- [x] 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
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.