In two important places - the normal form and sequence form (the latter currently in src/solvers/enumpoly/gameseq.(cc,h)) we have the problem of indexing into an N+1 dimensional array representing an N-player game.
We want these to be efficient processes internally. There is a straightforward method for mapping ("raveling") an $(N+1)$-tuple of integers to an index in a contiguous vector. However, externally, calling code working with these objects operates in terms of game objects (strategies, sequences).
After a recent significant refactoring we've left the sequence form currently going through an indirect step - it converts a map of sequences to an array of integers, then passes this to a separate NDArray class, which is very inefficient. This isn't critical right now because the amount of time spent accessing these values is small relative to the computational runtime of solving such games. However, we should have a better implementation, not least because we can apply the same code to the strategic form representation.
Two additional observations:
We may be able to take some inspirations from not only numpy arrays, but also DataFrames a la pandas - essentially we have a similar task of having $N$-dimensional array of data which we want to be able to refer to by labels, and also potentially to take slices of.
A common need is to iterate over all (or a subset of) contingencies. For this the arithmetic to update the current integer raveled index is quite straightforward and efficient - so a bespoke iterator should be included.
The question is what's the best way to do this - the code to do this mapping is only a few lines in principle, but how best to package it so we can use it any place we need to have $N$ or $N+1$-dimensional tables.
In two important places - the normal form and sequence form (the latter currently in
src/solvers/enumpoly/gameseq.(cc,h)
) we have the problem of indexing into an N+1 dimensional array representing an N-player game.We want these to be efficient processes internally. There is a straightforward method for mapping ("raveling") an $(N+1)$-tuple of integers to an index in a contiguous vector. However, externally, calling code working with these objects operates in terms of game objects (strategies, sequences).
After a recent significant refactoring we've left the sequence form currently going through an indirect step - it converts a map of sequences to an array of integers, then passes this to a separate
NDArray
class, which is very inefficient. This isn't critical right now because the amount of time spent accessing these values is small relative to the computational runtime of solving such games. However, we should have a better implementation, not least because we can apply the same code to the strategic form representation.Two additional observations:
numpy
arrays, but alsoDataFrame
s a lapandas
- essentially we have a similar task of having $N$-dimensional array of data which we want to be able to refer to by labels, and also potentially to take slices of.The question is what's the best way to do this - the code to do this mapping is only a few lines in principle, but how best to package it so we can use it any place we need to have $N$ or $N+1$-dimensional tables.