matrix_game_utils missing sequence-form sparse matrix conversion?

[masonmcbride]

It looks like ExtensiveToMatrixGame defaults to creating a payoff matrix of all pure strategies but that is far from desirable now. Especially with the new sparsification techniques, is there any option to convert the extensive form game (kuhn poker for example) into its sparse matrix form based on sequences?

[masonmcbride]

I want to explore solving games using linear programs and I am struggling to find a general method that converts the way I have written kuhn poker to implement CFR and the sparse sequence-form version used in modern LP methods. I thought ExtensiveToMatrixGame would help but it just goes to pure strategies.

[lanctot]

Hi @masonmcbride,

ExtensiveToMatrixGame is just a demonstration for toy games. I'm not sure what method you're referring to (can you be more specific?), but I can say with a high degree of certainty that it's not implemented in OpenSpiel.

OpenSpiel only has limited support for the sequence-form and mostly an intermediate step to be able to send them to solvers (though https://github.com/deepmind/open_spiel/pull/871 is a step toward better native support, but would be in Python). You can see what we have here and here.

It would be good to have support for other game representations and more easily convert to and from (I talked about it briefly here: https://github.com/deepmind/open_spiel/issues/783#issuecomment-1035360039), but the main focus has been on reinforcement learning and hence the extensive-form. So this would likely have to come via external contributions.

[masonmcbride]

Thank you for the reply! To be more specific I meant this paper from Mr Farina: Fast Payoff Matrix Sparsification Techniques for Structured Extensive-Form (http://aaai.org/AAAI22Papers/AAAI-10793.FarinaG.pdf)

[ryan-dorazio]

is there any option to convert the extensive form game (kuhn poker for example) into its sparse matrix form based on sequences?

@masonmcbride Not sure about Farina et. al. but to your original question, as @lanctot pointed out, #871 includes some new methods in open_spiel.python.algorithms.sequence_form_utils that allow you to construct the sequence form payoff matrix but it is in python. Here's an example of how you can extract the payoff matrix for Kuhn:

from open_spiel.python.algorithms import sequence_form_utils
import pyspeil

game = pyspiel.load_game("kuhn_poker")

infosets, infoset_actions_to_seq, \
        infoset_action_maps, infoset_parent_map, \
        payoff_mat, infoset_actions_children = sequence_form_utils.construct_vars(game)

There's a lot of variables constructed from sequence_form_utils.construct_vars but the one of interest is payoff_mat which is a just a numpy array (matrix). This might be a good start if you're okay with working in python.

If you look at the test file for sequence_form_utils.construct_vars https://github.com/deepmind/open_spiel/blob/b5e0bf6495bd8baf7c6011c18fa4fd403e21385d/open_spiel/python/algorithms/sequence_form_utils_test.py#L74-L86 you can see how the policy values for each player can be computed by doing a matrix multiplication with the sequences and the payoff matrix.